NP von BQP relativ zu einem Orakel trennen

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

$\mathsf{BQP}$$A$$\mathsf{NP}^{A} \not\subseteq \mathsf{BQP}^{A}$

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“.$A$$\mathsf P^A = \mathsf{NP}^A$$A$$\mathsf P^A \ne \mathsf{NP}^A$

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, dass$A$$\mathsf{NP}^A \not\subseteq \mathsf{BQP}^A$$A$

$$L_A = \Bigl\{ 1^n \;\Big\vert\; \exists z \in \{0,1\}^n : A(z,0) = (z,1)\Bigr\} .$$ $L_A \in \mathsf{NP}^A$$1^n$$n$$z \in \{0,1\}^n$$A(z,0) = (z,1)$$z$$L_A$kann nicht in Polynomzeit mit begrenztem Fehler durch eine einheitliche Einheitsschaltungsfamilie unter Verwendung der Untergrenze für das Suchproblem entschieden werden.$O(2^{n/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 > 0$$n$$c 2^{n/2}$$n > 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-Maschinen$\mathbf C^{(1)}\!$$\mathbf C^{(2)}\!$$\ldots$$\mathbf C^{(k)} \!= \{ C^{(k)}_n \}_{n \geqslant 0 }$$C^{(k)}_n\!$$n$$c 2^{n/2}$$\mathbf T^{(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.$C^{(k)}_n$$c 2^{n/2}$$k$$c 2^{n/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 .$n$$C^{(n)}_n\!$$n > N$$f: \{0,1\}^n \to \{0,1\}$$C^{(n)}_n\!$$1^n$$\exists z \!\in\! \{0,1\}^n\!:\! f(z) \!=\! 1$

   • für jedes eine solche Funktion für die auf diese Weise "fehlschlägt".$n > N$$f_n$$C^{(n)}_n$
     
     

3. Lasse sein ein Orakel , die, an den Eingängen der Größe , auswertet .$A$$n > N$$f_{\!\!\:n\!\:}$

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 .$A$$\mathbf C^{(n)}$$L_A$$n > N$$n$$\mathbf C^{(k)}$$L_A$$L_A$$p(n)$

Somit , woraus folgt, dass .$L_A \notin \mathsf{BQP}^A$$\mathsf{NP}^A \not\subseteq \mathsf{BQP}^A$