Conséquences de ?

20

Alors que le théorème d'Adleman montre que , je ne connais aucune littérature qui étudie l'inclusion possible de . Quelles seraient les conséquences théoriques de la complexité d'une telle inclusion?BPPP/polyBQPP/poly

Le théorème d'Adleman est parfois appelé «l'ancêtre des arguments de dérandomisation». On pense que est dérandomisable, alors qu'il n'y a aucune preuve que la "quanticité" de pourrait être en quelque sorte supprimée. Est-ce une preuve possible que est peu susceptible d'être dans ?BPPBQPBQPP/poly

Martin Schwarz
la source

Réponses:

14

Je dirais que nous n'avons aucune bonne raison de penser que BQP est en P / poly. Nous avons des raisons de penser que BQP n'est pas en P / poly, mais ils sont plus ou moins identiques à nos raisons de penser que BQP ≠ BPP. Par exemple, si BQP⊂P / poly alors l'affacturage est en P / poly, ce qui est suffisant pour casser beaucoup de cryptographie selon les définitions de sécurité standard.

En outre, comme vous le faites remarquer correctement, il n'y a pas d'analogue quantique de l'astuce d'Adleman --- en effet, il n'y a aucun moyen de "retirer la quanticité d'un algorithme quantique", analogue à la façon dont on peut extraire le caractère aléatoire d'un algorithme randomisé. Donc, je ne pense pas que quiconque ait une idée de ce que les conseils P / poly pour simuler un ordinateur quantique devraient même consister (pas plus qu'ils n'ont une supposition, disons, dans le cas de NP vs P / poly).

Une dernière note: mon travail avec Alex Arkhipov (et le travail indépendant de Bremner-Jozsa-Shepherd), peut facilement être adapté pour montrer que si QUANTUM-SAMPLING est en P / poly (OK, en "BPP-SAMPLING / poly") , alors P #P ⊂BPP NP / poly, et donc la hiérarchie polynomiale s'effondre --- dans ce cas, je pense, au quatrième niveau. À l'heure actuelle, cependant, nous ne savons pas comment adapter ce type de résultat de problèmes d'échantillonnage à des problèmes de décision.

Scott Aaronson
la source
2
Merci beaucoup d'avoir répondu, Scott! Je me demande une chose: quels sont les résultats connus concernant P ^ # P avec les niveaux de PH / poly? Que sait-on réellement de P ^ # P par rapport à PH / poly? (par exemple, existe-t-il une version non uniforme du théorème de Toda?). Pourquoi P ^ # P dans PH / poly effondrerait-il PH / poly, si nous ne connaissons pas PH / poly dans P ^ # P? Ou qu'est-ce qui me manque?
Martin Schwarz
1
Ce qu'il faut faire ici, c'est généraliser la preuve du théorème de Karp-Lipton. Dans un premier temps, il n'est pas difficile de montrer (en utilisant un raisonnement de type KL) que si coNP est en NP / poly, alors PH s'effondre au 3ème niveau. Mais alors cela devrait relativiser, pour montrer que si coNP ^ NP ^ NP est dans NP ^ NP ^ NP / poly, alors PH s'effondre au 5ème niveau. Et certainement P ^ # P dans BPP ^ NP / poly implique que coNP ^ NP ^ NP est dans NP ^ NP ^ NP / poly. Mais hmm, je ne fais qu'effondrer au 5ème niveau ici! En supposant que cela soit correct, quelqu'un peut-il l'améliorer en un effondrement de 4e niveau? (Si ce n'est pas le cas, c'est l'effondrement du pH le "plus élevé" que j'ai jamais vu! :))
Scott Aaronson
1
Le 3ème niveau fera l'affaire. Les deux et Karp-Lipton relativiser, donc d' abord , et deuxièmement, si , alors . BPPP/polyBPPNP/poly=PNP/polyΣ2P(BP)PNP/polyΣ3P=Π3P
Emil Jeřábek soutient Monica
1
(Et divers renforcements connus de KL relativisent également d'ailleurs, en particulier l'hypothèse ci-dessus réduit en fait PH à , sauf que je n'ai jamais vu avec un indice autre que 2, donc c'est probablement une notation non standard.) S PS3PZPPNPNPΣ3PΠ3PSP
Emil Jeřábek soutient Monica