Qual é o papel apropriado da verificação em amostragem quântica, simulação e teste de Church-Turing estendido (ECT)?

9

Como nenhuma resposta foi dada, foi definido um sinalizador solicitando que essa pergunta fosse convertida em um wiki da comunidade.


Os comentários de Aaron Sterling, Sasho Nikolov e Vor foram sintetizados na seguinte resolução, que está aberta para discussão no wiki da comunidade:

Resolvido:    com relação aos algoritmos clássicos que produzem números, amostras ou trajetórias de simulação, uma lógica matemática rigorosa exige que todas as quatro proposições a seguir sejam aceitas ou nenhuma delas:

  1. Podemos descartar um algoritmo clássico de tempo polinomial para gerar números aleatórios.  [1]
  2. "Podemos descartar um algoritmo clássico de tempo polinomial para amostrar a distribuição de saída de um computador quântico, sob a única suposição de que a hierarquia polinomial é infinita".  [2]
  3. "Não podemos simular [uma trajetória mecânica quântica] da maneira usual ... há muitas variáveis". ψ(t) [3]
  4. A extensa Tese de Church-Turing (ECT) é descartada, pelo motivo rigoroso de que algoritmos clássicos não podem gerar números aleatórios.  [4]

Para iniciar a discussão, aqui estão respostas afirmativas e negativas que, embora cada uma seja defensável, são deliberadamente superexpostas. Um argumento fortemente afirmativo pode ser:

Afirmativo:   essas quatro afirmações refletem teoremas que, para respeitar o rigor, exigem que nunca falemos de algoritmos clássicos que geram números aleatórios, amostras aleatórias ou simulações quânticas, mas sim que falemos apenas de algoritmos clássicos que geram números pseudoaleatórios e (por extensão) amostras pseudo-aleatórias e simulações de pseudo-quantum.

Sendo assim, todas as quatro afirmações são verdadeiras. Além disso, para evitar ambiguidade e evitar confusão, os matemáticos devem incentivar cientistas e engenheiros a afixar o prefixo "pseudo-" a quase todos os usos de "aleatória", "amostra" e "simulação quântica".

Um argumento fortemente negativo pode ser:

Negativo:   Essas afirmações (e seus teoremas formais associados) são postes de sinalização que nos levam a um distrito de "luz vermelha" no estilo de Lakatos, em que somos chamados a abraçar com entusiasmo (o que poderia ser chamado) as disciplinas da pseudo-aleatoriedade , pseudo-amostragem e pseudo-simulação ... práticas matemáticas divertidas por uma razão deliciosamente pecaminosa: elas atingem efeitos matemáticos que a lógica formal diz que são impossíveis. Portanto, o que poderia ser mais mágico e mais divertido do que essa conclusão: as quatro afirmações da resolução são formalmente verdadeiras, mas praticamente falsas?

Sendo assim, todas as quatro afirmações são falsas. Além disso, como a maioria das práticas de "aleatoriedade", "amostragem" e "simulação quântica" ocorrem nesse ambiente mágico - no qual questões associadas à complexidade de Kolmogorov e às avaliações oraculares são deliberadamente ignoradas - são os matemáticos que devem alterar seu uso.

Realisticamente, porém, como os teóricos da complexidade devem expressar suas descobertas relacionadas à aleatoriedade, amostra e simulação ... por um lado, com vistas a manter um equilíbrio razoável de clareza, concisão e rigor ... e, por outro lado, com uma visão para sustentar a comunicação de baixo ruído com outras disciplinas STEM? O último objetivo é especialmente importante, pois os recursos práticos aumentam constantemente em campos como criptografia, testes estatísticos, aprendizado de máquina e simulação quântica.

Seria muito útil (e agradável também) ler respostas bem fundamentadas, afirmativas ou negativas.


A pergunta feita é

Qual é / são os papéis geralmente aceitos de verificação nas definições teóricas da complexidade associadas à amostragem, simulação e teste da tese estendida de Church-Turing (ECT)?

A resposta preferida é a referência a artigos, monografias ou livros didáticos que discutem essas questões em profundidade.

Se essa literatura for escassa ou insatisfatória, então (depois de dois dias) vou converter essa pergunta em um wiki da comunidade, perguntando:

Qual é / são os papéis razoáveis ​​e adequados de verificação nas definições teóricas da complexidade associadas à amostragem, simulação e teste da tese ampliada de Church-Turing (ECT)?

fundo

A pergunta é motivada pelo recente tópico "O que significaria refutar a tese de Church-Turing?" , especificamente as respostas (excelentes IMHO) dadas por Gil Kalai e por Timothy Chow

Na pergunta feita, a frase "definições teóricas da complexidade apropriadas e / ou aceitas" deve ser interpretada como impedindo Alice de afirmações implausíveis como as seguintes:

Alice:   Aqui está minha amostra experimental de dígitos binários verdadeiramente aleatórios calculados pela minha rede óptica linear (de um fóton).

