In Mike und Ikes "Quantenberechnung und Quanteninformation" wird der Grover-Algorithmus ausführlich erklärt. In dem Buch und in allen Erklärungen, die ich online für Grovers Algorithmus gefunden habe, scheint es jedoch keine Erwähnung zu geben, wie Grovers Orakel aufgebaut ist, es sei denn, wir wissen bereits, nach welchem Zustand wir suchen, was den Zweck des Grovers zunichte macht Algorithmus. Insbesondere lautet meine Frage: Wenn man f (x) so gibt, dass für einen x-Wert f (x) = 1 ist, aber für alle anderen f (x) = 0, wie konstruiert man ein Orakel, von dem man uns bekommt unser willkürlicher Anfangszustand | x> | y> bis | x> | y + f (x)>? So viele explizite Details wie möglich (vielleicht ein Beispiel?) Wären sehr dankbar. Wenn eine solche Konstruktion für eine beliebige Funktion mit Hadamard, Pauli oder anderen Standardquantengattern möglich ist,
16
Antworten:
Das Orakel ist im Grunde nur eine Implementierung des Prädikats, für das Sie nach einer zufriedenstellenden Lösung suchen möchten.
Angenommen, Sie haben ein 3-Sat-Problem:
Oder in Tabellenform, wobei jede Zeile eine 3-Klausel ist, wobei x "diese Variable falsch", o "diese Variable wahr" und Leerzeichen "nicht in Klausel" bedeutet:
Erstellen Sie nun eine Schaltung, die berechnet, ob der Eingang eine Lösung ist, wie folgt:
Um Ihre Schaltung in ein Orakel zu verwandeln, schlagen Sie das Ausgangsbit mit einem Z-Gatter und berechnen Sie den von Ihnen verursachten Müll nicht (dh führen Sie die Rechenschaltung in umgekehrter Reihenfolge aus):
Das ist alles dazu. Berechnen Sie das Prädikat, schlagen Sie das Ergebnis mit einem Z und berechnen Sie das Prädikat nicht. Das ist ein Orakel.
Iterieren Sie Diffusionsschritte mit Orakelschritten, und Sie haben eine Grover-Suche :
... obwohl Sie wahrscheinlich ein Beispiel mit weniger Lösungen auswählen sollten, ist der Fortschritt schrittweise (anstatt sich wie in meinem Beispiel um mehr als 90 Grad pro Schritt entlang der Ebene des Startzustands-Lösungszustands zu drehen).
quelle