Interaktive Proofs per Nachauswahl?

Definieren Sie das Rechenmodell MPostBQP so, dass es mit PostBQP identisch ist, außer dass wir vor der Nachauswahl und der endgültigen Messung polynomiell viele Qubit-Messungen zulassen.

Können wir Hinweise darauf geben, dass MPostBQP leistungsfähiger als PostBQP ist?

Definieren Sie MPostBQP [k], um mehrere Mess- und Nachauswahlrunden zu ermöglichen, bevor wir die endgültige Messung durchführen. Wählen Sie die Indizierung so, dass MPostBQP [1] = PostBQP und MPostBQP [2] = MPostBQP usw. (Update: Eine formale Definition ist unten angegeben.)

Betrachten Sie Arthur-Merlin-Spiele. Vielleicht können wir sie in diesem Berechnungsmodell simulieren: Die Nachauswahl kann Merlins Rolle bei der Erstellung überzeugender Botschaften übernehmen, und die Zwischenmessungen können die Rolle von Arthurs öffentlichen Münzwürfen übernehmen. Diese Möglichkeit lässt mich fragen:

Haben wir AM [k] $\subset$ MPostBQP [k]?

Dies ist in der Tat für $k=1$ , was MA $\subset$ PP sagt . Es für zu zeigen, $k=2$ würde MPostBQP = PP nur bedeuten, wenn AM $\subset$ PP ist. Da es ein Orakel gibt, zu dem AM nicht in PP enthalten ist , könnte dies eine positive Antwort auf meine erste Frage geben.

Schließlich für den polynomiell vielen Rundenfall,

Haben wir PSPACE MPostBQP [poly]? Wenn ja, ist es Gleichheit? $\subset$

Dies wäre philosophisch interessant (zumindest für mich), da es uns sagen würde, dass die "nachvollziehbare" Klasse von Problemen für einen "nachselektierenden Zauberer" das gesamte PSPACE umfasst (oder ist ).

EDIT: Ich wurde nach einer formalen Definition von MPostBQP gefragt. (Ich habe Folgendes aktualisiert.)

MPostBQP [k] ist die Klasse der Sprachen für die es eine einheitliche Familie von Quantenschaltungen mit Polynomgröße so dass für alle Eingaben die folgende Prozedur wahr ist mit mindestens Wahrscheinlichkeit , wenn , und mit einer Wahrscheinlichkeit von höchstens , wenn . Die Prozedur, die einige Auswahlmöglichkeiten zulässt, die von abhängen können (aber nicht von $L \subset \{0,1\}^*$ $\{C_n\}_{n \geq 1}$ $x$ $2/3$ $x \in L$ $1/3$ $x \notin L$ $L$ $x$ ) ist wie folgt definiert:

Vorgehensweise: Schritt 1. Wenden Sie den entsprechenden Einheitsoperator auf den Eingabezustand . Beachten Sie die Länge des ersten Register sind höchstens Polynom in der Länge . Schritt 2. Wenn ungerade ist, wählen Sie nach, so dass ein ausgewähltes einzelnes Qubit im ersten Register als misst $C_n$ $\left\vert 0\cdots 0\right> \otimes \left\vert x \right>$ $\left\vert0\cdots 0\right>$ $x$ : Wenn ist, messen Sie eine beliebige Anzahl von Qubits aus dem ersten Register (höchstens polynomiell viele, angesichts der Größe des Registers). Wenn $i = 1 \cdots k$ $i$ $i$ $\left\vert 0 \right>$ (und eine Garantie haben , dass die Wahrscheinlichkeit ungleich Null ist, so dass die postselection gültig ist, natürlich). Schritt 3. Messen Sie abschließend ein letztes Qubit im ersten Register und geben Sie true zurück, wenn wir messen und andernfalls false. $\left \vert 1 \right>$

Wir haben MPostBQP [0] = BQP, MPostBQP [1] = PostBQP und MPostBQP: = MPostBQP [2]. Ich versuche, die Arthur-Merlin-Klassen zu spiegeln, in denen AM [0] = BPP, AM [1] = MA und AM [2] = AM.

