Folgen von

20

Während Adlemans Theorem zeigt, dass , ist mir keine Literatur bekannt, die den möglichen Einschluss von B Q PP / poly untersucht . Welche komplexitätstheoretischen Konsequenzen hätte eine solche Einbeziehung?BPPP/polyBQPP/poly

Adlemans Theorem wird manchmal als "der Urvater der Derandomisierungsargumente" bezeichnet. wird angenommen , derandomizable zu sein, während es keine Beweise dafür, dass die „Quantenhaftigkeit“ von B Q P irgendwie entfernt werden kann. Ist dies ein möglicher Beweis dafür, dass B Q P wahrscheinlich nicht in P / poly vorliegt ?BPPBQPBQPP/poly

Martin Schwarz
quelle

Antworten:

14

Ich würde sagen, wir haben keinen guten Grund zu der Annahme, dass BQP in P / Poly vorliegt. Wir haben Gründe zu der Annahme, dass BQP nicht in P / Poly vorliegt, aber sie sind mehr oder weniger identisch mit unseren Gründen für die Annahme, dass BQP ≠ BPP ist. Beispiel: Wenn BQP⊂P / poly ist, wird Factoring in P / poly angegeben. Dies reicht aus, um viele Kryptografien gemäß den Standardsicherheitsdefinitionen aufzubrechen.

Außerdem gibt es, wie Sie richtig betonen, kein Quantenanalogon von Adlemans Trick - tatsächlich gibt es keine Möglichkeit, "die Quantität aus einem Quantenalgorithmus herauszuholen", wie man die Zufälligkeit aus einem randomisierten Algorithmus herausziehen kann. Daher glaube ich nicht, dass jemand eine Vermutung hat, woraus der P / Poly-Rat für die Simulation eines Quantencomputers bestehen sollte (genauso wenig, wie er beispielsweise im Fall von NP gegen P / Poly vermutet).

Eine letzte Anmerkung: Meine Arbeit mit Alex Arkhipov (und die unabhängige Arbeit von Bremner-Jozsa-Shepherd) kann leicht angepasst werden, um zu zeigen, dass wenn QUANTUM-SAMPLING in P / poly ist (OK, in "BPP-SAMPLING / poly") , dann P #P ⊂ BPP NP / poly, und daher kollabiert die Polynomhierarchie - in diesem Fall denke ich auf die vierte Ebene. Gegenwärtig wissen wir jedoch nicht, wie wir solche Ergebnisse von Stichprobenproblemen an Entscheidungsprobleme anpassen können.

Scott Aaronson
quelle
2
Vielen Dank für die Antwort, Scott! Eines wundere ich mich: Was sind die bekannten Ergebnisse, die P ^ # P mit PH / Poly-Werten in Verbindung bringen? Was ist eigentlich über P ^ # P vs. PH / poly bekannt? (zB gibt es eine uneinheitliche Version von Todas Theorem?) Warum würde P ^ # P in PH / poly PH / poly kollabieren, wenn wir PH / poly in P ^ # P nicht kennen? Oder was fehle ich?
Martin Schwarz
1
Hier muss man den Beweis des Karp-Lipton-Theorems verallgemeinern. In einem ersten Schritt ist es nicht schwer zu zeigen (unter Verwendung der KL-artigen Argumentation), dass, wenn coNP in NP / Poly vorliegt, PH auf die 3. Ebene zusammenbricht. Aber dann sollte sich das relativieren, um zu zeigen, dass, wenn coNP ^ NP ^ NP in NP ^ NP ^ NP / poly ist, PH auf die 5. Ebene zusammenbricht. Und sicherlich impliziert P ^ # P in BPP ^ NP / poly, dass coNP ^ NP ^ NP in NP ^ NP ^ NP / poly ist. Aber hmm, ich bekomme hier nur einen Zusammenbruch bis zum 5. Level! Unter der Annahme, dass dies korrekt ist, kann jemand es zu einem Zusammenbruch der 4. Ebene verbessern? (Wenn nicht, ist es der "höchste" PH-Zusammenbruch, den ich je gesehen habe! :))
Scott Aaronson
1
3rd Level wird genügen. Sowohl und Karp-Lipton relativieren so erster B P P N P / p o l y = P N P / p o l y , und zweitens, wenn Σ P 2( B P ) P N P / p o l y , dann Σ P 3 = Π PBPPP/polyBPPNP/poly=PNP/polyΣ2P(BP)PNP/poly . Σ3P=Π3P
Emil Jeřábek unterstützt Monica
1
(Und verschiedene bekannte Festigungen von KL auch Relativieren was das betrifft, insbesondere die Annahme oben kollabiert tatsächlich PH , außer ich habe noch nie gesehen S P mit einem anderen Index als 2, daher ist es wahrscheinlich keine Standardnotation.)S3PZPPNPNPΣ3PΠ3PSP
Emil Jeřábek unterstützt Monica