Grover-Algorithmus

Für dieses Qiskit in Classrooms-Modul müssen Studierende eine funktionierende Python-Umgebung mit den folgenden installierten Paketen haben:

• qiskit v2.1.0 oder neuer
• qiskit-ibm-runtime v0.40.1 oder neuer
• qiskit-aer v0.17.0 oder neuer
• qiskit.visualization
• numpy
• pylatexenc

Um die oben genannten Pakete einzurichten und zu installieren, siehe den Leitfaden Qiskit installieren. Um Jobs auf echten Quantencomputern auszuführen, müssen Studierende ein Konto bei IBM Quantum® einrichten, indem sie die Schritte im Leitfaden Richte dein IBM Cloud-Konto ein befolgen.

Dieses Modul wurde getestet und verwendete 12 Sekunden QPU-Zeit. Dies ist eine Schätzung nach bestem Wissen; deine tatsächliche Nutzung kann variieren.

# Added by doQumentation — required packages for this notebook
!pip install -q qiskit qiskit-ibm-runtime

# Uncomment and modify this line as needed to install dependencies
#!pip install 'qiskit>=2.1.0' 'qiskit-ibm-runtime>=0.40.1' 'qiskit-aer>=0.17.0' 'numpy' 'pylatexenc'

Einführung

Der Grover-Algorithmus ist ein grundlegender Quantenalgorithmus, der das unstrukturierte Suchproblem adressiert: Gegeben eine Menge von $N$ Elementen und eine Möglichkeit zu überprüfen, ob ein gegebenes Element dasjenige ist, nach dem du suchst, wie schnell kannst du das gewünschte Element finden? Beim klassischen Computing gilt: Wenn die Daten unsortiert sind und es keine Struktur gibt, die ausgenutzt werden kann, ist der beste Ansatz, jedes Element einzeln zu überprüfen, was zu einer Abfragekomplexität von $O(N)$ führt – im Durchschnitt musst du etwa die Hälfte der Elemente überprüfen, bevor du das Ziel findest.

Der 1996 von Lov Grover eingeführte Grover-Algorithmus zeigt, wie ein Quantencomputer dieses Problem viel effizienter lösen kann und nur $O(\sqrt{N})$ Schritte benötigt, um das markierte Element mit hoher Wahrscheinlichkeit zu finden. Dies stellt eine quadratische Beschleunigung gegenüber klassischen Methoden dar, was für große Datensätze signifikant ist.

Der Algorithmus arbeitet im folgenden Kontext:

• Problemstellung: Du hast eine Funktion $f(x)$, die 1 zurückgibt, wenn $x$ das gewünschte Element ist, und sonst 0. Diese Funktion wird oft als Orakel oder Black Box bezeichnet, da du nur durch Abfragen von $f(x)$ etwas über die Daten erfahren kannst.
• Nutzen von Quanten: Während klassische Algorithmen für dieses Problem im Durchschnitt $N/2$ Abfragen erfordern, kann der Grover-Algorithmus die Lösung in ungefähr $\pi\sqrt{N}/4$ Abfragen finden, was für große $N$ viel schneller ist.
• Wie es funktioniert (im Überblick):
  • Der Quantencomputer erzeugt zunächst eine Überlagerung aller möglichen Zustände, die alle möglichen Elemente gleichzeitig darstellt.
  • Dann wendet er wiederholt eine Sequenz von Quantenoperationen (die Grover-Iteration) an, die die Wahrscheinlichkeit der richtigen Antwort amplifiziert und die anderen vermindert.
  • Nach genügend Iterationen liefert die Messung des Quantenzustands mit hoher Wahrscheinlichkeit die richtige Antwort.

Hier ist ein sehr einfaches Diagramm des Grover-Algorithmus, das viele Nuancen überspringt. Für ein detaillierteres Diagramm siehe dieses Paper.

Einige Dinge, die über den Grover-Algorithmus zu beachten sind:

• Er ist optimal für unstrukturierte Suche: Kein Quantenalgorithmus kann das Problem mit weniger als $O(\sqrt{N})$ Abfragen lösen.
• Er bietet nur eine quadratische, keine exponentielle Beschleunigung – im Gegensatz zu einigen anderen Quantenalgorithmen (z. B. Shors Algorithmus zum Faktorisieren).
• Er hat praktische Implikationen, wie z. B. die potenzielle Beschleunigung von Brute-Force-Angriffen auf kryptografische Systeme, obwohl die Beschleunigung nicht ausreicht, um die meiste moderne Verschlüsselung allein zu brechen.

Für Studierende im Grundstudium, die mit grundlegenden Computing-Konzepten und Abfragemodellen vertraut sind, bietet der Grover-Algorithmus eine klare Illustration, wie Quantencomputing klassische Ansätze für bestimmte Probleme übertreffen kann, auch wenn die Verbesserung "nur" quadratisch ist. Er dient auch als Einstieg in das Verständnis fortgeschrittenerer Quantenalgorithmen und des breiteren Potenzials des Quantencomputings.

Amplituden-Amplifikation ist ein Quantenalgorithmus oder eine Unterroutine für allgemeine Zwecke, die verwendet werden kann, um eine quadratische Beschleunigung gegenüber einer Handvoll klassischer Algorithmen zu erzielen. Der Grover-Algorithmus war der erste, der diese Beschleunigung bei unstrukturierten Suchproblemen demonstrierte. Die Formulierung eines Grover-Suchproblems erfordert eine Orakelfunktion, die einen oder mehrere rechnerische Basiszustände als die Zustände markiert, an deren Auffinden wir interessiert sind, und einen Amplifikationsschaltkreis, der die Amplitude markierter Zustände erhöht und folglich die verbleibenden Zustände unterdrückt.

Hier demonstrieren wir, wie man Grover-Orakel konstruiert und den GroverOperator aus der Qiskit-Schaltkreisbibliothek verwendet, um eine Grover-Suchinstanz einfach einzurichten. Das Runtime-Sampler-Primitiv ermöglicht eine nahtlose Ausführung von Grover-Schaltkreisen.

Theorie

Angenommen, es existiert eine Funktion $f$, die Binärstrings auf eine einzelne binäre Variable abbildet, d. h.

$$f: \Sigma^n \rightarrow \Sigma$$

Ein Beispiel, definiert auf $\Sigma^6$, ist

$$f(x)= \begin{cases} 1 \qquad \text{wenn }x=\{010101\}\\ 0 \qquad \text{sonst } \end{cases}$$

Ein weiteres Beispiel, definiert auf $\Sigma^{2n}$, ist

$$f(x)= \begin{cases} 1 \qquad \text{wenn gleiche Anzahl von 1en und 0en im String}\\ 0 \qquad \text{sonst } \end{cases}$$

Du bist beauftragt, Quantenzustände zu finden, die denjenigen Argumenten $x$ von $f(x)$ entsprechen, die auf 1 abgebildet werden. Mit anderen Worten, finde alle $\{x_1\}\in \Sigma^n$ so, dass $f(x_1)=1$ (oder wenn es keine Lösung gibt, melde das). Wir würden Nicht-Lösungen als $x_0$ bezeichnen. Natürlich werden wir dies auf einem Quantencomputer tun, unter Verwendung von Quantenzuständen, daher ist es nützlich, diese Binärstrings als Zustände auszudrücken:

$$\{|x_1\rangle\} \in |\Sigma^n\rangle$$

Mit der Quantenzustands-(Dirac-)Notation suchen wir nach einem oder mehreren speziellen Zuständen $\{|x_1\rangle\}$ in einer Menge von $N=2^n$ möglichen Zuständen, wobei $n$ die Anzahl der Qubits ist, und mit Nicht-Lösungen bezeichnet als $\{|x_0\rangle\}.$

Wir können uns die Funktion $f$ als von einem Orakel bereitgestellt vorstellen: eine Black Box, die wir abfragen können, um ihre Wirkung auf einen Zustand $|x\rangle$ zu bestimmen. In der Praxis werden wir die Funktion oft kennen, aber sie kann sehr kompliziert zu implementieren sein, was bedeutet, dass die Reduzierung der Anzahl von Abfragen oder Anwendungen von $f$ wichtig sein könnte. Alternativ können wir uns ein Paradigma vorstellen, in dem eine Person ein von einer anderen Person kontrolliertes Orakel abfragt, sodass wir die Orakelfunktion nicht kennen, sondern nur ihre Wirkung auf bestimmte Zustände durch Abfragen kennen.

Dies ist ein "unstrukturiertes Suchproblem", insofern es nichts Besonderes an $f$ gibt, das uns bei unserer Suche hilft. Die Ausgaben sind weder sortiert noch sind Lösungen bekanntermaßen gruppiert, und so weiter. Betrachte als Analogie alte Papier-Telefonbücher. Diese unstrukturierte Suche wäre wie das Durchsuchen, um eine bestimmte Nummer zu finden, und nicht wie das Durchsuchen einer alphabetisierten Namensliste.