EDIT (27.03.11, 17 Uhr): Es scheint eine Debatte darüber zu geben, wie die Nachauswahl in diesem Zusammenhang definiert werden sollte. Natürlich meine ich eine Definition, die meine Frage nicht trivialisiert! :) Die Definition, die ich angenommen habe, lautet wie folgt: Nachauswahl auf dem k-ten Bit bedeutet, dass wir den Zustand in den Unterraum projizieren, in dem das k-te Bit $0$ und normalisieren. Es stellt sich heraus, dass wir in einem Schema, in dem wir vor der Durchführung von Messungen eine Nachauswahl treffen, die endgültige Statistik erhalten können, indem wir die bedingten Wahrscheinlichkeiten in einem Schema betrachten, in dem die Nachauswahl durch Messungen ersetzt wird. Ich behaupte jedoch, dass diese Charakterisierung zusammenbricht, wenn Messungen und Nachauswahl eingestreut werden. Ich denke, die Verwirrung rührt von Leuten her, die diese "bedingte Wahrscheinlichkeitsdefinition" (die in dem Sonderfall, aus dem ich verallgemeinere, funktioniert) als Definition der Nachauswahl verwenden und nicht die Definition der "erzwungenen Messung", die ich gerade gegeben habe und die eindeutig davon abhängt Ordnung wegen mangelnder Kommutativität. Ich hoffe das hilft!

EDIT (27.03.11 21 Uhr): Ich habe die Nachauswahl bereits im reinen Staatsformalismus definiert. Niel gab eine Analyse im Dichtematrix-Formalismus, die mit meiner für das 3-Qubit-Beispiel nicht übereinstimmt. Der Schuldige ist wiederum die Definition der Nachauswahl. Definieren Sie die Nachauswahl in der Dichtematrixeinstellung wie folgt. Schreiben Sie eine gegebene Dichtematrix als eine Mischung trennbarer Zustände . Lassen Sie $M$ $M = \sum p_i \left\vert a_i \right> \left< a_i \right\vert$ das Ergebnis postselection sein (bei einigen Qubit)den reinen Zustand Formalismus I oben definiert. Definieren Sie das Ergebnis der Nachauswahl aufals $\left\vert A_i \right>$ $M$ . $\sum p_i \left\vert A_i \right> \left< A_i \right\vert$

Dies ist eine sinnvollere Definition, da sie keine Ergebnisse liefert, die besagen, dass wir nach der Nachauswahl die Statistik der Ereignisse (Messungen) ändern, die wir bereits beobachtet haben. Das heißt, die sind Wahrscheinlichkeiten von Münzen, die wir "bereits geworfen" haben. Es macht für mich keinen Sinn zu sagen, dass wir in der Zeit zurückgehen und einen Münzwurf voreingenommen machen werden, der bereits stattgefunden hat, weil dies die aktuelle Nachauswahl wahrscheinlicher machen würde. $p_i$

EDIT (28.03.11, 13 Uhr): Niel räumt ein, dass das Problem mit meinen Definitionen Sinn macht und nicht trivialisiert - aber mit der Bedingung, dass ich es nicht nennen sollte Nachwahl sollte . Angesichts der Verwirrung muss ich ihm zustimmen. Nennen wir das, was ich definiert habe, Auswahl , die eine "erzwungene Messung" durchführt. Ich sollte wahrscheinlich auch den Namen der von mir definierten Komplexitätsklassen ändern (um nicht "Post" zu haben), also nennen wir sie QMS [k] (Quantum-Measure-Select).

cc.complexity-theory complexity-classes quantum-computing interactive-proofs Shaun Harker
quelle

Können Sie MPostBQP formeller definieren? Wenn Sie nur meinen, dass diese Klasse die Möglichkeit hat, basierend auf dem Ergebnis mehrerer Bits eine Nachauswahl zu treffen, sollte diese Klasse in PostBQP enthalten sein.

Robin Kothari

Die Schlüsselidee besteht nicht darin, viele Bits gleichzeitig nachzusuchen, da dies, wie Robin betont, nicht hilft. Es dient dazu , Messungen und Nachselektionen zu verteilen. Wir können diese nicht pendeln; Die Reihenfolge ist wichtig. Zum Beispiel würde es in PostBQP nicht funktionieren, die Antwort zu messen und dann nachzuwählen.

Shaun Harker

