Was ist Nachauswahl im Quantencomputer?

13

Ein Quantencomputer kann Probleme, die in der Komplexitätsklasse BQP liegen, effizient lösen . Ich habe eine Behauptung gesehen, die man (möglicherweise, weil wir nicht wissen, ob BQP eine richtige Teilmenge oder gleich PP ist) die Effizienz eines Quantencomputers durch Anwendung der Nachauswahl steigern kann und dass die Klasse der effizient lösbaren Probleme jetzt postBQP = wird PP .

Was bedeutet Nachauswahl hier?

jk - Monica wieder einsetzen
quelle

Antworten:

16

"Nachauswahl" bezieht sich auf den Prozess der Konditionierung des Ergebnisses einer Messung an einem anderen Qubit. (Dies ist etwas, das Sie sich auch für klassische Wahrscheinlichkeitsverteilungen und statistische Analysen vorstellen können: Es ist kein spezielles Konzept für die Quantenberechnung.)

Die Nachselektion wurde (bis zu diesem Zeitpunkt) in quantenmechanischen Experimenten häufig verwendet, da sie - für Experimente an sehr kleinen Systemen mit nicht sehr vielen Teilchen - eine relativ einfache Möglichkeit ist, eine gute Quantenkontrolle oder Vorwärtskopplung zu simulieren. Dies ist jedoch keine praktische Methode zur Realisierung von Berechnungen, da Sie von einem Ergebnis einer oder mehrerer Messungen abhängig sein müssen, die mit sehr geringer Wahrscheinlichkeit auftreten können.

Tatsächlich ist das „Auswählen“ eines Messergebnisses nichts, was Sie in der Quantenmechanik leicht tun können - was man tatsächlich tut, ist, jedes Ergebnis wegzuwerfen, das es Ihnen nicht erlaubt, das zu tun, was Sie tun möchten. Wenn das Ergebnis, das Sie auswählen möchten, die Wahrscheinlichkeit , müssen Sie eine erwartete Zahl mal versuchen, bevor Sie das Ergebnis erhalten, das Sie auswählen möchten. Wenn für eine große ganze Zahl , warten Sie möglicherweise sehr lange.1 / p p = 1 / 2 n n0<p<11/pp=1/2nn

