Warum ist in Grovers Algorithmus ein Orakel-Qubit erforderlich?

10

Ich bin etwas verwirrt über die Notwendigkeit eines Orakel-Qubits in Grovers Algorithmus.

Meine Frage ist, hängt es davon ab, wie Sie Ihr Orakel implementieren, ob Sie ein Orakel-Qubit benötigen oder nicht? Oder gibt es einen Grund für ein Orakel-Qubit? (Zum Beispiel gibt es einige Probleme, die ohne ein Orakel-Qubit nicht gelöst werden können, oder es ist einfacher, über das Problem mit einem Orakel-Qubit nachzudenken, oder es ist eine Konvention usw.)

Viele Ressourcen führen den Grover-Algorithmus mit einem Orakel-Qubit ein, aber ich habe festgestellt, dass es einige Fälle gibt, in denen Sie kein Orakel-Qubit benötigen.

Hier sind beispielsweise zwei Implementierungen des Grover-Algorithmus im IBM Q-Simulator. Einer benutzt ein Orakel-Qubit und der andere nicht. In beiden Fällen möchte ich | 11> aus einem Raum von | 00>, | 01>, | 10> und | 11> finden. In beiden Fällen wechselt Orakel erfolgreich | 11> zu - | 11>.

・ Mit einem Orakel-Qubit ( Link zum IBM Q-Simulator ) Geben Sie hier die Bildbeschreibung ein

・ Ohne Orakel-Qubit ( Link zum IBM Q-Simulator ) Geben Sie hier die Bildbeschreibung ein

algorithm grovers-algorithm Bick
quelle

Antworten:

5

Aus der Perspektive der Definition der Quantenschaltung ist das Orakel-Qubit nicht unbedingt erforderlich. Beispielsweise können Sie bei Grovers Suche normalerweise die Aktion des Orakels als wobei 1 if zurückgibt ist das markierte Element. Wir verwenden dies jedoch immer auf eine bestimmte Weise, wir in das Orakel-Qubit . Dies hat den Nettoeffekt, dass nur eine Phase für das markierte Element implementiert wird. Mit anderen Worten, es ist völlig äquivalent zur Implementierung eines neuen einheitlichen f ( x ) x ( | 0 ⟩ - | 1 ⟩ ) / √

U|x⟩|y⟩=|x⟩|y⊕f(x)⟩,
f(x)x˜ U | x⟩=(-1) f ( x ) | x⟩(|0⟩−|1⟩)/2
U~|x⟩=(−1)f(x)|x⟩

Wo es jedoch einen Unterschied macht, ist die praktische Realität. Bei der Suche nach einem Element benötigen wir tatsächlich eine Schaltung, die das markierte Element anhand der Eingabe von erkennt . An diesem Punkt ist es viel einfacher, über die Ausgabe der Antwort auf das Orakelbit nachzudenken, als die Einheit, die die Phase ergibt, direkt zu bauen, ohne das Orakel-Qubit zu verwenden. Ich vermute, wenn ich Sie bitten würde, eine generische Version zu entwerfen , würden Sie mit dem zusätzlichen Qubit als Lösung finden.˜ U U.xU~U

DaftWullie
quelle
Es ist tatsächlich sehr einfach, das zusätzliche Qubit zu vermeiden, vorausgesetzt, es wird während der Orakelberechnung nicht als Arbeitsbereich verwendet. Suchen Sie alle CNOTs auf dem zusätzlichen Qubit und ersetzen Sie sie durch ein Z-Gate auf der Steuerung des CNOT. Ersetzen Sie in ähnlicher Weise CCNOTs auf dem zusätzlichen Qubit durch eine CZ zwischen den beiden Steuerelementen des CCNOT. Usw.
Craig Gidney
@CraigGidney Es ist ein fairer Punkt, obwohl ich denke, dass Ihre Aussage mehr Annahmen enthält (was sie nicht generisch macht, auch wenn die meisten uns bekannten Fälle sie erfüllen): (1) Es sollten keine Zwischen-Ancillas verwendet werden, die während dieser Aussage verwendet werden die Funktionsbewertung; (2) die Schaltung des Orakels muss in einen Gate-Satz zerlegt werden, in dem die einzigen Multi-Qubit-Gates, die auf das Oracly-Qubit wirken, (mehrfach) gesteuerte Nots sind, die auf das Orakel-Qubit abzielen; (3) Keine anderen Gates können auf das Orakel-Qubit einwirken (dh Sie können C-Nots nicht einfach umkehren, indem Sie Hadamards an Ein- und Ausgängen verwenden).
DaftWullie
Das ist richtig.
Craig Gidney