Wie wird der Grover-Algorithmus auf eine Datenbank angewendet?

Frage

Ich möchte den Grover-Algorithmus verwenden, um eine unsortierte Datenbank nach einem Element zu durchsuchen . Nun stellt sich die Frage, wie ich Index und Wert der Datenbank mit den Qubits initialisiere.$x$

Beispiel

• Angenommen, ich habe Qubits. Somit können klassische Werte abgebildet werden.$4$$2 ^ 4 = 16$
• Meine unsortierte Datenbank enthält die folgenden Elemente: d [\ text {Value}] = [3,2,0,1] .$d$$d [\text{Value}] = [3,2,0,1]$
• Ich möchte nach $x = 2_d = 10_b = |10\rangle$ suchen .
• Mein Ansatz: Indiziere die Datenbank $d$ mit $d [(\text{Index, Value})] = [(0,3), (1,2), (2,0), (3,1)]$ . Register $0$ und $1$ für den Index und Register $2$ und $3$ für den Wert. Wenden Sie dann den Grover-Algorithmus nur auf die Register $2$ und $3 (\text{Value})$ . Kann das realisiert werden? Gibt es einen anderen Ansatz?

Was ich bereits implementiert habe ( auf GitHub )

Der "Grover-Algorithmus mit 2-, 3-, 4-Qubits", aber was es tut, ist einfach: Die Bits werden mit initialisiert , das Orakel markiert meine Lösung (das ist nur eine Zahl wie ) erhöht der Grover-Teil die Wahrscheinlichkeit des ausgewählten Elements und verringert alle anderen Wahrscheinlichkeiten, und dann werden die Qubits ausgelesen, indem sie auf die klassischen Bits abgebildet werden. Wir lassen diesen Prozess mehrmals hintereinander ablaufen und erhalten so eine Wahrscheinlichkeitsverteilung, bei der die höchste Wahrscheinlichkeit unser gesuchtes Element .$|0\rangle$$x$$2_d = 10_b$$x$$x$

Die Ausgabe ist immer die gleiche wie die im Orakel angegebene. Wie kann ich aus der Ausgabe weitere Informationen generieren, die ich zum Zeitpunkt der Erstellung des Orakels noch nicht kenne?

Ich habe auch an diesem Problem gearbeitet. Als Anfänger und klassischer Programmierer (dh ich spreche keine Quantenmechanik) ist es schwierig, die Konzepte ohne vollständige Beispiele zu verstehen. Ich habe mit dem Beispiel für die Microsoft Q # -Datenbanksuche gearbeitet . Es wird einfach nach einem bestimmten Index / Schlüssel in der Datenbank gesucht, was nicht sehr nützlich ist. Ich habe dieses Beispiel erweitert, um eine Liste von Werten in einer Datenbank zu durchsuchen und den entsprechenden Schlüssel zurückzugeben.

Wie in Ihrem Beispiel gibt es ein Zwei-Qubit-Schlüsselregister für die Indizes und ein separates Zwei-Qubit-Register für die Werte. Es gibt auch ein fünftes "markiertes Qubit", das aus dem Beispiel von Microsoft stammt und angibt, wann der gewünschte Wert gefunden wurde. Die Schlüssel und Werte sind durch Verschränkung verbunden. Das lässt sich am besten mit einer Schaltung demonstrieren. Klicken Sie hier, um die aktuelle Rennstrecke von Quirk zu sehen .

Beachten Sie, dass diese Schaltung nur das Orakel enthält. Es werden nicht alle Algorithmen von Grover implementiert.

• Die oberen beiden Qubits sind das Schlüsselregister, die nächsten beiden sind das Wertregister und das untere Qubit ist das markierte Qubit.
• Der erste Abschnitt ordnet das Schlüsselregister unter Verwendung von Haramard-Gattern in einer einheitlichen Überlagerung an, wie es der Algorithmus von Grover erfordert.
• Im zweiten Abschnitt werden die Schlüssel durch Verschränkung mit den Werten verknüpft. Jeder Schlüssel wird durch Anwenden von (Anti) Controlled X-Gattern mit einem entsprechenden Wert im Werteregister verwickelt. Wenn also das Schlüsselregister 0 ist, wird das Wertregister auf 3 gesetzt. Wenn der Schlüssel 1 ist, wird der Wert auf 2 gesetzt und so weiter.
• Der dritte Teil der Strecke ist das Suchorakel. Das Werteregister ist mit dem markierten Qubit verwickelt. In diesem Beispiel ist der gewünschte Wert 2. Wenn das Werteregister 2 enthält, wird das markierte Qubit auf 1 gesetzt.
• Der Algorithmus von Grover untersucht das Schlüsselregister und das markierte Qubit. Das Suchorakel sieht sich das Werteregister an und setzt das markierte Qubit. Dadurch wird Taste 1 verstärkt, wenn der Wert 2 ist.

Es ist interessant festzustellen, dass die Schlüssel und Werte nicht in den Qubits gespeichert sind, sondern in der Schaltung / im Programm. Man könnte sagen, dass es sich nicht wirklich um eine Datenbank an sich handelt. Es ist eher eine switch / case-Anweisung, die jedoch auf einer Überlagerung von Werten basieren kann.

Weitere Informationen, Vorbehalte und Q # -Code finden Sie in meinem GitHub-Repository .

EDIT: Etwas, das ich seit der Beantwortung besser verstehe ... Sie müssen die Schaltung als Teil jeder Iteration umkehren / rückgängig machen. Im Q # -Code erledigt der Adjoint StatePreparationOracle () -Aufruf innerhalb der ReflectStart () -Operation dies, sodass ich es nicht explizit tun musste. Ich weiß nicht, ob Qiskit eine ähnliche Funktion hat. Wenn ich die Übersetzung richtig gemacht habe, ist hier eine komplette Schaltung für das obige Beispiel.

$n=4$

Ich denke, es ist besser, sich den Quantensuchalgorithmus als Optimierung einer Funktion vorzustellen, als in einer Liste / Datenbank zu suchen. Hier ist ein Artikel, an dem ich gearbeitet habe, in dem die Quantensuche zur Lösung eines kombinatorischen Maximierungsproblems verwendet wird, wenn Sie Ihr Verständnis des Algorithmus weiter vertiefen möchten.

Sie müssen das Orakel konvertieren, um auch die Datenbank zu halten. Infolgedessen wird das allgemeine Oracle (Phase Inversion) zwei Unterorakel haben, die die Abbildung betrachten.

Das erste Unterorakel, das vorbereitet werden muss, ist die Speicherschaltung. Im Gegensatz zu QRAM, die Quantendaten (Zustand) in ihrem Körper speichert, ist diese Speicherschaltung (Array) darauf vorbereitet, nur klassische Informationen in ihrem Rahmen zu speichern. Ein Beispiel für eine solche Art von Schaltung, die ein Array von Binärdateien [010, 110, 100, 011] speichert, ist nachstehend dargestellt: Lesen Sie dieses Dokument, um weitere Informationen zu erhalten .