Bob:   Aqui está minha amostra simulada de dígitos pseudo-aleatórios calculados por uma máquina de Turing clássica.

Alice:   Desculpe Bob ... sua amostra é algorítmica compressível e a minha não. Portanto, meus dados experimentais demonstram que a ECT é falsa! "

Na ausência de qualquer associação entre verificação e amostragem, o raciocínio de Alice é impecável. Em outras palavras, os teóricos da complexidade deveriam considerar o ECT como formalmente refutado ... décadas atrás?

Do ponto de vista prático, os métodos de simulação associados à amostragem de trajetória quântica em espaços de estado varietais estão sendo amplamente utilizados em muitas disciplinas da ciência e da engenharia. É por isso que as definições de amostragem teóricas da complexidade que respeitam o papel central da verificação (que é inseparável da replicabilidade) na ciência e na engenharia seriam muito bem-vindas para cientistas e engenheiros praticantes ... especialmente se essas definições fossem acompanhadas por teoremas que descrevem a complexidade computacional da amostragem verificada.


Edição adicionada: graças a uma colaboração entre a Universidade de Genebra e a empresa id Quantique , é perfeitamente viável concluir esse exercício na realidade.

Aqui estão 1024 bits aleatórios que são certificados pelo id Quantique como sendo algoritmicamente incompressíveis:

0110001000010111111100010111001000101110110001001100000010010110
0101000110100011101001110110000001010110011101111110101010110100
1001001110001110101000001110000101000110000001010001101001000000
0110101010110000110101001110011010010101000000110000010000010111
0100110110001011011101110000010110000100110001001110011000000011
1111010100010110110010011000110110110010101101010000010010001111
1101111000111101111010000110100110011000101101010110110110000101
1110111100000111000111101111110011101101110111101001001111111110
1000001011001000011101001000001110101110101010000111100000111010
1010011001110111101001100010110000101101100100101100000110111111
1000001101111001111011100011110101011010010100000010100101100010
0011101000111100000001101100111110100100010100100010011000001000
0000001001110101010111110001010010000111010011000100001101101000
1011111010001000110101110101111101010111111011011111110010010111
0111000010000111000100110110010101110100000110101001111010101001
0100011110011101000011000100110110010000100001111100101001010011 

Devemos agora aceitar a afirmação: "A tese da ECT é refutada"?

Caso contrário, que motivos devemos dar?

John Sidles
fonte
11
por verificação, você quer dizer que a instrução "algoritmo A possui propriedade P em um modelo computacional M" pode ser testada em tempo finito, para qualquer comprimento de entrada específico? Por exemplo, a propriedade "algoritmo probabilístico A para em etapas de em qualquer entrada de tamanho , usando no máximo bits aleatórios e linguagem de acerto com probabilidade " pode ser verificada em tempo finito para qualquer . Verificado em tempo finito significaria uma máquina de Turing determinística como um modelo de computação à prova de falhas? n log 2 n L 2 / 3 n1000nnlog2nL2/3n
Sasho Nikolov
3
Eu acho que essa é uma ótima pergunta. Mas, no seu exemplo, como Alice sabe que sua sequência de dígitos não é algorítmica compressível?
Aaron Sterling
11
Na amostragem equivalência / pesquisar: scottaaronson.com/papers/samprel.ps
Marzio De Biasi
11
@ John: apenas um esclarecimento (sublinho que não sou especialista): " ... são certificados pelo id Quantique como sendo algoritmicamente incompressíveis ", mas como eles podem atestar isso? Obviamente, a complexidade Kolmogorov de uma string não é computável, portanto a sentença parece falsa. Mesmo se eles simplesmente disserem " nós certificamos que a sequência é (quântica) aleatória ", tenho algumas dúvidas: o processo físico (o hardware) é difícil de equilibrar, então eles usam o viesamento de Von Neumann, o que é bom, mas não garante que o O resultado é verdadeiramente aleatório .
Marzio De Biasi
2
@ John Sidles: enquanto você faz observações interessantes e som, eu não entendo o que você está procurando. Está claro o que Aaronson e co-autores entendem por "descartar": se PH é infinito, não existe um algoritmo específico em um modelo específico. Suponho que você esteja perguntando se as suposições de modelagem são verificáveis. nota que o objetivo do modelo é para verificar apenas o pressuposto de modelagem, em vez de teste de qualquer possível algoritmo / teorema
Sasho Nikolov

Respostas:

2

A essência da questão é, dado que a probabilidade quântica é uma fonte de verdadeira aleatoriedade, como isso afeta a tese de Church-Turing prolongada (ou eficiente ou em tempo polinomial)?

A resposta é que, por conjectura, isso não afeta. As pessoas conjeturam que BPP = P, ou seja, que algoritmos aleatórios podem ser des randomizados com geradores de números pseudo-aleatórios com sobrecarga polinomial. A fé nos PRNGs como um substituto para a verdadeira aleatoriedade é uma das razões pelas quais as pessoas acreditariam na tese estendida de Church-Turing, se não fosse na computação quântica.

Greg Kuperberg
fonte