Im Fall, dass eine einzelne Lösung gesucht wird, erfordert dies klassisch eine Anzahl von Abfragen, die linear in $N$ ist. Klar, du könntest eine Lösung beim ersten Versuch finden, oder du könntest in den ersten $N-1$ Vermutungen keine Lösungen finden, sodass du die $N$-te Eingabe abfragen musst, um zu sehen, ob es überhaupt eine Lösung gibt. Da die Funktionen keine ausbeutbare Struktur haben, benötigst du im Durchschnitt $N/2$ Vermutungen. Der Grover-Algorithmus erfordert eine Anzahl von Abfragen oder Berechnungen von $f$, die wie $\sqrt{N}$ skaliert.

Skizze der Schaltkreise im Grover-Algorithmus

Eine vollständige mathematische Durcharbeitung des Grover-Algorithmus findet sich beispielsweise in Fundamentals of quantum algorithms, einem Kurs von John Watrous auf IBM Quantum Learning. Eine verdichtete Behandlung ist in einem Anhang am Ende dieses Moduls enthalten. Aber vorerst werden wir nur die Gesamtstruktur des Quantenschaltkreises überprüfen, der den Grover-Algorithmus implementiert.

Der Grover-Algorithmus kann in die folgenden Stufen unterteilt werden:

• Vorbereitung einer anfänglichen Überlagerung (Anwendung von Hadamard-Gates auf alle Qubits)
• "Markierung" des Zielzustands (der Zielzustände) mit einem Phasen-Flip
• Eine "Diffusions"-Stufe, in der Hadamard-Gates und ein Phasen-Flip auf alle Qubits angewendet werden.
• Mögliche Wiederholungen der Markierungs- und Diffusionsstufen, um die Wahrscheinlichkeit zu maximieren, den Zielzustand zu messen
• Messung

Oft werden das Markierungsgate $Z_f$ und die Diffusionsschichten bestehend aus $H,$ $Z_{\text{OR}},$ und $H$ gemeinsam als der "Grover-Operator" bezeichnet. In diesem Diagramm wird nur eine einzige Wiederholung des Grover-Operators gezeigt.

Hadamard-Gates $H$ sind bekannt und werden im Quantencomputing weit verbreitet eingesetzt. Das Hadamard-Gate erzeugt Überlagerungszustände. Konkret ist es definiert durch

$$H|0\rangle = \frac{1}{\sqrt{2}}\left(|0\rangle+|1\rangle\right)\\ H|1\rangle = \frac{1}{\sqrt{2}}\left(|0\rangle-|1\rangle\right)$$

Seine Operation auf jeden anderen Zustand ist durch Linearität definiert. Insbesondere ermöglicht uns eine Schicht von Hadamard-Gates, vom Anfangszustand mit allen Qubits in $|0\rangle$ (bezeichnet als $|0\rangle^{\otimes n}$) zu einem Zustand zu gelangen, in dem jedes Qubit eine gewisse Wahrscheinlichkeit hat, entweder in $|0\rangle$ oder $|1\rangle$ gemessen zu werden; dies lässt uns den Raum aller möglichen Zustände anders untersuchen als im klassischen Computing.

Eine wichtige Folgerungseigenschaft des Hadamard-Gates ist, dass eine zweite Anwendung solche Überlagerungszustände rückgängig machen kann:

$$H\frac{1}{\sqrt{2}}\left(|0\rangle+|1\rangle\right)=|0\rangle\\ H\frac{1}{\sqrt{2}}\left(|0\rangle-|1\rangle\right)=|1\rangle$$

Dies wird gleich wichtig sein.

Überprüfe dein Verständnis

Demonstriere ausgehend von der Definition des Hadamard-Gates, dass eine zweite Anwendung des Hadamard-Gates solche Überlagerungen wie oben behauptet rückgängig macht.

Answer

Wenn wir X auf den $|+\rangle$-Zustand anwenden, erhalten wir den Wert +1 und auf den Zustand $|-\rangle$ erhalten wir -1, also wenn wir eine 50-50-Verteilung hätten, würden wir einen Erwartungswert von 0 erhalten.

Das $Z_\text{OR}$-Gate ist weniger verbreitet und ist definiert gemäß

$$\text{Z}_\text{OR}|x\rangle = \begin{cases} |x\rangle & \text{wenn } x = 0^n \\ -|x\rangle & \text{wenn } x \neq 0^n \end{cases} \qquad \forall x \in \Sigma^n$$

Schließlich ist das $Z_f$-Gate definiert durch

$$Z_f:|x\rangle \rightarrow (-1)^{f(x)}|x\rangle \qquad \forall x \in \Sigma^n$$

Beachte, dass die Wirkung davon ist, dass $Z_f$ das Vorzeichen an einem Zielzustand umdreht, für den $f(x) = 1$ gilt, und andere Zustände unbeeinflusst lässt.

Auf einer sehr hohen, abstrakten Ebene kannst du über die Schritte im Schaltkreis auf folgende Weise nachdenken:

• Erste Hadamard-Schicht: versetzt die Qubits in eine Überlagerung aller möglichen Zustände.
• $Z_f$: markiert den Zielzustand (die Zielzustände), indem ein "-"-Vorzeichen davor gesetzt wird. Dies ändert nicht sofort die Messwahrscheinlichkeiten, aber es ändert, wie sich der Zielzustand in nachfolgenden Schritten verhalten wird.
• Eine weitere Hadamard-Schicht: Das im vorherigen Schritt eingeführte "-"-Vorzeichen wird das relative Vorzeichen zwischen einigen Termen ändern. Da Hadamard-Gates eine Mischung von rechnerischen Zuständen $(|0\rangle+|1\rangle)/\sqrt{2}$ in einen rechnerischen Zustand, $|0\rangle,$ umwandeln, und sie $(|0\rangle-|1\rangle)/\sqrt{2}$ in $|1\rangle$ umwandeln, kann dieser relative Vorzeichenunterschied nun beginnen, eine Rolle dabei zu spielen, welche Zustände gemessen werden.
• Eine letzte Schicht von Hadamard-Gates wird angewendet, und dann werden Messungen vorgenommen. Wir werden im nächsten Abschnitt detaillierter sehen, wie dies funktioniert.

Beispiel

Um besser zu verstehen, wie der Grover-Algorithmus funktioniert, arbeiten wir ein kleines Zwei-Qubit-Beispiel durch. Dies kann als optional für diejenigen betrachtet werden, die sich nicht auf Quantenmechanik und Dirac-Notation konzentrieren. Aber für diejenigen, die hoffen, wesentlich mit Quantencomputern zu arbeiten, ist dies sehr zu empfehlen.

Hier ist das Schaltkreisdiagramm mit den an verschiedenen Positionen beschrifteten Quantenzuständen. Beachte, dass es mit nur zwei Qubits nur vier mögliche Zustände gibt, die unter allen Umständen gemessen werden könnten: $|00\rangle$, $|01\rangle$, $|10\rangle$ und $|11\rangle$.

Nehmen wir an, dass das Orakel ($Z_f$, uns unbekannt) den Zustand $|01\rangle$ markiert. Wir werden die Aktionen jeder Menge von Quantengattern durcharbeiten, einschließlich des Orakels, und sehen, welche Verteilung möglicher Zustände zum Zeitpunkt der Messung herauskommt. Zu Beginn haben wir

$$|\psi_0\rangle = |00\rangle$$

Mit der Definition der Hadamard-Gates haben wir

$$|\psi_1\rangle = \frac{1}{2}\left(|0\rangle+|1\rangle\right)\left(|0\rangle+|1\rangle\right)=\frac{1}{2}\left(|00\rangle+|01\rangle+|10\rangle+|11\rangle\right)$$

Jetzt markiert das Orakel den Zielzustand:

$$|\psi_2\rangle = \frac{1}{2}\left(|00\rangle-|01\rangle+|10\rangle+|11\rangle\right)$$

Beachte, dass in diesem Zustand alle vier möglichen Ergebnisse die gleiche Wahrscheinlichkeit haben, gemessen zu werden. Sie haben alle ein Gewicht der Größe $1/2,$ was bedeutet, dass sie jeweils eine $|1/2|^2=1/4$ Chance haben, gemessen zu werden. Während also der Zustand $|01\rangle$ durch die "-"-Phase markiert ist, hat dies noch nicht zu einer erhöhten Wahrscheinlichkeit geführt, diesen Zustand zu messen. Wir fahren fort, indem wir die nächste Schicht von Hadamard-Gates anwenden.

$$\begin{aligned} |\psi_3\rangle = &\frac{1}{4}\left(|00\rangle+|01\rangle+|10\rangle+|11\rangle\right)\\ -&\frac{1}{4}\left(|00\rangle-|01\rangle+|10\rangle-|11\rangle\right)\\ +&\frac{1}{4}\left(|00\rangle+|01\rangle-|10\rangle-|11\rangle\right)\\ +&\frac{1}{4}\left(|00\rangle-|01\rangle-|10\rangle+|11\rangle\right) \end{aligned}$$

