Consequências da

20

Enquanto o teorema de Adleman mostra, que , não conheço nenhuma literatura que investigue a possível inclusão de B Q PP / poli . Que consequências teóricas da complexidade essa inclusão teria?BPPP/polyBQPP/poly

O teorema de Adleman às vezes é chamado de "o progenitor dos argumentos de des randomização". acredita-se ser derandomizable, ao passo que não há nenhuma evidência de que o "quanticidade" de B Q P podia de alguma forma ser removido. Esta é uma possível evidência de que é improvável que B Q P esteja em P / poli ?BPPBQPBQPP/poly

Martin Schwarz
fonte

Respostas:

14

Eu diria que não temos boas razões para pensar que o BQP está em P / poli. Temos motivos para pensar que o BQP não está em P / poli, mas eles são mais ou menos idênticos aos nossos motivos para pensar que BQP ≠ BPP. Por exemplo, se BQP⊂P / poly, o Factoring está em P / poly, o que é suficiente para quebrar muita criptografia de acordo com as definições de segurança padrão.

Além disso, como você aponta corretamente, não há um análogo quântico do truque de Adleman - de fato, não há como "extrair a quantumidade de um algoritmo quântico", análogo ao modo como se pode extrair a aleatoriedade de um algoritmo aleatório. Portanto, não acho que alguém tenha um palpite sobre o que o conselho de P / poli para simular um computador quântico deve consistir (mais do que eles têm um palpite, digamos, no caso de NP vs. P / poli).

Uma observação final: meu trabalho com Alex Arkhipov (e o trabalho independente de Bremner-Jozsa-Shepherd) pode ser facilmente adaptado para mostrar que, se QUANTUM-SAMPLING estiver em P / poly (OK, em "BPP-SAMPLING / poly") , então P #P PBPP NP / poli e, portanto, a hierarquia polinomial entra em colapso - nesse caso, eu acho, para o quarto nível. No momento, porém, não sabemos como adaptar esse tipo de resultado de problemas de amostragem a problemas de decisão.

Scott Aaronson
fonte
2
Muito obrigado por responder, Scott! Uma coisa que me pergunto: quais são os resultados conhecidos que relacionam P ^ # P com níveis de PH / poli? O que realmente se sabe sobre P ^ # P vs. PH / poly? (por exemplo, existe alguma versão não uniforme do teorema de Toda?). Por que P ^ # P em PH / poli entra em colapso PH / poly, se não conhecemos PH / poly em P ^ # P? Ou o que estou perdendo?
Martin Schwarz
1
O que é preciso fazer aqui é generalizar a prova do Teorema de Karp-Lipton. Como primeiro passo, não é difícil mostrar (usando o raciocínio no estilo KL) que se o coNP estiver em NP / poli, o PH entrará em colapso para o terceiro nível. Mas isso deve ser relativizado, para mostrar que se coNP ^ NP ^ NP está em NP ^ NP ^ NP / poli, então PH entra em colapso no quinto nível. E certamente P ^ # P em BPP ^ NP / poly implica coNP ^ NP ^ NP está em NP ^ NP ^ NP / poly. Mas hmm, eu só estou tendo um colapso para o nível aqui! Supondo que isso esteja correto, alguém pode aprimorá-lo para um colapso do quarto nível? (Se não, é o "mais alto" colapso PH que eu já vi :)!)
Scott Aaronson
1
BPPP/polyBPPNP/poly=PNP/polyΣ2P(BP)PNP/polyΣ3P=Π3P
1
S3PZPPNPNPΣ3PΠ3PSP