Siehe den Kommentar zu Niels Antwort; Wir können sowohl Messungen als auch Nachselektionen bis nach der Quantenentwicklung verschieben. Das mache ich schon ! Das gleiche Argument scheint jedoch auch die Nachauswahl nach den Messungen nicht neu zu ordnen, da die Messungen nicht einheitlich sind. Insbesondere sage ich, dass die Messungen und Nachauswahl nicht einheitliche Operationen auf dem Quantenzustand sind, die nicht pendeln, soweit ich das beurteilen kann, können wir nicht alle Nachauswahl bis nach allen Messungen ohne Verlust verschieben.

Shaun Harker

@Shaun Harker: Die Tatsache, dass die Messungen und Nachauswahl nicht einheitlich sind, gibt uns keine weiteren Informationen darüber, ob sie pendeln werden. Vielleicht könnten Sie herausfinden, warum Sie denken, dass sie nicht pendeln?

Niel de Beaudrap

Wegen der Verstrickung. Hier ist ein Beispiel. Bereiten Sie den Zustand

. Wählen Sie

. Wenn wir zuerst das erste Qubit messen und dann das dritte Qubit erneut auswählen und dann das zweite Qubit für unser Ergebnis messen, erhalten wirmit gleicher Wahrscheinlichkeit

oder

. Wenn wir zuerst das dritte Qubit nachwählen, dann das erste Qubit messen und schließlich das zweite Qubit für unser Ergebnis messen, erhalten wir

seltener als

α | 000 ⟩ + \sqrt{1 / 2 - α^{2}} | 011 ⟩ + \sqrt{1 / 2 - β^{2}} | 101 ⟩ + β | 110 ⟩

$\alpha\left\vert 000 \right> + \sqrt{1/2 - \alpha^2} \left\vert 011 \right> + \sqrt{1/2 - \beta^2} \left\vert 101 \right> + \beta\left\vert 110 \right>$

0 < α < β < 1

$0 < \alpha < \beta < 1$

0

$0$

1

$1$

0

$0$

1

$1$

Shaun Harker

Antworten:

Aus den Kommentaren geht hervor, dass Shaun etwas anderes im Sinn hat als das, was normalerweise unter Nachauswahl verstanden wird. Ich verstehe dies jetzt so, dass die Statistiken für Messungen, die vor einer bestimmten Nachauswahl durchgeführt wurden, durch die nachfolgende Nachauswahl nicht geändert werden sollten. Dies ist vergleichbar mit einem Projektionsoperator, bei dem die Normalisierung über jeden Zweig der Wellenfunktion durchgeführt wird, der einem bestimmten Messergebnis entspricht, und nicht über die Wellenfunktion als Ganzes.

