NP von BQP relativ zu einem Orakel trennen

10

Ich habe mir diese Vorlesungsnotiz angesehen, in der der Autor eine Orakeltrennung zwischen BQP und NP . Er weist darauf hin, wie "Standarddiagonalisierungstechniken verwendet werden können, um dies rigoros zu machen".

BQPANPABQPA

BlackHat18
quelle

Antworten:

2

Es scheint mir , dass die Diagonalisierung Argumente , die nur geringfügig von einer Standard - eins sind verwendet werden können, zB  wie in diesen fand Skriptum über den Baker-Gill-Solovay Satz ( dh , dass es Orakel , für die und auch Orakel für die ). Grundsätzlich muss man beschreiben, wie man eine gegnerische Eingabe etwas anders „konstruiert“.APA=NPAAPANPA

Hier , wie wir diesen Ansatz verwenden können, um die Existenz eines Orakels zu beweisen, für das . Definieren Sie für jedes Orakel eine Sprache Es ist klar, dass aus dem einfachen Grund, dass eine nichtdeterministische Turing-Maschine prüfen kann, ob die Eingabe für einige die Form , und dann eine Zeichenfolge erraten kann für die wenn ein solches existiert. Das Ziel ist es zu zeigen, dassANPABQPAA

LA={1n|z{0,1}n:A(z,0)=(z,1)}.
LANPA1nnz{0,1}nA(z,0)=(z,1)zLAkann nicht in Polynomzeit mit begrenztem Fehler durch eine einheitliche Einheitsschaltungsfamilie unter Verwendung der Untergrenze für das Suchproblem entschieden werden.O(2n/2)

  1. Sei so, dass das Suchproblem bei Orakeln mit Bit-Eingaben mindestens Orakelabfragen erfordert , um für alle richtig (mit einer Wahrscheinlichkeit von mindestens 2/3) zu entscheiden .c,N>0nc2n/2n>N

  2. Sei,, ist eine Aufzählung aller einheitlichen Orakelschaltungsfamilien , so dass die Gate-Sequenz der SchaltungEinwirken auf Bit-Eingänge kann in einer Zeit erzeugt werden, die streng unter . (Diese Zeitgrenze bezieht sich auf die 'Gleichförmigkeits'-Bedingung, bei der wir an Schaltungen interessiert sein werden, die von einer deterministischen Turing-Maschine in Polynomzeit berechnet werden können - eine stärkere Bedingung, als wir hier auferlegen. Die Aufzählung dieser Schaltungsfamilien könnte z zum Beispiel durch indirekte Darstellung durch die deterministischen Turing-MaschinenC(1)C(2)C(k)={Cn(k)}n0Cn(k)nc2n/2T(k) , die ihre Gate - Sequenzen erzeugen, und Aufzählen diejenigen .) Wir aufzuzählen , die Schaltungsfamilien , so daß jede Schaltungsfamilie in der Aufzählung unendlich oft auftritt.

    • Aus den Laufzeitgrenzen der Beschreibung der Gate-Sequenz folgt insbesondere, dass für alle weniger als Gates hat und insbesondere weniger als ergibt Anfragen an das Orakel.Cn(k)c2n/2kc2n/2

    • Betrachten Sie für jedes die Schaltung. Aus der unteren Grenze des Suchproblems wissen wir, dass es für mögliche Werte der Orakelfunktion die vom Orakel ausgewertet werden, wie z dass mit einer Wahrscheinlichkeit von 2/3 die vonbei Eingabe ist nicht die richtige Antwort darauf, ob .nCn(n)n>Nf:{0,1}n{0,1}Cn(n)1nz{0,1}n:f(z)=1

    • für jedes eine solche Funktion für die auf diese Weise "fehlschlägt".n>NfnCn(n)

  3. Lasse sein ein Orakel , die, an den Eingängen der Größe , auswertet .An>Nfn

Nachdem auf diese Weise konstruiert wurde, kann jede Schaltungsfamilie mit einer Wahrscheinlichkeit von mindestens 2/3 für einige (und tatsächlich unendlich viele solcher nicht richtig entscheiden . Dann entscheidet keine der Schaltungsfamilien korrekt mit einer Erfolgswahrscheinlichkeit, die unten durch 2/3 an allen Eingaben begrenzt ist, so dass nicht mit solchen Grenzen durch eine einheitliche einheitliche Schaltungsfamilie gelöst werden kann, die in der Zeit konstruierbar ist .AC(n)LAn>NnC(k)LALAp(n)

Somit , woraus folgt, dass .LABQPANPABQPA

Niel de Beaudrap
quelle