Das Ergebnis, dass die Nachauswahl (wie Sie sagen) die Leistung der Quantenberechnung mit begrenzten Fehlern von BQP zu PP "erhöht" , ist ein beliebtes Ergebnis in der Theorie der Quantenberechnung, nicht weil sie praktisch ist , sondern weil sie einfach und einfach ist Knackiges Ergebnis von einer Art, die in der Komplexität der Berechnungen selten ist und nützlich ist, um Intuitionen über die Quantenberechnung zu informieren - es hat zu Ideen von Experimenten zur "Quantenüberlegenheit" geführt, zum Beispiel. Sie sollten sich diese Operation jedoch nicht als eine Operation vorstellen, die Quantencomputern als praktische Technik frei zur Verfügung steht, es sei denn, Sie können nachweisen, dass die Ergebnisse, die Sie nach der Auswahl auswählen möchten, nur wenige und mit ausreichender Wahrscheinlichkeit sind (oder Wie bei der messungsbasierten Berechnung können Sie das "wünschenswerte" Ergebnis durch eine geeignete Anpassung Ihres Verfahrens simulieren, wenn Sie eines der "unerwünschten" Ergebnisse erhalten.

Niel de Beaudrap
quelle
4

Wie die andere Antwort zeigt (und auf die ich nur eine Klarstellung versuche), geht es bei der Nachauswahl nur darum, eine Teilmenge möglicher Messergebnisse zu betrachten. Meiner Meinung nach fällt dies in zwei verschiedene Fälle, wie unten. Ja, sie sind verschiedene Aspekte derselben Sache, aber sie werden von zwei verschiedenen Gemeinschaften sehr unterschiedlich verwendet.

Experimentelle Nachauswahl

Sie führen einige Experimente durch, sammeln jedoch nur dann Daten, wenn bestimmte Bedingungen erfüllt sind. Im Allgemeinen wird es verwendet, um angekündigte experimentelle Unvollkommenheiten zu kompensieren (dh es wird etwas ausgelöst, das uns sagt, dass wir ein unerwünschtes Ergebnis erzielt haben, bevor wir mit einem anderen Teil des Experiments fortfahren). Zum Beispiel könnten Sie ein Paar Photonen als Informations- oder Verschränkungsträger verwenden, aber manchmal gehen diese Photonen unterwegs verloren. Wenn Sie nur dann etwas tun, wenn beide Photonen erkannt wurden, wählen Sie sie bei erfolgreicher Ankunft nach.

Theoretische Nachauswahl

Dies ist ein Gedankenexperiment über " Wie viel leistungsfähiger könnte mein Computer sein, wenn ich die Ergebnisse von Messungen auswählen könnte? " Und ist kein praktischer Vorschlag.

Denken Sie als einfaches Beispiel an die Quantenteleportation. Im normalen Szenario teilen sich Alice und Bob ein Bell-Paar, und Alice hat ein Qubit in einem unbekannten Zustand, das sie zu Bob teleportieren möchte. Sie führt eine Bell-Messung an ihren beiden Qubits durch und sendet ihr Messergebnis an Bob. Wenn Bob weit von Alice entfernt ist, dauert es eine begrenzte Zeit, bis die Informationen über das Messergebnis dort ankommen, und nach dieser Zeit kann man sich vorstellen, dass er das Qubit erhalten hat (weil er die Auswirkungen der verschiedenen Ergebnisse kompensieren muss auf dem Qubit hält er).

Wenn Alice das Messergebnis jedoch nachträglich als immer ein bestimmtes Ergebnis auswählen kann und Bob weiß, dass sie dieses auswählen wird, muss Alice das Messergebnis nicht an Bob senden. Er kann das Qubit, das er hält, sofort verwenden. Noch stärker kann er es verwenden, bevor Alice die Messung durchgeführt hat, sicher in dem Wissen, dass sie es tun wird! Sie erreichen also nicht nur eine Kommunikation, die schneller als das Licht ist, sondern Sie kommunizieren tatsächlich zeitlich rückwärts! Sie können sich vorstellen, wie immens leistungsfähig das für einen Computer sein könnte (rechnen Sie für eine beliebig lange Zeit und senden Sie die Antwort dann rechtzeitig zu dem Zeitpunkt zurück, an dem die Frage gestellt wurde).

DaftWullie
quelle
Ich verstehe den letzten Absatz nicht: Selbst wenn Alice ein bestimmtes Ergebnis einer Bell-Messung nachwählt, gibt es Messungen, die sie verwerfen muss, weil sie nicht das richtige Ergebnis liefern und Alice die Tatsache mitteilen muss, ob sie hat das experimentelle Ergebnis akzeptiert oder verworfen.
jk - Reinstate Monica
@jknappen Das ist der Unterschied zwischen Theorie und Experiment. Experimente verwerfen die falschen Ergebnisse. Die theoretische Version geht davon aus, dass Sie sie zwingen können, immer das richtige Ergebnis zu liefern. Es gibt nichts zu verwerfen.
DaftWullie
Ich denke nicht, auch theoretisch muss man einige Berechnungen verwerfen. In der klassischen Berechnung gilt das Gleiche für bekannte wissensfreie Protokolle.
jk - Stellen Sie Monica
@jknappen Ich muss zugeben, dass ich dieses Argument aus meiner Erinnerung an ein Papier rekonstruiert habe, das ich jetzt nicht sofort in die Hände legen kann, um die Details zu überprüfen. In diesem Fall geht es jedoch darum, genau das Gleiche zu tun.
DaftWullie
2
@jknappen Im letzten Absatz bezieht sich DaftWullie auf eine hypothetische Welt, in der Sie wirklich wirklich eine Nachauswahloperation ausführen können (z. B. die nicht einheitliche Einzel-Qubit-Operation anwenden [[1,0], [0,0]] durch eine Normalisierung der Wellenfunktion, wie dies in einem Simulator möglich ist ).
Craig Gidney