Wenn wir gleichartige Terme kombinieren, finden wir

$$|\psi_3\rangle = \frac{1}{2}\left(|00\rangle+|01\rangle-|10\rangle+|11\rangle\right)$$

Jetzt dreht $Z_{\text{OR}}$ das Vorzeichen an allen Zuständen außer $|00\rangle$ um:

$$|\psi_4\rangle = \frac{1}{2}\left(|00\rangle-|01\rangle+|10\rangle-|11\rangle\right)$$

Und schließlich wenden wir die letzte Schicht von Hadamard-Gates an:

$$\begin{aligned} |\psi_5\rangle =&\frac{1}{4}\left(|00\rangle+|01\rangle+|10\rangle+|11\rangle\right)\\ -&\frac{1}{4}\left(|00\rangle-|01\rangle+|10\rangle-|11\rangle\right)\\ +&\frac{1}{4}\left(|00\rangle+|01\rangle-|10\rangle-|11\rangle\right)\\ -&\frac{1}{4}\left(|00\rangle-|01\rangle-|10\rangle+|11\rangle\right) \end{aligned}$$

Es lohnt sich, die Kombination dieser Terme durchzuarbeiten, um sich selbst davon zu überzeugen, dass das Ergebnis tatsächlich ist:

$$|\psi_5\rangle =|01\rangle$$

Das heißt, die Wahrscheinlichkeit, $|01\rangle$ zu messen, beträgt 100% (in Abwesenheit von Rauschen und Fehlern) und die Wahrscheinlichkeit, irgendeinen anderen Zustand zu messen, ist null.

Dieses Zwei-Qubit-Beispiel war ein besonders sauberer Fall; der Grover-Algorithmus wird nicht immer so funktionieren, dass eine 100%-ige Chance ergibt, den Zielzustand zu messen. Vielmehr wird er die Wahrscheinlichkeit amplifizieren, den Zielzustand zu messen. Außerdem muss der Grover-Operator möglicherweise mehr als einmal wiederholt werden.

Im nächsten Abschnitt werden wir diesen Algorithmus mit echten IBM® Quantencomputern in die Praxis umsetzen.

Das geometrische Bild

Das Zwei-Qubit-Beispiel oben hat gezeigt, wie die Algebra für einen kleinen Fall funktioniert, aber es gibt eine viel intuitivere Möglichkeit, den Grover-Algorithmus zu verstehen: als eine Folge geometrischer Spiegelungen in einer zweidimensionalen Ebene. Im Folgenden beschreiben wir dieses Bild. Weitere Details findest du auch in John Watrous' Kurs Fundamentals of Quantum Algorithms.

Aufbau der Ebene. Wir können den anfänglichen Überlagerungszustand $|\psi\rangle$ in zwei Komponenten zerlegen. Den richtigen Zustand — denjenigen, nach dem wir suchen — nennen wir $|A_1\rangle$. Jeden anderen Zustand, zusammengefasst, nennen wir $|A_0\rangle$. Per Definition sind $|A_1\rangle$ und $|A_0\rangle$ orthogonal zueinander, sodass wir sie als senkrechte Achsen in einem abstrakten, zweidimensionalen Raum darstellen können. Da $|\psi\rangle$ eine Linearkombination dieser beiden Komponenten ist, liegt er in einem kleinen Winkel $\theta$ zur $|A_0\rangle$-Achse — nahe bei $|A_0\rangle$, weil zu Beginn nur ein winziger Bruchteil des Zustands in der richtigen Komponente $|A_1\rangle$ liegt.

Spiegelungen. Die entscheidende mathematische Tatsache, die wir benötigen, ist, dass ein Operator der Form

$$2|v\rangle\langle v| - I$$

jeden Zustand um die durch $|v\rangle$ definierte Achse spiegelt. Um zu verstehen, warum, betrachte zwei Fälle: Ein Zustand entlang $|v\rangle$ bleibt unverändert, und ein Zustand senkrecht zu $|v\rangle$ bekommt sein Vorzeichen umgekehrt. Jeder andere Zustand kann in diese zwei Komponenten zerlegt werden, und der Operator wirkt entsprechend auf jede — was genau eine Spiegelung um $|v\rangle$ ist.

Es stellt sich heraus, dass sowohl der Orakel- als auch der Diffusionsschritt im Grover-Algorithmus in diesem geometrischen Bild als Spiegelungen ausgedrückt werden können.

Das Orakel als Spiegelung. Das Orakel dreht das Vorzeichen des $|A_1\rangle$-Zustands um und lässt alles andere in Ruhe. Das ist dasselbe wie eine Spiegelung um die $|A_0\rangle$-Achse.

Diffusion als Spiegelung. Es ist etwas schwieriger zu sehen, wie der Diffusionsoperator ebenfalls eine Spiegelung ist. Der Diffusionsoperator ist

$$H^{\otimes n}\, Z_{\text{OR}}\, H^{\otimes n}$$

$Z_{\text{OR}}$ allein ist eine Spiegelung um den Null-Zustand, da er das Vorzeichen jedes Zustands umkehrt, der nicht $|0\rangle^{\otimes n}$ ist. Dies lässt sich als $2|0\rangle\langle 0| - I$ schreiben. Die umgebenden Hadamard-Schichten führen effektiv einen Basiswechsel durch und transformieren die Spiegelungsachse. Erinnere dich daran, dass $H^{\otimes n}$ den Zustand $|0\rangle^{\otimes n}$ auf die gleichmäßige Überlagerung $|u\rangle = \frac{1}{\sqrt{N}}\sum_{x}|x\rangle$ abbildet. Da das Hadamard seine eigene Inverse ist, wird der gesamte Ausdruck zu

$$H^{\otimes n}\left(2|0\rangle\langle 0| - I\right)H^{\otimes n} = 2|u\rangle\langle u| - I$$

was eine Spiegelung um $|u\rangle$ ist. Da $|u\rangle$ sehr nahe bei $|\psi\rangle$ liegt (beide liegen fast entlang $|A_0\rangle$), sendet diese zweite Spiegelung den Zustand auf einen Winkel $2\theta$ von dort, wo er startete.

Rotation um $2\theta$. Der kombinierte Effekt dieser beiden Spiegelungen ist eine Rotation um $2\theta$ in Richtung $|A_1\rangle$. Jede weitere Iteration des Grover-Operators rotiert den Zustand um weitere $2\theta$.

Optimale Anzahl von Iterationen. Unser Ziel ist es, den Zustand so nah wie möglich an $|A_1\rangle$ zu rotieren, was bedeutet, um insgesamt ungefähr $\pi/2$ Bogenmäßig (eine Vierteldrehung) zu rotieren. Wenn jede Iteration $2\theta$ beiträgt, erfüllt die optimale Anzahl von Iterationen $t$

$$(2t + 1)\theta \approx \frac{\pi}{2}$$

Für eine einzelne Lösung unter $N$ Zuständen ist der anfängliche Winkel $\theta \approx \sin^{-1}(1/\sqrt{N}) \approx 1/\sqrt{N}$ (für große $N$). Einsetzen ergibt

$$t \approx \frac{\pi}{4}\sqrt{N} - \frac{1}{2}$$

Daher kommt die berühmte $\sqrt{N}$-Beschleunigung: Wir benötigen nur $O(\sqrt{N})$ Iterationen, um das Ziel zu erreichen, statt der $O(N)$ Prüfungen, die eine klassische Suche erfordern würde.

Allgemeiner gilt: Wenn es $|A_1|$ Lösungszustände unter $N$ Gesamtzuständen gibt, ist die optimale Anzahl von Iterationen

$$t \approx \frac{\pi}{4}\sqrt{\frac{N}{|A_1|}} - \frac{1}{2}$$

Beachte, dass du, wenn du zu viele Iterationen anwendest, an $|A_1\rangle$ vorbeirotatierst und die Wahrscheinlichkeit, dein Ziel zu finden, wieder abnimmt. Die richtige Anzahl von Iterationen zu finden ist wichtig, obwohl auf verrauschter Quantenhardware die experimentell optimale Zahl von dieser idealen Formel abweichen kann.

Warum ist der Grover-Algorithmus nützlich?

An diesem Punkt fragst du dich vielleicht: Wir haben gerade ein Orakel aufgebaut, das einen Zielzustand markiert — aber um es zu bauen, mussten wir den Zielzustand kennen. Wonach suchen wir also eigentlich?

Das ist eine berechtigte Frage, und es gibt mehrere gute Antworten.