In diesem Fall gelten die Argumente, die ich und Neil in anderen Antworten gegeben haben, nicht mehr. In der Tat ist leicht zu erkennen, dass MPostBQP [k] ist, da MPostBQP als BQP-Maschine angesehen werden kann, die Abfragen an ein PP-Orakel und damit $P^{PP[k]}\subseteq$ $[k]$ $k$ $P^{\# P}\subseteq$ MPostBQP stellen kann .

Jetzt haben wir also eine nicht triviale Untergrenze. Was ist mit einer Obergrenze? Das Problem liegt eindeutig in PSPACE , aber können wir es besser machen? Eigentlich denke ich können wir.

Wir können jede Berechnung in MPostBQP als eine Folge von Schichten der Form schreiben : Quantenberechnung, gefolgt von einer Nachauswahl, gefolgt von einer einzelnen Qubit-Messung. In der Tat könnte dies eine alternative Methode sein, um MPostBQP [k] als eine Berechnung zu formulieren , die aus solchen Schichten besteht (dies unterscheidet sich geringfügig von Shauns Definition, von der ich glaube, dass sie nur die Anzahl der Nachselektionen zählen soll), gefolgt von a letzte Schicht der klassischen Nachbearbeitung. Ich werde diese Definition von MPostBQP [k] im Folgenden verwenden, da sie zu einem ästhetischeren Ergebnis führt. $k$

Das Folgende wurde von der Originalversion aktualisiert, um ein Loch im Proof zu reparieren.

Zuerst möchten wir das Ergebnis der Messung des ersten gemessenen Qubits berechnen (nicht nachgewählt!). Dazu stellen wir zunächst fest, dass jede Quantenberechnung nur mit Hadamard-Gattern und Toffoli-Gattern und der Amplitude eines bestimmten rechnerischen Basiszustands ausgedrückt werden kann in der Ausgabe kann als die Summe von höchstens geschrieben werden Begriffe , wobei die Gesamtzahl der Hadamard - Gattern, von denen jede entspricht einem eindeutigen computational Pfad. Es ist klar, dass $\alpha_w$ $|w\rangle$ $2^{H}$ $a_{j,w}$ $H$ $a_{j,w} = \pm 2^{-H/2}$ . Die Wahrscheinlichkeit für einen Endzustand zu erhalten wird dann gegeben durch . Wir möchten die Gesamtwahrscheinlichkeit der Messung einer 1 berechnen. Sei die Menge der Berechnungsgrundzustände, die die Nachauswahlkriterien erfüllen (dh das Nachauswahl-Qubit ist 1) und ergeben 0 für das gemessene Qubit, und sei $|w\rangle$ $\alpha_w^2 = (\sum_j a_{j,w})^2 = \sum_{i,j} a_{j,w}a_{i,w}$ $S_0$ $S_1$ sei die Menge der rechnerischen Basiszustände, die die Nachauswahlkriterien erfüllen und für das gemessene Qubit 1 ergeben. Wir können und

π_{0}^{\pm} = \sum w \in S_{0} \pm \sum_{s i g n (a_{j, w} a_{i, w}) = \pm} a_{j, w} a_{i, w}

$\pi_0^\pm = \sum{w \in S_0} \pm \sum_{sign(a_{j,w}a_{i,w}) = \pm} a_{j,w}a_{i,w}$

π_{1}^{\pm} = \pm \sum_{w \in S_{1}} \sum_{s i g n (a_{j, w} a_{i, w}) = \pm} a_{j, w} a_{i, w} .

$\pi_1^\pm = \pm \sum_{w \in S_1} \sum_{sign(a_{j,w}a_{i,w}) = \pm} a_{j,w}a_{i,w}.$

Die in diesem Fall die Wahrscheinlichkeit der Messung einer 1, die von einer 1 abhängig ist, für das nachgewählte Qubit ist gegeben durch . Wie wir dies mit 4 Aufrufen eines # P-Orakels feststellen können. Wir verwenden dies, um ein zufälliges Bitzu erzeugen,das mit der Wahrscheinlichkeit, genau wie die Quantenmessung. Somit istMPostBQP[1] in $\frac{\pi_1^+ - \pi_1^-}{\pi_1^+ - \pi_1^- - \pi_0^- + \pi_0^+}$ $b_1$ $X_1$ $BPP^{\# P[4]}$ .

Als nächstes berechnen wir das Messergebnis des zweiten Qubits. Um dies zu tun, führen wir die gleichen #P Abfragen wie für die erste Schicht, jedoch auf der Schaltung , die durch die ersten beiden Schichten zu komponieren, und wo wir nachträglich auszuwählen auf 1 für jede der Post ausgewählt Qubits, sondern auch auf für Die Ausgabe von Messung 1. Beachten Sie, dass dies zwar eine Nachauswahl für die Zustände von 3 Qubits anstelle von 1 ist, dies jedoch eine triviale Modifikation der Abfragen ist, indem einfach eine Ancilla hinzugefügt wird, die nur festgelegt wird, wenn alle 3 Qubits die erforderlichen Bedingungen erfüllen und stattdessen nachträglich auf dieser Ancilla auswählen. Dies erzeugt dann die korrekten bedingten Ausgabewahrscheinlichkeiten für das Ergebnis des zweiten gemessenen Qubits, das wir als $b_1$ $\# P$ $b_2$ . Beachten Sie, dass wir jetzt 8 Aufrufe an das # P- Orakel verwendet haben.

Wir wiederholen diesen Prozess iterativ, so dass bei einer Schicht wir auf 1 für alle nachträglich auszuwählen die vorhergehenden post ausgewählt Qubits und für alle vorherigen Messung und beschriften Sie das Ergebnis der entsprechenden Maschine . Insgesamt waren dafür erforderlich . $j$ $j$ $b_{i<j}$ $P^{\# P}$ $b_j$ $4j$

Wir haben also MPostBQP [k] , was zusammen mit dem vorherigen Ergebnis, dassMPostBQP, impliziert, dassMPostBQP[k] und damitMPostBQP . $\subseteq P^{\# P[4k]}$ $P^{PP[k]}\subseteq$ $[k]$ $P^{PP[k]} \subseteq$ $\subseteq BPP^{\# P[4k]}$ $= P^{\# P}$

Joe Fitzsimons
quelle

[Überarbeitet.] Ich habe meine Antwort basierend auf Ihren Überarbeitungen Ihrer Frage Ich habe den Inhalt meiner ursprünglichen Antwort beibehalten, sie jedoch kürzer gemacht. Die ausführlichere Beschreibung des "Simulations" -Prozesses wurde ersetzt, aber ich nehme an, dass sie anhand des Bearbeitungsverlaufs dieses Beitrags angezeigt werden kann.

Die meisten Menschen werden "Nachauswahl" im Sinne einer bedingten Wahrscheinlichkeit verstehen. In der aktuellen Version des Wikipedia-Artikels über PostBQP wird dies tatsächlich so beschrieben. und als eine Operation auf Dichteoperatoren angesehen (bei der eine vollständig positive, nicht ansteigende Spur Φ angewendet wird, so dass Φ ² = Φ ist, und dann die Spur renormiert), stellt man diese Definition wieder her.

Angesichts dieser Definition der Nachauswahl kann Ihre Definition eines MPostBQP [ k ] -Algorithmus durch einen PostBQP- Algorithmus simuliert werden, indem die Nachauswahl verschoben und gleichzeitig in geeigneter Weise ausgeführt wird. Dies wird mehr oder weniger explizit auf Seite 3 von Aaronsons Artikel Quantum Computing, Postselection und Probabilistic Polynomial-Time erwähnt, in dem die Klasse PostBQP vorgestellt wird .

Dies kann explizit gezeigt werden, indem angemerkt wird, dass es für eine Folge von Bits P ₁ , P ₂ , ..., die nachgewählt werden sollen ( z. B. in dem 1Zustand, der üblich ist), keinen Unterschied zwischen der Konditionierung auf ihnen 1in der Mitte von gibt Die Berechnung und Konditionierung erfolgt am 1Ende der Berechnung, solange die Werte dieser Bits in der Zwischenzeit nicht geändert werden. Anstatt jedes einzelne Wesen nachträglich auszuwählen 1, können wir ihr logisches UND vor der nachträglichen Auswahl berechnen und dann dieses Konjunktionswesen nachträglich auswählen1. Darüber hinaus kann die Berechnung des UND an jedem Punkt zwischen der letzten Transformation des Bits und seiner Nachauswahl durchgeführt werden. Dies hat keinerlei Auswirkungen auf die gemeinsame Statistik der Eigenschaften des Staates.

Unter Verwendung der gemeinsamen Definition der Nachauswahl in Bezug auf bedingte Wahrscheinlichkeiten hätten wir also MPostBQP [ k ] = PostBQP für alle k > 0.

Wie ich in den obigen Kommentaren bemerkt habe, denke ich nicht, dass die Operation, die Sie beschreiben, den Zustand betrifft Vektoren - insbesondere die unabhängige Renormierung von Zustandsvektoren in jedem Zweig der Wahrscheinlichkeitsverteilung über die Messergebnisse- entspricht der Nachauswahl, da viele Fachleute (epsecially experimentists) das Konzept beschreiben würden. Es kann sogar zu einigen "unphysischen" Eigenschaften führen, wenn es auf eine Abbildung auf Dichteoperatoren erweitert wird. Es ist jedoch ein mögliches Mittel, um so etwas wie Entscheidungsbäume zu konstruieren, deren Knoten durch Zustandsvektoren gekennzeichnet sind, und daher ist es im Prinzip ein vernünftiger eigenständiger Studienprozess. Ich würde diesen Prozess einfach nicht als "Nachauswahl" bezeichnen.

[Bearbeiten.] Aus Gründen der Ordnung habe ich das berechnete Beispiel entfernt. Ich nehme an, dass es durch Anzeigen des Bearbeitungsverlaufs dieses Beitrags gesehen werden kann.

Niel de Beaudrap
quelle

Das Argument erscheint unvollständig. Der Kommentar in Aaronsons Artikel weist darauf hin, dass wir keine Macht gewinnen, wenn wir Nachselektionen mit den einheitlichen Entwicklungen durchsetzen, so wie es nicht hilft, Messungen mit einheitlichen Entwicklungen zu vermischen. Aber ich mache beides nicht; Ich mische Nachauswahl und Messung ein. Um meine Frage auf diese Weise zu verneinen, müsste nachgewiesen werden, dass wir die Nachauswahl nach den Messungen jederzeit ohne Leistungsverlust bestellen können. (Für mich überhaupt nicht offensichtlich.) Der Rest der Antwort erklärt nur, warum ich die Klasse so definiert habe, dass in jeder Runde nur ein Bit nachgewählt wird.

Shaun Harker

@Shaun Harker: Unabhängig davon, ob Aaronsons Artikel Ihre Frage beantwortet, sollte meine obige Antwort. Der Effekt der Nachauswahl besteht im Wesentlichen darin, dass Messungen eher bedingte Wahrscheinlichkeiten als "nicht bedingte" Wahrscheinlichkeiten realisieren können. Die Nachauswahl der Bits

im Wesentlichen der Auswahl für Konjunktionen von Bedingungen für bedingte Wahrscheinlichkeiten. Diese bedingten Wahrscheinlichkeiten auf den Bits

nicht ändern, nur durch die Auswertung von aufzuschieben , ob die Bedingung erfüllt ist , solange die Bits

unbehelligt gelassen.

C_{j}

$C_j$

C_{j}

$C_j$

C_{j}

$C_j$

Niel de Beaudrap

Es scheint, dass Sie argumentieren, dass wir die gleichen Statistiken erhalten, wenn wir die Nachauswahl und Messungen neu anordnen. Wenn wir jedoch einige Bits vor einer Nachauswahl messen, messen wir aus einer anderen Verteilung , als wenn wir dieselben Bits nach der Nachauswahl messen würden. Die Statistiken sind also nicht die gleichen.

Shaun Harker

Zum Sammeln von Statistiken kann eine Nachauswahl physisch (wenn auch ineffizient) implementiert werden, indem Versuche einfach abgelehnt werden, bei denen die gewünschte Nachbedingung nicht zutrifft. Der Status, ob eine Nachbedingung gilt ( z. B. "dieses einzelne Bit befindet sich im Zustand | 1⟩" oder "diese fünf Bits befinden sich alle im Zustand | 1⟩"), wird von der Messreihenfolge nicht beeinflusst, solange dies nicht der Fall ist angewendet, um Bits zu ändern, die die Ergebnisse speichern. Da die Tatsache, ob ein Versuch abgelehnt wird oder nicht, unabhängig von der Messreihenfolge in PostBQP ist , können wir die Nachauswahl bis zum Ende verschieben.

Niel de Beaudrap

Diese Charakterisierung der Nachauswahl gilt nur, wenn wir die Nachauswahl vor den Messungen durchführen. Das Drei-Qubit-Beispiel, das ich gegeben habe, hat dies bereits gezeigt. Wenn ich mich irre, antworten Sie bitte, indem Sie dieses Beispiel direkt widerlegen, das je nach Reihenfolge der Messungen und Nachauswahl unterschiedliche Statistiken liefert.

Shaun Harker

Aus Ihrer Definition von MPostBQP geht hervor , dass dies einfach PostBQP in Kostümen ist . Anstatt Sie davon zu überzeugen, dass die Messungen nachbestellt werden können, ist es vielleicht überzeugender, MPostBQP = PP zu beweisen , da bekannt ist, dass PostBQP = PP ist (siehe quant-ph / 0412187 ). Um dies zu beweisen, teilen wir es in zwei Aufgaben auf:

$\subseteq$
$\subseteq$

$\subseteq$

Das Folgende ist aus der Wikipedia- Proofskizze für PostBQP = PP angepasst .

$|\psi\rangle = \prod_i (P_i^1 \prod_j A^{ij}) |x\rangle$ $P_i^1$ $i$ $|1\rangle$ $A^{ij}$ $A^{ij}$

$\{p_i\}$ $q$ $\pi_0 = \sum_{w \in S_0} \psi_w^2$ $\pi_1 = \sum_{w \in S_1} \psi_w^2$ $S_0$ $S_1$ $p_i = 1 \forall i$ $q=0$ $q=1$ $\pi(1) \geq 2\pi(0)$ $\pi_0 \geq 2\pi_1$ $\pi_0$ $\pi_1$ $\psi_w$ $\psi$ $w$ $i$ $j$ $A^{ij}$ $k$ $G$ $\psi_w = \sum_{\alpha_1 ... \alpha_G} A^{G}_{w,\alpha_G} A^{G-1}_{\alpha_G,\alpha_{G-1}} ... A^{1}_{\alpha_2,\alpha_1} x_{\alpha_1}$

Die Idee ist also, eine PP- Maschine zu konstruieren , die mit Wahrscheinlichkeit akzeptiert $\frac{1}{2}(1+C(\pi_1-\pi_0))$ $C>0$ $x \in L$ $\frac{1}{2}(1+\pi_1-\pi_0)> \frac{1}{2}$ $\frac{1}{2}(1+\pi_1-\pi_0) < \frac{1}{2}$ $x \notin L$

$\alpha = \{\alpha_i\}$ $F(A,w,\alpha,X) = A^{G}_{w,\alpha_G} A^{G-1}_{\alpha_G,\alpha_{G-1}} ... A^{1}_{\alpha_2,\alpha_1} x_{\alpha_1}$ $\pi_1 - \pi_0 = \sum_{w \in S_1} \sum{\alpha,\alpha'} F(A,w,\alpha,X)F(A,w,\alpha',X) - \sum_{w \in S_0} \sum{\alpha,\alpha'} F(A,w,\alpha,X)F(A,w,\alpha',X)$

Eine solche PP- Maschine kann dann wie folgt definiert werden:

$w$
$w \notin S_0 \cup S_1$ $1/2$
$\alpha$ $\alpha'$ $G$
$X = F(A,w,\alpha,x)F(A,w,\alpha',x)$
$w\in S_1$ $\frac{1+X}{2}$ $w\in S_0$ $\frac{1-X}{2}$

$\subseteq$ $k$

Joe Fitzsimons
quelle

Dieses Argument zeigt, dass die Vermischung mehrerer Nachauswahlen mit einheitlichen Entwicklungen nichts mehr als PP ergibt. Ich bin völlig einverstanden. Wir können sie ohne Machtverlust bis zum Ende verschieben und wir brauchen nur eine. Ich sehe nicht, dass dieses Argument mir mehr sagt. Aber meine Frage stellt etwas anderes; Es handelt sich um eine einheitliche Entwicklung, gefolgt von Mess- und Auswahlrunden (wobei die endgültigen Wahrscheinlichkeiten über diese Entscheidungsbaummethode berechnet werden). Ich sehe also nicht, dass dies meine Frage anspricht.

Shaun Harker

Um nicht zu sagen, ich schätze die Mühe, die Sie in Ihre Antwort gesteckt haben, nicht (extrem). Ich sehe nur nicht, dass es das anspricht, was ich wirklich versucht habe zu erreichen, was ich zugegebenermaßen nicht allzu gut erklärt habe.

Shaun Harker

@Shaun: Ich sehe den Unterschied nicht. Schlagen Sie vor, dass das Hinzufügen von Messungen die Leistung ändert? Dies ist sicherlich nicht der Fall, da Messungen immer einer einheitlichen Evolution auf einem größeren Hilbert-Raum entsprechen.

Joe Fitzsimons

@Shaun: Mein Punkt ist, dass mathematisch die Situation mit Messungen und die Situation ohne (aber mit einem entsprechend vergrößerten Hilbert-Raum) identisch sind. Ich versuche nicht, irgendeine Art von philosophischem Punkt zu machen oder eine Interpretation der Quantenmechanik zu bevorzugen. Ich weise lediglich darauf hin, dass das Hinzufügen von Messungen aufgrund eines gut etablierten (mathematischen) Ergebnisses keinen Unterschied zur Rechenleistung macht.

Joe Fitzsimons

@Shaun: Es scheint mir, dass Sie die Nachauswahl falsch implementieren. Wenn Sie es auf normale Weise implementieren (dh wenn Sie berücksichtigen, welche Statistiken Sie erhalten, wenn Sie nur die Ergebnisse berücksichtigen, die einem bestimmten Kriterium entsprechen), erhalten Sie PostBQP = MPostBQP, wie sowohl Niel als auch ich gezeigt haben. Sie erhalten auch identische Statistiken unabhängig von der Reihenfolge der Messungen des Zustands, den Sie in den Kommentaren angegeben haben. Wichtig ist, dass das erste Qubit nicht mit gleicher Wahrscheinlichkeit 0 und 1 ergibt. (Fortsetzung

folgt