• Das Abfragemodell ist ein theoretisches Werkzeug. Das Abfragemodell der Berechnung wurde nie dafür entworfen, direkt praktisch zu sein. Sein Zweck ist es, uns eine saubere Möglichkeit zu geben, algorithmische Komplexität zu analysieren, indem ein Problem in zwei Teile aufgeteilt wird: das Orakel und alles andere. Wie schwer ist die Suche, wenn Verifizierung kostenlos ist? Wie skaliert die Anzahl der Abfragen mit der Größe der Eingabe? Das sind nützliche Fragen, auch wenn kein echtes System genau so funktioniert.

• Du kannst es auch als eine Zwei-Parteien-Aktivität betrachten: Eine Person kennt den Zielzustand und baut das Orakel; die andere Person muss die Antwort mithilfe des Orakels als Black Box finden, ohne hineinzusehen. In Aktivität 2 unten wirst du genau das mit einem Partner machen.

• Amplituden-Amplifikation ist eine weithin nützliche Unterroutine. Auch wenn diese erste Demonstration zirkulär erscheint, taucht der zugrundeliegende Mechanismus — Amplituden-Amplifikation — immer wieder im Quantencomputing auf. Was wir hier wirklich aufbauen, ist eine Intuition für ein Werkzeug, das als Unterroutine in vielen komplexeren Quantenalgorithmen auftaucht.

• Es gibt Probleme, bei denen du ein Orakel bauen kannst, ohne die Antwort zu kennen. Die entscheidende Erkenntnis ist, dass es eine ganze Klasse von Problemen gibt, bei denen es sehr schwer ist, eine Lösung zu finden, aber sehr einfach ist, zu überprüfen, dass eine gegebene Lösung korrekt ist. Faktorisierung ist ein Beispiel: Gegeben ein Produkt zweier großer Primzahlen, ist es extrem schwierig, diese Primzahlen zu bestimmen, aber sobald du sie hast, kannst du sie leicht multiplizieren, um zu überprüfen. (Für die Faktorisierung speziell haben wir einen besseren Algorithmus als Grover's — siehe Shors Algorithmus — aber das ist bei Weitem nicht das einzige Problem mit diesem Merkmal.) Sudoku, Erfüllbarkeitsprobleme (constraint satisfaction) und sogar das klassische Spiel Minesweeper sind allesamt Probleme, die schwer zu lösen, aber leicht zu überprüfen sind.

Warum ist das relevant? Es bedeutet, dass wir alle Bedingungen und Anforderungen, die eine Lösung erfüllen muss, kennen können und diese Anforderungen in einen Quantenschaltkreis kodieren können, der als Orakel dient — auch wenn wir die Lösung selbst nicht kennen. Der Grover-Algorithmus findet sie für uns.

Mit diesen Ideen im Hinterkopf arbeiten wir mehrere Beispiele durch. Wir beginnen mit einem Beispiel, in dem der Lösungszustand klar angegeben ist, damit wir der Logik des Algorithmus folgen können. Danach werden wir zu einer Zwei-Parteien-Aktivität übergehen und schließlich zu einem Beispiel, bei dem das Orakel aus Problembedingungen statt aus dem Wissen um die Antwort aufgebaut wird.

Allgemeine Importe und Ansatz

Wir beginnen mit dem Import mehrerer notwendiger Pakete.

# Built-in modules
import math

# Imports from Qiskit
from qiskit import QuantumCircuit, QuantumRegister, ClassicalRegister
from qiskit.circuit.library import grover_operator, MCMTGate, ZGate
from qiskit.visualization import plot_distribution
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager

In diesem und anderen Tutorials werden wir ein Framework für Quantencomputing verwenden, das als "Qiskit-Muster" bekannt ist und Arbeitsabläufe in die folgenden Schritte unterteilt:

• Schritt 1: Klassische Eingaben auf ein Quantenproblem abbilden
• Schritt 2: Problem für die Quantenausführung optimieren
• Schritt 3: Ausführung mit Qiskit Runtime Primitives
• Schritt 4: Nachbearbeitung und klassische Analyse

Wir werden diesen Schritten im Allgemeinen folgen, obwohl wir sie möglicherweise nicht immer explizit kennzeichnen.

Aktivität 1: Einen einzelnen gegebenen Zielzustand finden

Schritt 1: Klassische Eingaben auf ein Quantenproblem abbilden

Wir benötigen das Phasenabfrage-Gate, um eine Gesamtphase (-1) auf Lösungszustände zu setzen und die Nicht-Lösungszustände unbeeinflusst zu lassen. Eine andere Art, dies zu sagen, ist, dass der Grover-Algorithmus ein Orakel erfordert, das einen oder mehrere markierte rechnerische Basiszustände spezifiziert, wobei "markiert" einen Zustand mit einer Phase von -1 bedeutet. Dies geschieht unter Verwendung eines Controlled-Z-Gates oder seiner mehrfach kontrollierten Verallgemeinerung über $N$ Qubits. Um zu sehen, wie dies funktioniert, betrachte ein spezifisches Beispiel eines Bitstrings {110}. Wir möchten einen Schaltkreis, der auf einen Zustand $|\psi\rangle = |q_2,q_1,q_0\rangle$ wirkt und eine Phase anwendet, wenn $|\psi\rangle = |011\rangle$ (wo wir die Reihenfolge des Binärstrings umgedreht haben, wegen der Notation in Qiskit, die das am wenigsten signifikante (oft 0) Qubit auf die rechte Seite setzt).

Somit wollen wir einen Schaltkreis $Z_f$, der erreicht

$$Z_f|\psi\rangle = \begin{cases} -|\psi\rangle \qquad \text{wenn} \qquad |\psi\rangle = |011\rangle \\ |\psi\rangle \qquad \text{wenn} \qquad |\psi\rangle \neq |011\rangle\end{cases}$$

Wir können das Multiple Control Multiple Target Gate (MCMTGate) verwenden, um ein Z-Gate anzuwenden, das von allen Qubits kontrolliert wird (die Phase umdrehen, wenn alle Qubits im $|1\rangle$-Zustand sind). Natürlich können einige der Qubits in unserem gewünschten Zustand $|0\rangle$ sein. Daher müssen wir für diese Qubits zuerst ein X-Gate anwenden, dann das mehrfach kontrollierte Z-Gate ausführen, dann ein weiteres X-Gate anwenden, um unsere Änderung rückgängig zu machen. Das MCMTGate sieht so aus:

mcmt_ex = QuantumCircuit(3)
mcmt_ex.compose(MCMTGate(ZGate(), 3 - 1, 1), inplace=True)
mcmt_ex.draw(output="mpl", style="iqp")

Beachte, dass viele Qubits am Kontrollprozess beteiligt sein können (hier sind es drei Qubits), aber kein einzelnes Qubit wird als Ziel bezeichnet. Dies liegt daran, dass der gesamte Zustand ein Gesamt-"-"-Vorzeichen erhält (Phasenumkehr); das Gate wirkt auf alle Qubits gleichwertig. Dies unterscheidet sich von vielen anderen Mehrqubit-Gates, wie dem CX-Gate, das ein einzelnes Kontrollqubit und ein einzelnes Zielqubit hat.

Im folgenden Code definieren wir ein Phasenabfrage-Gate (oder Orakel), das genau das tut, was wir oben beschrieben haben: markiert einen oder mehrere Eingabebasiszustände, die durch ihre Bitstring-Darstellung definiert sind. Das MCMT-Gate wird verwendet, um das mehrfach kontrollierte Z-Gate zu implementieren.

def grover_oracle(marked_states):
    """Build a Grover oracle for multiple marked states

    Here we assume all input marked states have the same number of bits

    Parameters:
        marked_states (str or list): Marked states of oracle

    Returns:
        QuantumCircuit: Quantum circuit representing Grover oracle
    """
    if not isinstance(marked_states, list):
        marked_states = [marked_states]
    # Compute the number of qubits in circuit
    num_qubits = len(marked_states[0])

    qc = QuantumCircuit(num_qubits)
    # Mark each target state in the input list
    for target in marked_states:
        # Flip target bitstring to match Qiskit bit-ordering
        rev_target = target[::-1]
        # Find the indices of all the '0' elements in bitstring
        zero_inds = [
            ind for ind in range(num_qubits) if rev_target.startswith("0", ind)
        ]
        # Add a multi-controlled Z-gate with pre- and post-applied X-gates (open-controls)
        # where the target bitstring has a '0' entry
        qc.x(zero_inds)
        qc.compose(MCMTGate(ZGate(), num_qubits - 1, 1), inplace=True)
        qc.x(zero_inds)
    return qc

Jetzt wählen wir einen bestimmten "markierten" Zustand als unser Ziel und wenden die gerade definierte Funktion an. Schauen wir uns an, welche Art von Schaltkreis sie erstellt hat.

marked_states = ["1110"]
oracle = grover_oracle(marked_states)
oracle.draw(output="mpl", style="iqp")

Wenn die Qubits 1-3 im $|1\rangle$-Zustand sind und Qubit 0 anfänglich im $|0\rangle$-Zustand ist, wird das erste X-Gate Qubit 0 auf $|1\rangle$ umdrehen und alle Qubits werden in $|1\rangle$ sein. Dies bedeutet, dass das MCMT-Gate eine Gesamt-Vorzeichenänderung oder Phasenumkehr anwenden wird, wie gewünscht. Für jeden anderen Fall sind entweder die Qubits 1-3 im $|0\rangle$-Zustand, oder Qubit 0 wird auf den $|0\rangle$-Zustand umgedreht, und die Phasenumkehr wird nicht angewendet. Wir sehen, dass dieser Schaltkreis tatsächlich unseren gewünschten Zustand $|0111\rangle,$ oder den Bitstring {1110} markiert. Der vollständige Grover-Operator besteht aus dem Phasenabfrage-Gate (Orakel), Hadamard-Schichten und dem $Z_\text{OR}$-Operator. Wir können den eingebauten grover_operator verwenden, um diesen aus dem oben definierten Orakel zu konstruieren.

grover_op = grover_operator(oracle)
grover_op.decompose(reps=0).draw(output="mpl", style="iqp")

Wie wir im geometrischen Bild oben besprochen haben, müssen wir möglicherweise den Grover-Operator mehrmals anwenden. Die optimale Anzahl von Iterationen $t$, um die Amplitude des Zielzustands in Abwesenheit von Rauschen zu maximieren, ist

$$t\approx \frac{\pi}{4} \sqrt{\frac{N}{|A_1|}}-\frac{1}{2}$$

wobei $|A_1|$ die Anzahl der Lösungszustände und $N=2^n$ die Gesamtzahl der Zustände ist. Bei modernen verrauschten Quantencomputern könnte die experimentell optimale Anzahl von Iterationen anders sein — aber hier berechnen und verwenden wir diese theoretische, optimale Zahl unter Verwendung von $|A_1|=1$.

optimal_num_iterations = math.floor(
    math.pi / (4 * math.asin(math.sqrt(len(marked_states) / 2**grover_op.num_qubits)))
)
print(optimal_num_iterations)

3

Konstruieren wir nun einen Schaltkreis, der die anfänglichen Hadamard-Gates enthält, um eine Überlagerung aller möglichen Zustände zu erzeugen, und wenden wir den Grover-Operator die optimale Anzahl von Malen an.

qc = QuantumCircuit(grover_op.num_qubits)
# Create even superposition of all basis states
qc.h(range(grover_op.num_qubits))
# Apply Grover operator the optimal number of times
qc.compose(grover_op.power(optimal_num_iterations), inplace=True)
# Measure all qubits
qc.measure_all()
qc.draw(output="mpl", style="iqp")

Wir haben unseren Grover-Schaltkreis konstruiert!

Schritt 2: Problem für die Ausführung auf Quanten-Hardware optimieren

Wir haben unseren abstrakten Quantenschaltkreis definiert, aber wir müssen ihn in Bezug auf Gates umschreiben, die nativ für den Quantencomputer sind, den wir tatsächlich verwenden möchten. Wir müssen auch angeben, welche Qubits auf dem Quantencomputer verwendet werden sollen. Aus diesen und anderen Gründen müssen wir nun unseren Schaltkreis transpilieren. Geben wir zunächst den Quantencomputer an, den wir verwenden möchten.

Unten ist Code zum Speichern deiner Anmeldeinformationen bei der ersten Verwendung. Stelle sicher, dass du diese Informationen aus dem Notebook löschst, nachdem du sie in deine Umgebung gespeichert hast, damit deine Anmeldeinformationen nicht versehentlich geteilt werden, wenn du das Notebook teilst. Siehe Richte dein IBM Cloud-Konto ein und Initialisiere den Service in einer nicht vertrauenswürdigen Umgebung für weitere Anleitungen.

# To run on hardware, select the backend with the fewest number of jobs in the queue
from qiskit_ibm_runtime import QiskitRuntimeService

# Syntax for first saving your token.  Delete these lines after saving your credentials.

# QiskitRuntimeService.save_account(channel='ibm_quantum_platform',
# instance = '<YOUR_IBM_INSTANCE_CRN>', token='<YOUR_API_KEY>', overwrite=True, set_as_default=True)
# service = QiskitRuntimeService(channel='ibm_quantum_platform')

# Load saved credentials
service = QiskitRuntimeService()

backend = service.least_busy(operational=True, simulator=False)
backend.name

qiskit_runtime_service._resolve_cloud_instances:WARNING:2025-08-08 14:14:19,931: Default instance not set. Searching all available instances.

'ibm_brisbane'

Jetzt verwenden wir einen Preset-Pass-Manager, um unseren Quantenschaltkreis für das ausgewählte Backend zu optimieren.

target = backend.target
pm = generate_preset_pass_manager(target=target, optimization_level=3)

circuit_isa = pm.run(qc)
# The transpiled circuit will be very large. Only draw it if you are really curious.
# circuit_isa.draw(output="mpl", idle_wires=False, style="iqp")

Es ist an dieser Stelle erwähnenswert, dass die Tiefe des transpilierten Quantenschaltkreises erheblich ist.

print("The total depth is ", circuit_isa.depth())
print(
    "The depth of two-qubit gates is ",
    circuit_isa.depth(lambda instruction: instruction.operation.num_qubits == 2),
)

The total depth is  439
The depth of two-qubit gates is  113

Dies sind tatsächlich ziemlich große Zahlen, selbst für diesen einfachen Fall. Da alle Quantengates (und insbesondere Zwei-Qubit-Gates) Fehler erfahren und Rauschen unterliegen, würde eine Serie von über 100 Zwei-Qubit-Gates nichts als Rauschen ergeben, wenn die Qubits nicht extrem leistungsfähig wären. Schauen wir uns an, wie diese funktionieren.

Schritt 3: Mit Qiskit-Primitiven ausführen

Wir möchten viele Messungen durchführen und sehen, welcher Zustand am wahrscheinlichsten ist. Eine solche Amplituden-Amplifikation ist ein Sampling-Problem, das für die Ausführung mit dem Sampler Qiskit Runtime-Primitiv geeignet ist.

Beachte, dass die run()-Methode von Qiskit Runtime SamplerV2 ein Iterable von Primitive Unified Blocks (PUBs) annimmt. Für Sampler ist jedes PUB ein Iterable im Format (circuit, parameter_values). Mindestens benötigt es jedoch eine Liste von Quantenschaltkreis(en).

# To run on a real quantum computer (this was tested on a Heron r2 processor and
# used 4 sec. of QPU time)

from qiskit_ibm_runtime import SamplerV2 as Sampler

sampler = Sampler(mode=backend)
sampler.options.default_shots = 10_000
result = sampler.run([circuit_isa]).result()
dist = result[0].data.meas.get_counts()

Um das Beste aus dieser Erfahrung herauszuholen, empfehlen wir dringend, dass du deine Experimente auf den von IBM Quantum verfügbaren echten Quantencomputern durchführst. Wenn du jedoch deine QPU-Zeit erschöpft hast, kannst du die folgenden Zeilen auskommentieren, um diese Aktivität mit einem Simulator abzuschließen.

# To run on local simulator:
# from qiskit.primitives import StatevectorSampler as Sampler
# sampler = Sampler()
# result = sampler.run([qc]).result()
# dist = result[0].data.meas.get_counts()

Schritt 4: Nachbearbeitung und Rückgabe des Ergebnisses im gewünschten klassischen Format

Jetzt können wir die Ergebnisse unseres Samplings in einem Histogramm darstellen.

plot_distribution(dist)

Wir sehen, dass der Grover-Algorithmus den gewünschten Zustand mit der höchsten Wahrscheinlichkeit zurückgab, mindestens eine Größenordnung höher als andere Optionen. In der nächsten Aktivität werden wir den Algorithmus auf eine Weise verwenden, die konsistenter mit dem Zwei-Parteien-Workflow eines Abfragealgorithmus ist.

Überprüfe dein Verständnis

Wir haben gerade nach einer einzelnen Lösung in einer Menge von $2^4=16$ möglichen Zuständen gesucht. Wir haben die optimale Anzahl von Wiederholungen des Grover-Operators als $t=3$ bestimmt. Würde diese optimale Zahl zunehmen oder abnehmen, wenn wir nach (a) einer von mehreren Lösungen suchen würden, oder (b) einer einzelnen Lösung in einem Raum von mehr möglichen Zuständen?

Answer

Erinnere dich daran, dass wir, solange die Anzahl der Lösungen im Vergleich zum gesamten Lösungsraum klein ist, die Sinusfunktion um kleine Winkel erweitern und verwenden können

$$(2t+1)\theta = (2t+1) \sin^{-1}{\sqrt{\frac{|\mathcal{A}_1|}{N}}}\approx (2t+1) \sqrt{\frac{|\mathcal{A}_1|}{N}} \approx \pi/2\\ t \approx \frac{\pi}{4}\sqrt{\frac{N}{|\mathcal{A}_1|}}-\frac{1}{2}$$

(a) Wir sehen aus dem obigen Ausdruck, dass die Erhöhung der Anzahl von Lösungszuständen die Anzahl der Iterationen verringern würde. Vorausgesetzt, dass der Bruch $\frac{|\mathcal{A}_1|}{N}$ noch klein ist, können wir beschreiben, wie $t$ abnehmen würde: $t~\frac{1}{\sqrt{|\mathcal{A}_1|}}.$

(b) Wenn der Raum möglicher Lösungen ($N$) zunimmt, erhöht sich die Anzahl der erforderlichen Iterationen, aber nur wie $t~\sqrt{N}$.

Angenommen, wir könnten die Größe des Ziel-Bitstrings beliebig lang erhöhen und hätten dennoch das Ergebnis, dass der Zielzustand eine Wahrscheinlichkeitsamplitude hat, die mindestens eine Größenordnung größer ist als jeder andere Zustand. Bedeutet dies, dass wir den Grover-Algorithmus verwenden könnten, um zuverlässig den Zielzustand zu finden?

Answer

Nein. Angenommen, wir würden die erste Aktivität mit 20 Qubits wiederholen und den Quantenschaltkreis eine Anzahl von Malen num_shots = 10.000 ausführen. Eine gleichmäßige Wahrscheinlichkeitsverteilung würde bedeuten, dass jeder Zustand eine Wahrscheinlichkeit von $10.000/2^{20}=0,00954$ hat, auch nur ein einziges Mal gemessen zu werden. Wenn die Wahrscheinlichkeit, den Zielzustand zu messen, 10 Mal so hoch wäre wie die von Nicht-Lösungen (und die Wahrscheinlichkeit jeder Nicht-Lösung entsprechend leicht verringert würde), gäbe es nur etwa eine 10%-ige Chance, den Zielzustand auch nur einmal zu messen. Es wäre sehr unwahrscheinlich, den Zielzustand mehrmals zu messen, was ihn von den vielen zufällig erhaltenen Nicht-Lösungszuständen nicht zu unterscheiden machen würde. Die gute Nachricht ist, dass wir noch höhere Treue-Ergebnisse durch Verwendung von Fehlerunterdrückung und -minderung erhalten können.

Aktivität 2: Ein präziser Abfragealgorithmus-Workflow

Wir beginnen diese Aktivität genau wie die erste, außer dass du dich jetzt mit einem anderen Qiskit-Enthusiasten zusammentun wirst. Du wirst einen geheimen Bitstring wählen, und dein Partner wird einen (im Allgemeinen) anderen Bitstring wählen. Ihr werdet jeweils einen Quantenschaltkreis generieren, der als Orakel fungiert, und ihr werdet sie austauschen. Du wirst dann den Grover-Algorithmus mit diesem Orakel verwenden, um den geheimen Bitstring deines Partners zu bestimmen.

Schritt 1: Klassische Eingaben auf ein Quantenproblem abbilden

Konstruiere mit der oben definierten grover_oracle-Funktion einen Orakel-Schaltkreis für einen oder mehrere markierte Zustände. Stelle sicher, dass du deinem Partner mitteilst, wie viele Zustände du markiert hast, damit er den Grover-Operator die optimale Anzahl von Malen anwenden kann. Mache deinen Bitstring nicht zu lang. 3-5 Bits sollten ohne große Schwierigkeiten funktionieren. Längere Bitstrings würden zu tiefen Schaltkreisen führen, die fortgeschrittenere Techniken wie Fehlerminderung erfordern.

# Modify the marked states to mark those you wish to target.
marked_states = ["1000"]
oracle = grover_oracle(marked_states)

Jetzt hast du einen Quantenschaltkreis erstellt, der die Phase deines Zielzustands umdreht. Du kannst diesen Schaltkreis als my_circuit.qpy mit der unten stehenden Syntax speichern.

from qiskit import qpy

# Save to a QPY file at a location where you can easily find it.
# You might want to specify a global address.
with open("C:\\Users\\...put your own address here...\\my_circuit.qpy", "wb") as f:
    qpy.dump(oracle, f)

Sende diese Datei jetzt an deinen Partner (per E-Mail, Messaging-Service, einem gemeinsamen Repo usw.). Lass deinen Partner auch seinen Schaltkreis an dich senden. Stelle sicher, dass du die Datei an einem Ort speicherst, wo du sie leicht finden kannst. Sobald du den Schaltkreis deines Partners hast, könntest du ihn visualisieren - aber das würde das Abfragemodell brechen. Das heißt, wir modellieren eine Situation, in der du das Orakel abfragen kannst (den Orakel-Schaltkreis verwenden), es aber nicht untersuchen kannst, um zu bestimmen, welchen Zustand es anvisiert.

from qiskit import qpy

# Load the circuit from your partner's qpy file from the folder where you saved it.
with open("C:\\Users\\...file location here...\\my_circuit.qpy", "rb") as f:
    circuits = qpy.load(f)

# qpy.load always returns a list of circuits
oracle_partner = circuits[0]

# You could visualize the circuit, but this would break the model of a query algorithm.
# oracle_partner.draw("mpl")

Frage deinen Partner, wie viele Zielzustände er codiert hat, und gib es unten ein.

# Update according to your partner's number of target states.
num_marked_states = 1

Dies wird im nächsten Ausdruck verwendet, um die optimale Anzahl von Grover-Iterationen zu bestimmen.

grover_op = grover_operator(oracle_partner)
optimal_num_iterations = math.floor(
    math.pi / (4 * math.asin(math.sqrt(num_marked_states / 2**grover_op.num_qubits)))
)
qc = QuantumCircuit(grover_op.num_qubits)
qc.h(range(grover_op.num_qubits))
qc.compose(grover_op.power(optimal_num_iterations), inplace=True)
qc.measure_all()

Schritt 2: Problem für die Ausführung auf Quanten-Hardware optimieren

Dies verläuft genau wie zuvor.

# To run on hardware, select the backend with the fewest number of jobs in the queue
service = QiskitRuntimeService()
backend = service.least_busy(operational=True, simulator=False)
backend.name

target = backend.target
pm = generate_preset_pass_manager(target=target, optimization_level=3)
circuit_partner_isa = pm.run(qc)

Schritt 3: Mit Qiskit-Primitiven ausführen

Dies ist ebenfalls identisch mit dem Prozess in der ersten Aktivität.

# To run on a real quantum computer (this was tested on a Heron r2 processor and used
# 4 seconds of QPU time)

from qiskit_ibm_runtime import SamplerV2 as Sampler

sampler = Sampler(mode=backend)
sampler.options.default_shots = 10_000
result = sampler.run([circuit_partner_isa]).result()
dist = result[0].data.meas.get_counts()

Schritt 4: Nachbearbeitung und Rückgabe des Ergebnisses im gewünschten klassischen Format

Zeige jetzt ein Histogramm deiner Sampling-Ergebnisse an. Ein oder mehrere Zustände sollten eine viel höhere Messwahrscheinlichkeit haben als die anderen. Melde diese deinem Partner und überprüfe, ob du die Zielzustände korrekt bestimmt hast. Standardmäßig ist das angezeigte Histogramm das desselben Schaltkreises aus der ersten Aktivität. Du solltest unterschiedliche Ergebnisse vom Schaltkreis deines Partners erhalten.

plot_distribution(dist)

Überprüfe dein Verständnis

Du solltest den Zielzustand (die Zielzustände) deines Partners korrekt erhalten haben. Wenn nicht, arbeite mit deinem Partner zusammen, um herauszufinden, was schief gelaufen ist. Klicke unten für einige Ideen.

Hints

• Visualisiere/zeichne den Schaltkreis deines Partners und stelle sicher, dass er korrekt geladen wurde.
• Vergleiche die verwendeten Schaltkreise und vergleiche das erwartete Ergebnis mit dem, was du erhalten hast.
• Überprüfe die Tiefe der verwendeten Schaltkreise, um sicherzustellen, dass der Bitstring nicht zu lang war oder die Anzahl der Grover-Iterationen nicht unerschwinglich hoch war.

Wenn du es noch nicht getan hast, zeichne den Orakel-Schaltkreis, den dein Partner dir geschickt hat. Sieh, ob du die Wirkung jedes Gates durchsprechen und argumentieren kannst, was der Zielzustand gewesen sein muss. Dies wird viel einfacher sein für den Fall eines einzelnen markierten Zustands als für mehrere.

Hints

• Erinnere dich, dass die Aufgabe des Orakels darin besteht, das Vorzeichen am Zielzustand umzudrehen.
• Erinnere dich, dass das MCMTGate das Vorzeichen an einem Zustand umdreht, wenn und nur wenn alle am Kontrollprozess beteiligten Qubits im $|1\rangle$-Zustand sind.
• Wenn dein Zielzustand bereits ein $|1\rangle$ an einem bestimmten Qubit hat, musst du nichts mit diesem Qubit tun. Wenn dein Ziel ein $|0\rangle$ an einem bestimmten Qubit hat und du möchtest, dass das MCMTGate das Vorzeichen umdreht, musst du ein X-Gate auf dieses Qubit in deinem Orakel anwenden (und dann das X-Gate nach dem MCMTGate rückgängig machen).

Wiederhole das Experiment mit einer Iteration weniger des Grover-Operators. Erhältst du immer noch die richtige Antwort? Warum oder warum nicht?

Guidance

Du wirst es wahrscheinlich tun, obwohl es von der Anzahl der codierten Lösungen abhängen könnte. Dies hebt eine Subtilität hervor: Die "optimale" Anzahl von Grover-Iterationen ist die Zahl, die die Wahrscheinlichkeit, den markierten Zustand zu messen, so hoch wie möglich macht. Aber weniger Iterationen als das könnten den markierten Zustand dennoch wesentlich wahrscheinlicher machen als andere Zustände. Daher könntest du mit weniger Iterationen als der optimalen Anzahl auskommen. Dies reduziert die Schaltkreistiefe und reduziert somit Fehlerraten.

Warum könnte jemand weniger Grover-Iterationen verwenden wollen als die hier identifizierte "optimale Anzahl"?

Answer

Die "optimale" Anzahl von Grover-Iterationen ist die Zahl, die die Wahrscheinlichkeit, den markierten Zustand zu messen, in Abwesenheit von Rauschen so hoch wie möglich macht. Aber weniger Iterationen als das könnten den markierten Zustand dennoch wesentlich wahrscheinlicher machen als andere Zustände. Du könntest also mit weniger Iterationen als der optimalen Anzahl auskommen. Dies reduziert die Schaltkreistiefe und reduziert somit Fehlerraten.

Aktivität 3: Ein Minesweeper-Feld mit dem Grover-Algorithmus lösen

Im vorherigen Abschnitt haben wir festgestellt, dass der Grover-Algorithmus wirklich nützlich wird, wenn wir ein Orakel aus den Bedingungen eines Problems aufbauen können, anstatt aus dem Wissen um die Antwort. Minesweeper ist ein perfektes Beispiel: Die nummerierten Zellen sagen uns, wie viele Minen benachbart sind, und diese Bedingungen bestimmen vollständig, wo die Minen sein müssen — aber das Finden der Konfiguration erfordert Suche.

Es wurde bewiesen, dass Minesweeper NP-vollständig ist: Es ist schwer zu lösen, aber leicht zu überprüfen. Das macht es zu einem natürlichen Kandidaten für den Grover-Algorithmus. Natürlich können wir auf einem verrauschten Quantencomputer noch kein vollständiges 9$\times$9-Feld lösen — die Schaltkreise wären viel zu tief. Stattdessen verwenden wir ein winziges Feld als Spielzeugdemonstration, wie man sich einem größeren Feld auf einer zukünftigen fehlertoleranten Maschine nähern würde.

Ein paar wichtige Vorbehalte. Der Grover-Algorithmus bietet nur eine quadratische Beschleunigung gegenüber der unstrukturierten klassischen Suche. Minesweeper hat mit hoher Wahrscheinlichkeit ausbeutbare Struktur, die ein cleverer klassischer Algorithmus nutzen könnte. Und für einen exponentiell wachsenden Suchraum reicht auch die $\sqrt{N}$-Verbesserung nur so weit. Aber setzen wir diese Bedenken beiseite und verwenden wir dieses Spielzeugproblem, um zu illustrieren, wie Problembedingungen in ein Quanten-Orakel kodiert werden.

Das Feld

Hier ist unser kleines Minesweeper-Feld:

Jede leere Zelle kann durch eine binäre Variable dargestellt werden, die angibt, ob sie eine Mine enthält. Wir bezeichnen diese als $x_0$, $x_1$ und $x_2$, wobei $x_i = 1$ bedeutet, dass sich eine Mine auf dieser Zelle befindet, und $x_i = 0$ bedeutet, dass dies nicht der Fall ist:

Wir könnten dies in etwa einer halben Sekunde im Kopf lösen, aber wir verwenden dieses Spielzeugproblem, um zu illustrieren, wie ein viel schwierigeres Feld mit einem Quantencomputer angegangen werden könnte.

Bedingungen kodieren

Jede nummerierte Zelle stellt eine Bedingung an die benachbarten leeren Zellen. Wir müssen diese Bedingungen als boolesche Ausdrücke formulieren, die in einen Quantenschaltkreis kodiert werden können.

Die „1"-Zelle, die an $x_0$ und $x_1$ angrenzt, sagt, dass genau eine von ihnen eine Mine enthält. Das ist genau die exklusive Oder-Operation (XOR), $\oplus$, die wahr zurückgibt, wenn genau eine ihrer Eingaben wahr ist:

$$(x_0 \oplus x_1)$$

Ebenso gibt uns die andere „1"-Zelle (angrenzend an $x_1$ und $x_2$):

$$(x_1 \oplus x_2)$$

Die „2"-Zelle sagt, dass zwei der drei leeren Zellen Minen enthalten müssen. Da XOR eine Paritätsoperation ist, gibt $x_0 \oplus x_1 \oplus x_2$ wahr zurück, wenn eine ungerade Anzahl der Variablen wahr ist. Wir möchten eine gerade Anzahl (konkret zwei), die wahr ist, also negieren wir mit $\lnot$:

$$\lnot(x_0 \oplus x_1 \oplus x_2)$$

Für sich allein wäre dieser Ausdruck erfüllt, wenn entweder null oder zwei Qubits im $|1\rangle$-Zustand sind, da es sich um eine Paritätsaussage handelt. Aber in Kombination mit den anderen beiden Klauseln, die jeweils mindestens eine Mine erfordern, ist die einzige erfüllende Belegung diejenige mit genau zwei Minen.

Alle drei Bedingungen müssen gleichzeitig erfüllt sein, daher verknüpfen wir sie mit Und-Symbolen $\land$:

$$(x_0 \oplus x_1) \;\land\; (x_1 \oplus x_2) \;\land\; \lnot(x_0 \oplus x_1 \oplus x_2)$$

Schritt 1: Klassische Eingaben auf ein Quantenproblem abbilden

Jetzt müssen wir diesen booleschen Ausdruck in einen Quantenschaltkreis kodieren, der als Orakel dient. Die Quantenversion von XOR kann mit CX-Gates (CNOT-Gates) erreicht werden: Das Anwenden von zwei CX-Gates von den Daten-Qubits auf ein Arbeitsbereich-Qubit (Ancilla) berechnet effektiv deren XOR und speichert das Ergebnis im Ancilla.

Wir führen drei Arbeitsbereich-Qubits ein — eines für jede Klausel. Wir speichern das Ergebnis jedes booleschen Ausdrucks in seinem entsprechenden Arbeitsbereich-Qubit und verwenden dann ein mehrfach kontrolliertes Z-Gate, um die Phase des Drei-Qubit-Zustands umzukehren, bei dem alle drei Arbeitsbereich-Qubits $|1\rangle$ sind (d. h. alle Klauseln gleichzeitig erfüllt sind).

In der ersten Code-Zelle unten bauen wir die „Berechnen"-Hälfte des Orakels — den Teil, der jede Klausel auswertet und das Ergebnis in die Arbeitsbereich-Qubits schreibt.

x = QuantumRegister(3, "x")
a = QuantumRegister(3, "a")
qc = QuantumCircuit(x, a)

# Clause 1: x0 XOR x1 -> stored in a[0]
qc.cx(x[0], a[0])
qc.cx(x[1], a[0])

# Clause 2: x1 XOR x2 -> stored in a[1]
qc.cx(x[1], a[1])
qc.cx(x[2], a[1])

# Clause 3: NOT(x0 XOR x1 XOR x2) -> stored in a[2]
qc.cx(x[0], a[2])
qc.cx(x[1], a[2])
qc.cx(x[2], a[2])
qc.x(a[2])  # The NOT

qc.draw("mpl", style="iqp")

An diesem Punkt ist das Ergebnis jeder Klausel in ihrem entsprechenden Arbeitsbereich-Qubit gespeichert. Jetzt müssen wir dafür sorgen, dass der Drei-Qubit-Datenzustand, bei dem alle drei Arbeitsbereich-Qubits $|1\rangle$ sind, ein Minuszeichen erhält. Wir tun dies mit einem mehrfach kontrollierten Z-Gate (implementiert als MCX-Gate, flankiert von Hadamard-Gates am Ziel).

Nach dem Anwenden des Phasen-Flips müssen wir zurückrechnen — alle Klauselauswertungsschritte in umgekehrter Reihenfolge rückgängig machen — um die Arbeitsbereich-Qubits auf $|0\rangle$ zurückzusetzen. Dies ist wesentlich, damit die Arbeitsbereich-Qubits für nachfolgende Iterationen des Grover-Operators sauber sind.

# Multi-controlled Z: flip phase if all workspace qubits are |1>
qc.h(a[2])
qc.mcx([a[0], a[1]], a[2])
qc.h(a[2])

# Uncompute clause 3: NOT(x0 XOR x1 XOR x2)
qc.x(a[2])
qc.cx(x[2], a[2])
qc.cx(x[1], a[2])
qc.cx(x[0], a[2])

# Uncompute clause 2: x1 XOR x2
qc.cx(x[2], a[1])
qc.cx(x[1], a[1])

# Uncompute clause 1: x0 XOR x1
qc.cx(x[1], a[0])
qc.cx(x[0], a[0])

qc.draw("mpl", style="iqp")

Dieser Schaltkreis ist unser Orakel: Er dreht die Phase des Daten-Qubit-Zustands um, der alle drei Minesweeper-Bedingungen erfüllt, und lässt die Arbeitsbereich-Qubits wieder in $|0\rangle$.

Jetzt konstruieren wir den vollständigen Grover-Operator aus diesem Orakel. Beachte das reflection_qubits-Argument: Wir übergeben nur die Daten-Qubits x, weil die Arbeitsbereich-Qubits nicht Teil des Suchraums sind. Ihre Aufgabe ist erledigt, sobald das Orakel angewendet wurde.

grover_op = grover_operator(qc, reflection_qubits=x)
grover_op.decompose(reps=0).draw(output="mpl", style="iqp")

Mit drei Daten-Qubits und einem Lösungszustand ist die optimale Anzahl von Grover-Iterationen $t \approx \frac{\pi}{4}\sqrt{8} - \frac{1}{2} \approx 1{,}7$, also verwenden wir zwei Iterationen. Wir wenden Hadamard-Gates auf die Daten-Qubits an, um die anfängliche Überlagerung zu erzeugen, setzen den Grover-Operator zweimal zusammen und messen nur die Daten-Qubits.

x = QuantumRegister(3, "x")
a = QuantumRegister(4, "a")
meas = ClassicalRegister(3, "meas")

qc = QuantumCircuit(x, a, meas)
# Create superposition over the data qubits only
qc.h(x)
# Apply 2 iterations of the Grover operator
qc.compose(grover_op.power(2), inplace=True)
# Measure only the data qubits
qc.measure(x, meas)
qc.decompose().draw(output="mpl", style="iqp")

Schritt 2: Problem für die Ausführung auf Quanten-Hardware optimieren

Wie zuvor transpilieren wir den Schaltkreis für das Ziel-Backend.

service = QiskitRuntimeService()
backend = service.least_busy(operational=True, simulator=False)
print(backend.name)

target = backend.target
pm = generate_preset_pass_manager(target=target, optimization_level=3)
circuit_isa = pm.run(qc)

Jetzt können wir die Tiefe des transpilierten Schaltkreises überprüfen. Da das Minesweeper-Orakel Arbeitsbereich-Qubits und mehrere CX-Gates verwendet, wird der transpilierte Schaltkreis tiefer sein als die in den vorherigen Aktivitäten.

print("The total depth is ", circuit_isa.depth())
print(
    "The depth of two-qubit gates is ",
    circuit_isa.depth(lambda instruction: instruction.operation.num_qubits == 2),
)

Schritt 3: Mit Qiskit-Primitiven ausführen

# To run on a real quantum computer (this was tested on a Heron r2 processor and
#  used 4 sec. of QPU time)

from qiskit_ibm_runtime import SamplerV2 as Sampler

sampler = Sampler(mode=backend)
sampler.options.default_shots = 10_000
result = sampler.run([circuit_isa]).result()
dist = result[0].data.meas.get_counts()

# To run on local simulator:
# from qiskit.primitives import StatevectorSampler as Sampler
# sampler = Sampler()
# result = sampler.run([qc]).result()
# dist = result[0].data.meas.get_counts()

Schritt 4: Nachbearbeitung und Rückgabe des Ergebnisses im gewünschten klassischen Format

plot_distribution(dist)

Der 101-Zustand sollte mit weit höherer Wahrscheinlichkeit auftreten als jeder andere, was darauf hinweist, dass sich Minen bei $x_0$ und $x_2$ befinden. Wir haben einen Quantencomputer verwendet, um ein winziges Minesweeper-Spiel zu lösen!

Natürlich sind die besten klassischen Algorithmen für Minesweeper besser als eine Brute-Force-Suche durch alle möglichen Minenkonfigurationen — sie nutzen die Struktur des Feldes. Der Grover-Algorithmus würde nur einen Vorteil bei extrem schwierigen Feldern bieten, die so gestaltet sind, dass sie maximal mehrdeutig sind, und selbst dann bedeutet die quadratische Beschleunigung, dass er mit exponentiellem Wachstum auf Dauer nicht Schritt halten kann. Aber die eigentliche Erkenntnis ist die Technik: Das Kodieren von Problembedingungen in ein Quanten-Orakel ist ein mächtiges Muster, das sich auf Erfüllbarkeitsprobleme, kombinatorische Optimierung und viele andere Bereiche erstreckt.

Fragen und kritische Konzepte:

Kritische Konzepte:

In diesem Modul haben wir einige Schlüsselmerkmale des Grover-Algorithmus gelernt:

• Während klassische unstrukturierte Suchalgorithmen eine Anzahl von Abfragen erfordern, die linear in der Größe des Raums, $N,$ skaliert, erfordert der Grover-Algorithmus eine Anzahl von Abfragen, die wie $\sqrt{N}$ skaliert.
• Der Grover-Algorithmus beinhaltet das Wiederholen einer Reihe von Operationen (allgemein als "Grover-Operator" bezeichnet) eine Anzahl von Malen $t,$ die gewählt wird, um die Zielzustände optimal wahrscheinlich zu messen.
• Der Grover-Algorithmus kann mit weniger als $t$ Iterationen ausgeführt werden und dennoch die Zielzustände amplifizieren.
• Der Grover-Algorithmus passt in das Abfragemodell der Berechnung und macht am meisten Sinn, wenn eine Person die Suche kontrolliert und eine andere das Orakel kontrolliert/konstruiert. Er kann auch als Unterroutine in anderen Quantenberechnungen nützlich sein.
• Ein Orakel kann aus Problembedingungen aufgebaut werden, anstatt aus dem Wissen um die Lösung, wie am Minesweeper-Beispiel demonstriert.

Wahr/Falsch-Fragen:

1. W/F Der Grover-Algorithmus bietet eine exponentielle Verbesserung gegenüber klassischen Algorithmen in der Anzahl der Abfragen, die benötigt werden, um einen einzelnen markierten Zustand in unstrukturierter Suche zu finden.

2. W/F Der Grover-Algorithmus funktioniert, indem er iterativ die Wahrscheinlichkeit erhöht, dass ein Lösungszustand gemessen wird.

3. W/F Je öfter du den Grover-Operator iterierst, desto höher die Wahrscheinlichkeit, einen Lösungszustand zu messen.

MC-Fragen:

1. Wähle die beste Option, um den Satz zu vervollständigen. Die beste Strategie, um den Grover-Algorithmus auf modernen Quantencomputern erfolgreich zu verwenden, besteht darin, den Grover-Operator zu iterieren...

• a. Nur einmal.
• b. Immer $t$ Mal, um die Wahrscheinlichkeitsamplitude des Lösungszustands (der Lösungszustände) zu maximieren.
• c. Bis zu $t$ Mal, obwohl weniger ausreichen kann, um Lösungszustände hervorstechen zu lassen.
• d. Nicht weniger als 10 Mal.

2. Ein Phasenabfrage-Schaltkreis wird hier gezeigt, der als Orakel fungiert, um einen bestimmten Zustand mit einem Phasen-Flip zu markieren. Welche der folgenden Zustände werden von diesem Schaltkreis markiert?

• a. $|0000\rangle$
• b. $|0101\rangle$
• c. $|0110\rangle$
• d. $|1001\rangle$
• e. $|1010\rangle$
• f. $|1111\rangle$

3. Angenommen, du möchtest nach drei markierten Zuständen aus einer Menge von 128 suchen. Was ist die optimale Anzahl von Iterationen des Grover-Operators, um die Amplituden der markierten Zustände zu maximieren?

• a. 1
• b. 3
• c. 5
• d. 6
• e. 20
• f. 33

Diskussionsfragen:

1. Welche anderen Probleme könntest du als eine Grover-Suche formulieren? Denke an Probleme, bei denen es schwierig ist, eine Lösung zu finden, aber leicht, eine zu überprüfen.

2. Kannst du irgendwelche Probleme beim Skalieren des Grover-Algorithmus auf modernen Quantencomputern sehen?