Grover-Algorithmus

Für dieses Modul "Qiskit im Klassenzimmer" müssen die Schüler eine funktionierende Python Umgebung mit den folgenden Paketen installiert 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, lesen Sie die Anleitung Qiskit installieren. Um Aufträge auf echten Quantencomputern ausführen zu können, müssen die Schüler ein Konto bei IBM Quantum® einrichten, indem sie die Schritte in der Anleitung zur Einrichtung Ihres IBM Cloud Kontos befolgen.

Dieses Modul wurde getestet und verbrauchte 12 Sekunden QPU-Zeit. Dies ist eine Schätzung nach bestem Wissen und Gewissen; Ihr tatsächlicher Verbrauch kann davon abweichen.

# 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 sich mit dem Problem der unstrukturierten Suche befasst: Wie schnell kann man bei einer Menge von $N$ und einer Möglichkeit zu überprüfen, ob ein bestimmter Gegenstand der gesuchte ist, den gewünschten Gegenstand finden? Wenn die Daten unsortiert sind und es keine Struktur gibt, die ausgenutzt werden kann, besteht der beste Ansatz darin, jedes Element einzeln zu überprüfen, was zu einer Abfragekomplexität von $O(N)$ führt - im Durchschnitt müssen Sie etwa die Hälfte der Elemente überprüfen, bevor Sie das Ziel finden.

Der 1996 von Lov Grover vorgestellte Grover-Algorithmus zeigt, wie ein Quantencomputer dieses Problem viel effizienter lösen kann. Er benötigt nur $O(\sqrt{N})$ Schritte, um den markierten Gegenstand mit hoher Wahrscheinlichkeit zu finden. Dies bedeutet eine quadratische Beschleunigung gegenüber klassischen Methoden, was bei großen Datenmengen von Bedeutung ist.

Der Algorithmus arbeitet in folgendem Kontext:

• Problemstellung: Sie haben 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 Blackbox bezeichnet, da man nur durch Abfragen von $f(x)$ etwas über die Daten erfahren kann.
• Nützlichkeit von Quanten: Während klassische Algorithmen für dieses Problem im Durchschnitt $N/2$ Abfragen benötigen, kann der Algorithmus von Grover die Lösung in etwa $\pi\sqrt{N}/4$ Abfragen finden, was für große $N$ sehr viel schneller ist.
• Wie es funktioniert (in groben Zügen):
  • Der Quantencomputer erzeugt zunächst eine Überlagerung aller möglichen Zustände, die alle möglichen Elemente auf einmal darstellen.
  • Dann wendet es wiederholt eine Folge von Quantenoperationen an (die Grover-Iteration), die die Wahrscheinlichkeit der richtigen Antwort erhöht und die der anderen verringert.
  • Nach genügend Iterationen ergibt die Messung des Quantenzustands mit hoher Wahrscheinlichkeit die richtige Antwort.

Hier ist ein sehr einfaches Diagramm von Grovers Algorithmus, das viele Nuancen überspringt. Ein ausführlicheres Diagramm finden Sie in diesem Dokument.

Zu Grovers Algorithmus sind ein paar Dinge zu beachten:

• Sie ist optimal für die unstrukturierte Suche: Kein Quantenalgorithmus kann das Problem mit weniger als $O(\sqrt{N})$ Abfragen lösen.
• Im Gegensatz zu einigen anderen Quantenalgorithmen (z. B. Shors Algorithmus zum Faktorisieren) bietet er nur eine quadratische, nicht exponentielle Beschleunigung.
• Dies hat praktische Auswirkungen, wie z. B. die mögliche Beschleunigung von Brute-Force-Angriffen auf kryptografische Systeme, auch wenn die Beschleunigung nicht ausreicht, um die meisten modernen Verschlüsselungen allein zu knacken.

Für Studenten, die mit grundlegenden Computerkonzepten und Abfragemodellen vertraut sind, bietet Grovers Algorithmus eine klare Veranschaulichung, wie Quantencomputing klassische Ansätze für bestimmte Probleme übertreffen kann, selbst wenn die Verbesserung "nur" quadratisch ist. Es dient auch als Ausgangspunkt für das Verständnis fortgeschrittener Quantenalgorithmen und des breiteren Potenzials der Quanteninformatik.

Die Amplitudenverstärkung ist ein universeller Quantenalgorithmus bzw. ein Unterprogramm, mit dem eine quadratische Beschleunigung gegenüber einer Handvoll klassischer Algorithmen erzielt werden kann. Grovers Algorithmus war der erste, der diese Beschleunigung bei unstrukturierten Suchproblemen demonstrierte. Die Formulierung eines Grover-Suchproblems erfordert eine Orakelfunktion, die einen oder mehrere Zustände der Berechnungsbasis als die Zustände markiert, die wir finden wollen, und eine Verstärkungsschaltung, die die Amplitude der markierten Zustände erhöht und folglich die übrigen Zustände unterdrückt.

Hier zeigen wir, wie man Grover-Orakel konstruiert und wie man mithilfe der GroverOperator aus der Qiskit-Schaltkreisbibliothek auf einfache Weise eine Grover-Suchinstanz einrichtet. Die Primitive Sampler „ IBM Quantum “ ermöglicht die nahtlose Ausführung von Grover-Schaltungen.

Theorie

Angenommen, es gibt eine Funktion $f$, die binäre Zeichenketten auf eine einzige binäre Variable abbildet, was bedeutet

Ein auf $\Sigma^6$ definiertes Beispiel ist

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

Ihre Aufgabe ist es, Quantenzustände zu finden, die denjenigen Argumenten $x$ von $f(x)$ entsprechen, die auf 1 abgebildet werden. Mit anderen Worten: Finden Sie alle $\{x_1\}\in \Sigma^n$, so dass $f(x_1)=1$ (oder wenn es keine Lösung gibt, melden Sie das). Nicht-Lösungen würden wir als $x_0$ bezeichnen. Natürlich werden wir dies auf einem Quantencomputer unter Verwendung von Quantenzuständen tun, daher ist es sinnvoll, diese binären Zeichenfolgen als Zustände auszudrücken:

Unter Verwendung der Quantenzustandsnotation (Dirac) 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 Nicht-Lösungen mit $\{|x_0\rangle\}$ bezeichnet werden.

Wir können uns die Funktion $f$ so vorstellen, als würde sie von einem Orakel bereitgestellt: einer Blackbox, die wir abfragen können, um ihre Auswirkung auf einen Zustand $|x\rangle$ zu ermitteln. In der Praxis kennen wir die Funktion zwar oft, doch ihre Umsetzung kann sehr kompliziert sein, weshalb es wichtig sein könnte, die Anzahl der Abfragen oder Anwendungen von $f$ zu reduzieren. Alternativ können wir uns ein Paradigma vorstellen, in dem eine Person ein von einer anderen Person gesteuertes Orakel abfragt, sodass wir die Funktion des Orakels nicht kennen, sondern lediglich wissen, wie es bei bestimmten Zuständen auf Abfragen reagiert.

Es handelt sich um ein "unstrukturiertes Suchproblem", da $f$ nichts Besonderes enthält, das uns bei der Suche hilft. Die Ausgaben sind nicht sortiert, und es ist nicht bekannt, dass die Lösungen in Gruppen zusammengefasst werden usw. Betrachten Sie alte, papierne Telefonbücher als eine Analogie. Diese unstrukturierte Suche wäre wie das Durchsuchen nach einer bestimmten Zahl und nicht wie das Durchsuchen einer alphabetisch geordneten Liste von Namen.

Wird eine einzelne Lösung gesucht, erfordert dies klassischerweise eine Anzahl von Abfragen, die linear zu $N$ ist. Natürlich kann es sein, dass Sie bereits beim ersten Versuch eine Lösung finden, oder dass Sie bei den ersten $N-1$ Versuchen keine Lösung finden, sodass Sie die Eingabe $N^{th}$ abfragen müssen, um festzustellen, ob es überhaupt eine Lösung gibt. Da die Funktionen keine Struktur aufweisen, die sich ausnutzen lässt, benötigen Sie im Durchschnitt $N/2$ Versuche. Grovers Algorithmus erfordert eine Anzahl von Abfragen oder Berechnungen von $f$, die wie $\sqrt{N}$ skaliert.

Skizze der Schaltkreise in Grovers Algorithmus

Eine vollständige mathematische Darstellung des Grover-Algorithmus findet sich beispielsweise in Fundamentals of quantum algorithms, einem Kurs von John Watrous auf IBM Quantum Learning. Eine Kurzfassung findet sich in einem Anhang am Ende dieses Moduls. Doch zunächst wollen wir nur die Gesamtstruktur des Quantenschaltkreises betrachten, der den Grover-Algorithmus implementiert.

Der Algorithmus von Grover lässt sich in die folgenden Phasen unterteilen:

• Vorbereitung einer anfänglichen Superposition (Anwendung von Hadamard-Gattern auf alle Qubits)
• "Markierung" des/der Zielzustände(s) mit einem Phasensprung
• Eine "Diffusions"-Stufe, in der Hadamard-Gates und ein Phasenflip auf alle Qubits angewendet werden.
• Mögliche Wiederholungen der Markierungs- und Diffusionsphasen, um die Wahrscheinlichkeit der Messung des Zielzustands zu maximieren
• Messwert

Häufig werden das Markierungsgatter $Z_f$ und die Diffusionsschichten, bestehend aus $H$, $Z_{\text{OR}}$ und $H$, gemeinsam als „Grover-Operator“ bezeichnet. In dieser Abbildung ist nur eine einzige Wiederholung des Grover-Operators dargestellt.

Hadamard-Gatter $H$ sind bekannt und werden in der Quanteninformatik häufig verwendet. Das Hadamard-Gatter erzeugt Überlagerungszustände. Im Einzelnen ist sie definiert durch

Seine Funktionsweise bei jedem anderen Zustand wird durch die Linearität bestimmt. Insbesondere ermöglicht uns eine Schicht aus Hadamard-Gattern, vom Anfangszustand, in dem sich alle Qubits im Zustand $|0\rangle$ befinden (bezeichnet als $|0\rangle^{\otimes n}$ ), zu einem Zustand zu gelangen, in dem jedes Qubit mit einer bestimmten Wahrscheinlichkeit entweder im Zustand $|0\rangle$ oder im Zustand $|1\rangle$ gemessen wird; dadurch können wir den Raum aller möglichen Zustände auf eine andere Weise untersuchen als bei der klassischen Informatik.

Eine wichtige Folgeeigenschaft des Hadamard-Gatters ist, dass ein zweiter Eingriff solche Überlagerungszustände aufheben kann:

Das wird gleich noch wichtig sein.

Überprüfen Sie Ihr Verständnis

Zeigen Sie ausgehend von der Definition des Hadamard-Gatters, dass eine zweite Anwendung des Hadamard-Gatters solche Überlagerungen wie oben behauptet aufhebt.

• Antwort

  Wenn wir „ $H$ “ auf die Zustände „ $|+\rangle$ “ und „ $|+\rangle$ “ anwenden, erhalten wir:

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

Das Tor $Z_\text{OR}$ ist weniger verbreitet und wird wie folgt definiert

Das Tor $Z_f$ schließlich ist definiert durch

Dies hat zur Folge, dass $Z_f$ das Vorzeichen eines Zielzustands, für den $f(x) = 1$ gilt, umkehrt und andere Zustände unberührt lässt.

Auf einer sehr hohen, abstrakten Ebene kann man sich die Schritte in der Schaltung folgendermaßen vorstellen:

• Erste Hadamard-Schicht: versetzt die Qubits in eine Überlagerung aller möglichen Zustände.
• $Z_f$ : Markieren Sie den/die Zielzustand(e) durch ein vorangestelltes "-"-Zeichen. Dadurch ändern sich die Messwahrscheinlichkeiten nicht sofort, aber es ändert sich, wie sich der Zielzustand in den nachfolgenden Schritten verhalten wird.
• Eine weitere Hadamard-Schicht: Das im vorherigen Schritt eingeführte „-“-Zeichen verändert das Vorzeichen einiger Terme zueinander. Da Hadamard-Gatter eine Mischung von Rechenzuständen $(|0\rangle+|1\rangle)/\sqrt{2}$ in einen Rechenzustand $|0\rangle$ umwandeln und $(|0\rangle-|1\rangle)/\sqrt{2}$ in $|1\rangle$ umwandeln, kann dieser relative Vorzeichenunterschied nun eine Rolle dabei spielen, welche Zustände gemessen werden.
• Eine letzte Schicht von Hadamard-Gates wird aufgetragen, und dann werden Messungen durchgeführt. Wie das funktioniert, werden wir im nächsten Abschnitt genauer sehen.

Beispiel

Um besser zu verstehen, wie der Grover-Algorithmus funktioniert, wollen wir ein kleines Beispiel mit zwei Qubits durchspielen. Für diejenigen, die sich nicht mit Quantenmechanik und Dirac-Notation befassen, kann dies als fakultativ betrachtet werden. Aber für diejenigen, die mit Quantencomputern arbeiten wollen, ist es sehr empfehlenswert.

Hier ist der Schaltplan mit den Quantenzuständen an verschiedenen Stellen beschriftet. Beachten Sie, dass es bei nur zwei Qubits nur vier mögliche Zustände gibt, die unter allen Umständen gemessen werden können: $|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 jedes Satzes von Quantengattern, einschließlich des Orakels, durchspielen und sehen, welche Verteilung der möglichen Zustände zum Zeitpunkt der Messung herauskommt. Ganz am Anfang haben wir

Unter Verwendung der Definition von Hadamard-Toren ergibt sich

Nun markiert das Orakel den Zielzustand:

Beachten Sie, dass in diesem Zustand alle vier möglichen Ergebnisse die gleiche Wahrscheinlichkeit haben, gemessen zu werden. Sie alle haben ein Gewicht in der Größenordnung von $1/2$, was bedeutet, dass die Wahrscheinlichkeit, dass sie gemessen werden, jeweils $|1/2|^2=1/4$ beträgt. Auch wenn der Zustand $|01\rangle$ als „-“ Phase markiert ist, hat dies bislang noch nicht zu einer erhöhten Wahrscheinlichkeit geführt, diesen Zustand zu messen. Wir fahren fort, indem wir die nächste Schicht von Hadamard-Gattern anwenden.

Kombiniert man gleiche Begriffe, ergibt sich

Jetzt dreht $Z_{\text{OR}}$ das Vorzeichen auf alle Staaten außer $|00\rangle$ um:

Und schließlich wird die letzte Schicht der Hadamard-Tore angewendet:

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

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

Dieses Zwei-Qubit-Beispiel war ein besonders sauberer Fall; Grovers Algorithmus wird nicht immer eine 100%ige Chance bieten, den Zielzustand zu messen. Vielmehr wird dadurch die Wahrscheinlichkeit der Messung des Zielzustands erhöht. 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 obige Beispiel mit zwei Qubits hat gezeigt, wie die Algebra in einem einfachen Fall funktioniert, doch es gibt eine viel intuitivere Möglichkeit, Grovers Algorithmus zu verstehen: als Abfolge geometrischer Spiegelungen in einer zweidimensionalen Ebene. Im Folgenden beschreiben wir dieses Bild. Weitere Informationen finden Sie auch in John Watrous’ Kurs „Grundlagen der Quantenalgorithmen “.

Das Flugzeug vorbereiten. Wir können den anfänglichen Überlagerungszustand $|\psi\rangle$ in zwei Komponenten zerlegen. Den korrekten Zustand – den, nach dem wir suchen – bezeichnen wir als „ $|A_1\rangle$ “. Alle anderen Zustände, die wir hier zusammenfassen, nennen wir „ $|A_0\rangle$ “. Per Definition stehen „ $|A_1\rangle$ “ und „ $|A_0\rangle$ “ senkrecht zueinander, sodass wir sie als senkrechte Achsen in einem abstrakten zweidimensionalen Raum darstellen können. Da $|\psi\rangle$ eine Linearkombination dieser beiden Komponenten ist, steht sie in einem kleinen Winkel $\theta$ zur Achse $|A_0\rangle$ – nahe bei $|A_0\rangle$, da sich zu Beginn nur ein winziger Bruchteil des Zustands in der richtigen Komponente $|A_1\rangle$ befindet.

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

spiegelt jeden Zustand entlang der durch $|v\rangle$ definierten Achse wider. Um zu verstehen, warum das so ist, betrachten wir zwei Fälle: Ein Zustand entlang $|v\rangle$ bleibt unverändert, während bei einem Zustand senkrecht zu $|v\rangle$ das Vorzeichen umgekehrt wird. Jeder andere Zustand lässt sich in diese beiden Komponenten zerlegen, und der Operator wirkt entsprechend auf jede einzelne ein – was genau einer Spiegelung an $|v\rangle$ entspricht.

Es zeigt sich, dass sowohl der Orakel- als auch der Diffusionsschritt in Grovers Algorithmus in diesem geometrischen Modell als Spiegelungen dargestellt werden können.

Das Orakel als Spiegelbild. Das Orakel kehrt das Vorzeichen des Zustands „ $|A_1\rangle$ “ um und lässt alles andere unverändert. Das entspricht einer Spiegelung an der Achse „ $|A_0\rangle$ “.

Diffusion als Reflexion. Es ist etwas schwieriger zu erkennen, dass der Diffusionsoperator ebenfalls eine Spiegelung ist. Der Diffusionsoperator lautet

$Z_{\text{OR}}$ an sich ist eine Spiegelung des Nullzustands, da sie 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 bewirken praktisch einen Basiswechsel, der die Spiegelungsachse transformiert. Man erinnere sich daran, dass $H^{\otimes n}$ die Funktion $|0\rangle^{\otimes n}$ auf die gleichmäßige Überlagerung $|u\rangle = \frac{1}{\sqrt{N}}\sum_{x}|x\rangle$ abbildet. Da die Hadamard-Transformation ihre eigene Umkehrfunktion ist, lautet der vollständige Ausdruck

was eine Reflexion über $|u\rangle$ ist. Da $|u\rangle$ sehr nahe an $|\psi\rangle$ liegt (beide befinden sich fast auf einer Linie mit $|A_0\rangle$ ), lenkt diese zweite Reflexion den Zustand in einen Winkel $2\theta$ von seinem Ausgangspunkt aus.

Drehung um $2\theta$. Die kombinierte Wirkung dieser beiden Reflexionen ergibt eine Drehung um $2\theta$ in Richtung $|A_1\rangle$. Jede aufeinanderfolgende Iteration des Grover-Operators dreht 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 drehen, was einer Drehung um insgesamt etwa $\pi/2$ Radiant (eine Vierteldrehung) entspricht. Wenn jede Iteration einen Beitrag von $2\theta$ leistet, gilt für die optimale Anzahl von Iterationen $t$

Für eine einzelne Lösung unter den Bedingungen $N$ ist der Anfangswinkel $\theta \approx \sin^{-1}(1/\sqrt{N}) \approx 1/\sqrt{N}$ (für große $N$ ). Nach Einsetzen ergibt sich:

Hier liegt der Ursprung der berühmten Beschleunigung durch „ $\sqrt{N}$ “: Wir benötigen lediglich $O(\sqrt{N})$ Iterationen, um das Ziel zu erreichen, anstatt der $O(N)$ Prüfungen, die eine klassische Suche erfordern würde.

Allgemeiner gesagt: Wenn es unter den insgesamt $N$ Zuständen $|A_1|$ Lösungszustände gibt, beträgt die optimale Anzahl von Iterationen

Beachten Sie, dass bei zu vielen Iterationen die Drehung über den Punkt „ $|A_1\rangle$ “ hinausgeht und die Wahrscheinlichkeit, den Zielzustand zu finden, wieder abnimmt. Es ist wichtig, die richtige Anzahl von Iterationen zu finden, auch wenn die experimentell optimale Anzahl bei rauschbehafteter Quantenhardware von dieser idealen Formel abweichen kann.

Warum ist Grovers Algorithmus nützlich?

An dieser Stelle fragen Sie sich vielleicht: Wir haben gerade ein Orakel erstellt, das einen Zielzustand kennzeichnet – aber um es zu erstellen, mussten wir den Zielzustand kennen. Wonach suchen wir eigentlich?

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

• Das Abfragemodell ist ein theoretisches Instrument. Das Abfragemodell der Informatik war nie darauf ausgelegt, direkt in der Praxis anwendbar zu sein. Sein Zweck besteht darin, uns eine übersichtliche Methode zur Analyse der algorithmischen Komplexität an die Hand zu geben, indem ein Problem in zwei Teile unterteilt wird: das Orakel und alles andere. Wie aufwendig ist die Suche, wenn man bedenkt, dass die Überprüfung kostenlos ist? Wie verhält sich die Anzahl der Abfragen im Verhältnis zur Größe der Eingabe? Das sind nützliche Fragen, auch wenn kein reales System genau so funktioniert.

• Man kann sich das auch als eine Aufgabe für zwei Personen vorstellen: Eine Person kennt den Zielzustand und erstellt das Orakel; die Aufgabe der anderen Person besteht darin, die Antwort zu finden, indem sie das Orakel als Blackbox nutzt, ohne einen Blick hineinzuwerfen. In der folgenden Aufgabe 2 wirst du genau das gemeinsam mit einem Partner tun.

• Die Amplitudenverstärkung ist eine vielseitig einsetzbare Unterroutine. Auch wenn diese erste Demonstration auf den ersten Blick wie ein Zirkelschluss erscheint, taucht der zugrunde liegende Mechanismus – die sogenannte Amplitudenverstärkung – in der Quanteninformatik immer wieder auf. Was wir hier eigentlich entwickeln, ist ein Gespür für ein Werkzeug, das in vielen komplexeren Quantenalgorithmen als Unterprogramm auftritt.

• Es gibt Probleme, bei denen man ein Orakel erstellen kann, ohne die Antwort zu kennen. Die zentrale Erkenntnis ist, dass es eine ganze Klasse von Problemen gibt, für die es sehr schwer ist, eine Lösung zu finden, bei denen es jedoch sehr einfach ist, zu überprüfen, ob eine bestimmte Lösung richtig ist. Das Faktorisieren ist ein Beispiel dafür: Bei einem Produkt aus zwei großen Primzahlen ist es äußerst schwierig, diese Primzahlen zu ermitteln, aber sobald man sie kennt, kann man sie einfach miteinander multiplizieren, um das Ergebnis zu überprüfen. (Wir haben zwar einen besseren Algorithmus als den von Grover speziell für die Faktorisierung – siehe Shors Algorithmus –, doch das ist bei weitem nicht das einzige Problem dieser Funktion.) Sudoku, die Lösung von Gleichungssystemen und sogar das klassische Spiel „Minesweeper“ sind allesamt Probleme, die schwer zu lösen, aber leicht zu überprüfen sind.

Warum ist das relevant? Das bedeutet, dass wir alle Bedingungen und Anforderungen kennen, die eine Lösung erfüllen muss, und dass wir diese Anforderungen in einen Quantenschaltkreis kodieren können, der als Orakel dient – auch wenn wir die Lösung selbst nicht kennen. Grovers Algorithmus wird es für uns finden.

Lassen Sie uns vor diesem Hintergrund einige Beispiele durchgehen. Wir beginnen mit einem Beispiel, bei dem der Lösungszustand klar definiert ist, damit wir der Logik des Algorithmus folgen können. Anschließend wenden wir uns einer Übung für zwei Teilnehmer zu und schließlich einem Beispiel, bei dem das Orakel nicht auf der Grundlage der Antwort, sondern anhand der Problemvorgaben aufgebaut wird.

Allgemeine Einfuhren und Vorgehensweise

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 einen Rahmen für Quantencomputer verwenden, der als "Qiskit-Muster" bekannt ist und Arbeitsabläufe in die folgenden Schritte unterteilt:

• Schritt 1: Abbildung klassischer Eingaben auf ein Quantenproblem
• Schritt 2: Optimieren des Problems für die Quantenausführung
• Schritt 3: Ausführung mithilfe von „ IBM Quantum “-Primitiven
• Schritt 4: Nachbearbeitung und klassische Analyse

Im Allgemeinen werden wir diese Schritte befolgen, auch wenn wir sie nicht immer explizit kennzeichnen.

Aktivität 1: Finden Sie einen einzigen vorgegebenen Zielzustand

Schritt 1: Klassische Eingaben einem Quantenproblem zuordnen

Wir brauchen das Phasenabfrage-Gate, um eine Gesamtphase (-1) auf Lösungszustände zu legen und die Nicht-Lösungszustände unberührt zu lassen. Anders ausgedrückt: Grovers Algorithmus erfordert ein Orakel, das einen oder mehrere markierte Rechenbasiszustände angibt, wobei "markiert" einen Zustand mit einer Phase von -1 bedeutet. Dies geschieht mit Hilfe eines kontrollierten Z-Gatters oder seiner mehrfach kontrollierten Verallgemeinerung über $N$ qubits. Um zu sehen, wie das funktioniert, betrachten wir ein konkretes Beispiel für eine Bitfolge {110}. Wir möchten eine Schaltung, die auf einen Zustand $|\psi\rangle = |q_2,q_1,q_0\rangle$ einwirkt und eine Phase anwendet, wenn $|\psi\rangle = |011\rangle$ (wobei wir die Reihenfolge der binären Zeichenkette aufgrund der Notation in Qiskit umgedreht haben, die das niederwertigste (oft 0) Qubit auf die rechte Seite legt).

Wir wollen also eine Schaltung $Z_f$, die Folgendes leistet

Mit dem Multiple-Control-Multiple-Target-Gate (MCMTGate) können wir ein Z-Gate anwenden, das von allen Qubits gesteuert wird (und die Phase umkehren, wenn sich alle Qubits im Zustand $|1\rangle$ befinden). 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-Gatter anwenden, dann das mehrfach gesteuerte Z-Gatter, und dann ein weiteres X-Gatter anwenden, um unsere Änderung rückgängig zu machen. Die Website MCMTGate sieht folgendermaßen aus:

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

Output:

Man beachte, dass viele Qubits am Kontrollprozess beteiligt sein können (hier sind es drei Qubits), aber kein einzelnes Qubit als Ziel bezeichnet wird. Das liegt daran, dass der gesamte Zustand ein "-"-Vorzeichen erhält (Phasenkippung); das Gatter wirkt sich auf alle Qubits gleichermaßen aus. Dies unterscheidet sich von vielen anderen Gattern mit mehreren Qubits, wie z. B. dem CX -Gatter, das ein einzelnes Kontroll-Qubit und ein einzelnes Ziel-Qubit hat.

Im folgenden Code definieren wir ein Phasenabfrage-Gatter (oder Orakel), das genau das tut, was wir oben beschrieben haben: Es markiert einen oder mehrere Eingabe-Basiszustände, die durch ihre Bitstring-Darstellung definiert sind. Das MCMT-Gatter wird zur Implementierung des mehrfach gesteuerten Z-Gatters verwendet.

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

Nun wählen wir einen bestimmten "markierten" Zustand als Ziel und wenden die soeben definierte Funktion an. Mal sehen, was für ein Kreislauf dabei entsteht.

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

Output:

Befinden sich die Qubits 1–3 im Zustand „ $|1\rangle$ “ und ist Qubit 0 anfänglich im Zustand „ $|0\rangle$ “, so wird durch das erste X-Gatter Qubit 0 in den Zustand „ $|1\rangle$ “ umgedreht, und alle Qubits befinden sich im Zustand „ $|1\rangle$ “. Das bedeutet, dass das MCMT-Gatter je nach Wunsch eine allgemeine Vorzeichenänderung oder Phasenumkehr bewirkt. In allen anderen Fällen befinden sich entweder die Qubits 1–3 im Zustand „ $|0\rangle$ “ oder das Qubit 0 wird in den Zustand „ $|0\rangle$ “ umgeschaltet, und die Phasenumkehr wird nicht angewendet. Wir sehen, dass diese Schaltung tatsächlich unseren gewünschten Zustand $|0111\rangle$ oder die Bitfolge darstellt {1110}.

Der vollständige Grover-Operator besteht aus dem Phasenabfrage-Gate (Orakel), Hadamard-Schichten und dem $Z_\text{OR}$ -Operator. Wir können die eingebaute grover_operator verwenden, um dies aus dem oben definierten Orakel zu konstruieren.

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

Output:

Wie wir anhand der obigen geometrischen Darstellung besprochen haben, muss der Grover-Operator möglicherweise mehrmals angewendet werden. Die optimale Anzahl von Iterationen $t$, um die Amplitude des Zielzustands ohne Rauschen zu maximieren, beträgt

wobei $|A_1|$ die Anzahl der Lösungszustände und $N=2^n$ die Gesamtzahl der Zustände ist. Auf modernen, rauschbehafteten Quantencomputern kann die experimentell optimale Anzahl von Iterationen zwar abweichen – hier berechnen und verwenden wir jedoch diese theoretische, optimale Anzahl 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)

Output:

3

Konstruieren wir nun eine Schaltung, die die anfänglichen Hadamard-Gatter enthält, um eine Überlagerung aller möglichen Zustände zu erzeugen, und wenden wir den Grover-Operator so oft wie möglich 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")

Output:

Wir haben unseren Grover-Kreislauf aufgebaut!

Schritt 2: Optimierung des Problems für die Ausführung auf Quantenhardware

Wir haben unsere abstrakte Quantenschaltung definiert, aber wir müssen sie in Form von Gattern umschreiben, die in dem Quantencomputer, den wir tatsächlich verwenden wollen, vorhanden sind. Wir müssen auch festlegen, welche Qubits des Quantencomputers verwendet werden sollen. Aus diesen und anderen Gründen müssen wir unseren Schaltkreis nun umsetzen. Lassen Sie uns zunächst den Quantencomputer spezifizieren, den wir verwenden wollen.

Unten finden Sie einen Code, mit dem Sie Ihre Anmeldedaten bei der ersten Verwendung speichern können. Achten Sie darauf, diese Informationen aus dem Notebook zu löschen, nachdem Sie es in Ihrer Umgebung gespeichert haben, damit Ihre Anmeldedaten nicht versehentlich weitergegeben werden, wenn Sie das Notebook freigeben. Weitere Anleitungen finden Sie unter Einrichten Ihres IBM Cloud Kontos und Initialisieren des Dienstes in einer nicht vertrauenswürdigen Umgebung.

# 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

Output:

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 voreingestellten Passmanager, um unsere Quantenschaltung für das gewä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")

An dieser Stelle sei darauf hingewiesen, dass die Tiefe des transponierten Quantenkreises 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),
)

Output:

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

Das sind selbst für diesen einfachen Fall recht große Zahlen. Da alle Quantengatter (und insbesondere Zwei-Qubit-Gatter) mit Fehlern behaftet sind und Rauschen unterliegen, würde eine Reihe von über 100 Zwei-Qubit-Gattern nichts als Rauschen ergeben, wenn die Qubits nicht extrem leistungsfähig wären. Mal sehen, wie sie abschneiden.

Schritt 3: Ausführung mithilfe von „ IBM Quantum “-Primitiven

Wir möchten viele Messungen durchführen und herausfinden, welcher Zustand am wahrscheinlichsten ist. Eine solche Amplitudenverstärkung stellt ein Abtastproblem dar, das sich für die Ausführung mit der Primitivfunktion „ IBM QuantumSampler “ eignet.

Beachten Sie, dass die Methode run() „ IBM Quantum “ unter SamplerV2 ein iterierbares Objekt aus primitiven vereinheitlichten Blöcken (PUBs) erwartet. Für „Sampler“ ist jede „ PUB “ eine iterierbare Struktur im Format (Schaltung, Parameterwerte). Allerdings benötigt man zumindest eine Liste von Quantenschaltungen.

# 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 den größtmöglichen Nutzen aus dieser Erfahrung zu ziehen, empfehlen wir Ihnen dringend, Ihre Experimente auf den echten Quantencomputern von IBM Quantum durchzuführen. Wenn Sie jedoch Ihre QPU-Zeit ausgeschöpft haben, können Sie die folgenden Zeilen auskommentieren, um diese Aktivität mithilfe eines Simulators durchzuführen.

# 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

Nun können wir die Ergebnisse unserer Stichprobe in einem Histogramm darstellen.

plot_distribution(dist)

Output:

Wir sehen, dass Grovers Algorithmus den gewünschten Zustand mit der weitaus höchsten Wahrscheinlichkeit liefert, mindestens eine Größenordnung höher als andere Optionen. In der nächsten Aktivität werden wir den Algorithmus auf eine Art und Weise verwenden, die mehr mit dem zweiseitigen Arbeitsablauf eines Abfragealgorithmus vereinbar ist.

Überprüfen Sie Ihr Verständnis

Wir haben gerade nach einer einzigen Lösung in einer Menge von $2^4=16$ möglichen Zuständen gesucht. Wir haben die optimale Anzahl der Wiederholungen des Grover-Operators auf $t=3$ festgelegt. Hätte sich diese optimale Anzahl erhöht oder verringert, wenn wir (a) nach einer von mehreren Lösungen oder (b) nach einer einzigen Lösung in einem Raum mit mehr möglichen Zuständen gesucht hätten?

• Antwort

  Solange die Anzahl der Lösungen im Vergleich zum gesamten Lösungsraum klein ist, können wir die Sinusfunktion um kleine Winkel erweitern und Folgendes verwenden

  $$(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) Aus dem obigen Ausdruck geht hervor, dass eine Erhöhung der Anzahl der Lösungszustände zu einer Verringerung der Anzahl der Iterationen führen würde. Sofern der Bruchteil $\frac{|\mathcal{A}_1|}{N}$ noch klein ist, lässt sich beschreiben, wie sich $t$ verringern würde: $t~\frac{1}{\sqrt{|\mathcal{A}_1|}}$.

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

Nehmen wir an, wir könnten die Größe des Ziel-Bitstrings beliebig erhöhen und hätten immer noch 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önnen, um den Zielzustand zuverlässig zu finden?

• Antwort

  Anzahl Nehmen wir an, wir wiederholen die erste Aktivität mit 20 Qubits und lassen den Quantenschaltkreis mehrmals laufen num_shots = 10,000. 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. Wäre die Wahrscheinlichkeit, den Zielzustand zu messen, zehnmal so hoch wie die der Nichtlösungen (und die Wahrscheinlichkeit jeder Nichtlösung entsprechend leicht verringert), so bestünde nur eine Wahrscheinlichkeit von etwa 10 %, den Zielzustand auch nur einmal zu messen. Es wäre höchst unwahrscheinlich, den Zielzustand mehrfach zu messen, was ihn von den vielen zufällig erhaltenen Nichtlösungszuständen ununterscheidbar machen würde. Die gute Nachricht ist, dass wir mit Hilfe von Fehlerunterdrückung und -minderung sogar noch realitätsnähere Ergebnisse erzielen können.

Aktivität 2: Ein präziser Algorithmus-Workflow für Abfragen

Wir beginnen diese Aktivität genauso wie die erste, nur dass ihr euch jetzt mit einem anderen Qiskit-Enthusiasten zusammentut. Sie wählen einen geheimen Bitstring, und Ihr Partner wählt einen (im Allgemeinen) anderen Bitstring. Jeder von Ihnen wird einen Quantenschaltkreis erzeugen, der als Orakel fungiert, und Sie werden sie austauschen. Sie verwenden dann den Grover-Algorithmus mit diesem Orakel, um den geheimen Bitstring Ihres Partners zu ermitteln.

Schritt 1: Klassische Eingaben einem Quantenproblem zuordnen

Konstruieren Sie unter Verwendung der oben definierten Funktion grover_oracle eine Orakelschaltung für einen oder mehrere markierte Zustände. Sagen Sie Ihrem Partner, wie viele Staaten Sie markiert haben, damit er den Grover-Operator so oft wie möglich anwenden kann. Machen Sie Ihren Bitstring nicht zu lang. 3-5 Bits sollten ohne große Schwierigkeiten funktionieren. Längere Bitstrings würden tiefe Schaltungen zur Folge haben, die fortschrittlichere Techniken wie Fehlerminderung erfordern.

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

Jetzt haben Sie einen Quantenschaltkreis geschaffen, der die Phase Ihres Zielzustandes umkehrt. Sie können diese Schaltung mit der folgenden Syntax als my_circuit.qpy 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)

Senden Sie diese Datei nun an Ihren Partner (per E-Mail, Nachrichtendienst, über ein gemeinsames Repository usw.). Bitten Sie Ihren Partner, Ihnen auch seinen Schaltkreis zu schicken. Stellen Sie sicher, dass Sie die Datei an einem Ort speichern, an dem Sie sie leicht wiederfinden können. Sobald Sie den Schaltkreis Ihres Partners kennen, könnten Sie ihn visualisieren - aber das würde das Abfragemodell sprengen. Das heißt, wir modellieren eine Situation, in der man das Orakel zwar abfragen (den Orakelkreis verwenden), aber nicht untersuchen kann, um festzustellen, auf welchen Zustand es abzielt.

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")

Fragen Sie Ihren Partner, wie viele Zielzustände er kodiert hat, und tragen Sie dies 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: Optimierung des Problems für die Ausführung auf Quantenhardware

Dies geschieht genauso 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: Ausführung mithilfe von „ IBM Quantum “-Primitiven

Auch dies ist identisch mit dem Verfahren 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

Zeigen Sie nun ein Histogramm Ihrer Stichprobenergebnisse an. Ein oder mehrere Zustände sollten eine viel höhere Messwahrscheinlichkeit haben als die anderen. Teilen Sie diese Ihrem Partner mit und überprüfen Sie, ob Sie die Zielzustände richtig bestimmt haben. Standardmäßig wird das Histogramm desselben Stromkreises aus der ersten Aktivität angezeigt. Sie sollten unterschiedliche Ergebnisse aus der Schaltung Ihres Partners erhalten.

plot_distribution(dist)

Output:

Überprüfen Sie Ihr Verständnis

Sie sollten den/die Zielzustand(e) Ihres Partners korrekt ermittelt haben. Wenn dies nicht der Fall ist, sollten Sie gemeinsam mit Ihrem Partner herausfinden, was falsch gelaufen ist. Klicken Sie unten für ein paar Ideen.

• Hinweise
  • Visualisiere/zeichne die Schaltung deines Partners und stelle sicher, dass sie richtig geladen ist.
  • Vergleichen Sie die verwendeten Schaltkreise und vergleichen Sie das erwartete Ergebnis mit dem, was Sie erhalten haben.
  • Überprüfen Sie die Tiefe der verwendeten Schaltungen, um sicherzustellen, dass die Bitfolge nicht zu lang oder die Anzahl der Grover-Iterationen nicht zu hoch ist.

Wenn Sie es noch nicht getan haben, ziehen Sie den Orakelkreis, den Ihr Partner Ihnen geschickt hat. Versuchen Sie, die Auswirkungen der einzelnen Gates zu erklären und zu argumentieren, was der Zielzustand gewesen sein muss. Dies ist im Falle eines einzigen markierten Zustands viel einfacher als bei mehreren.

• Hinweise
  • Erinnern Sie sich daran, dass die Aufgabe des Orakels darin besteht, das Vorzeichen des Zielzustandes umzudrehen.
  • Es sei daran erinnert, dass das MCMTGate das Vorzeichen eines Zustands nur dann umkehrt, wenn sich alle an der Steuerung beteiligten Qubits im Zustand $|1\rangle$ befinden.
  • Wenn Ihr Zielzustand bereits eine $|1\rangle$ auf einem bestimmten Qubit hat, dann brauchen Sie an diesem Qubit nichts zu tun. Wenn Ihr Ziel ein $|0\rangle$ auf einem bestimmten Qubit hat und Sie möchten, dass das MCMTGate das Vorzeichen umkehrt, müssen Sie ein X Gate auf dieses Qubit in Ihrem Orakel anwenden (und dann das X Gate nach dem MCMTGate rückgängig machen).

Wiederholen Sie das Experiment mit einer Iteration des Grover-Operators weniger. Erhalten Sie trotzdem die richtige Antwort? Gründe?

• Anleitung

  Wahrscheinlich schon, obwohl es von der Anzahl der verschlüsselten Lösungen abhängen könnte. Dies verdeutlicht eine Spitzfindigkeit: Die "optimale" Anzahl von Grover-Iterationen ist die Anzahl, die die Wahrscheinlichkeit, den markierten Zustand zu messen, so hoch wie möglich macht. Bei einer geringeren Anzahl von Iterationen könnte der markierte Zustand jedoch immer noch wesentlich wahrscheinlicher sein als andere Zustände. Daher kann es sein, dass Sie mit weniger Iterationen als der optimalen Anzahl auskommen. Dies verringert die Schaltungstiefe und damit die Fehlerquote.

Warum sollte jemand weniger Grover-Iterationen als die hier ermittelte "optimale Anzahl" verwenden wollen?

• Antwort

  Die "optimale" Anzahl von Grover-Iterationen ist die Anzahl, die die Wahrscheinlichkeit, den markierten Zustand zu messen, so hoch wie möglich macht, wenn kein Rauschen vorhanden ist. Bei einer geringeren Anzahl von Iterationen könnte der markierte Zustand jedoch immer noch wesentlich wahrscheinlicher sein als andere Zustände. Es kann also sein, dass Sie mit weniger Iterationen als der optimalen Anzahl auskommen. Dies verringert die Schaltungstiefe und damit die Fehlerquote.

Aufgabe 3: Löse ein „Minesweeper“-Raster mit dem Grover-Algorithmus

Im vorigen Abschnitt haben wir festgestellt, dass Grovers Algorithmus erst dann wirklich nützlich wird, wenn wir ein Orakel anhand der Rahmenbedingungen eines Problems erstellen können, anstatt auf der Grundlage der bekannten Lösung. „Minesweeper“ ist ein perfektes Beispiel: Die nummerierten Felder geben an, wie viele Minen sich in der Nachbarschaft befinden, und diese Bedingungen legen vollständig fest, wo sich die Minen befinden müssen – doch um die Anordnung zu ermitteln, ist eine Suche erforderlich.

Es ist erwiesen, dass „Minesweeper“ NP-vollständig ist: Es ist schwer zu lösen, aber leicht zu überprüfen. Damit ist es ein naheliegender Kandidat für den Grover-Algorithmus. Natürlich können wir auf einem verrauschten Quantencomputer noch kein vollständiges 9× $\times$ -9-Gitter lösen – die Schaltkreise wären viel zu komplex. Stattdessen werden wir ein kleines Raster als anschauliches Beispiel dafür verwenden, wie man bei einer zukünftigen fehlertoleranten Maschine an ein größeres Spielfeld herangehen würde.

Ein paar wichtige Hinweise. Grovers Algorithmus bietet gegenüber der unstrukturierten klassischen Suche lediglich eine quadratische Beschleunigung. „Minesweeper“ weist mit ziemlicher Sicherheit eine Struktur auf, die sich durch einen cleveren klassischen Algorithmus ausnutzen lässt. Und bei einem exponentiell wachsenden Suchraum stößt selbst die Verbesserung durch „ $\sqrt{N}$ “ an ihre Grenzen. Aber lassen wir diese Bedenken einmal beiseite und nutzen wir dieses Beispielproblem, um zu veranschaulichen, wie Problembedingungen in ein Quantenorakel kodiert werden.

Das Raster

Hier ist unser „Baby-Minesweeper“-Spielfeld:

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

Wir könnten das im Kopf in etwa einer halben Sekunde lösen, aber wir nutzen dieses Beispielproblem, um zu veranschaulichen, wie man ein viel schwierigeres Problem mit einem Quantencomputer angehen könnte.

Die Einschränkungen kodieren

Jede nummerierte Zelle legt eine Bedingung für die benachbarten leeren Zellen fest. Wir müssen diese Bedingungen als Boolesche Ausdrücke formulieren, die in einen Quantenschaltkreis kodiert werden können.

Die Zelle mit der „1“ neben $x_0$ und $x_1$ besagt, dass genau eine dieser beiden Seiten eine Mine enthält. Dies ist genau die Exklusiv-ODER-Operation (XOR), $\oplus$, die „true“ zurückgibt, wenn genau eine ihrer Eingaben wahr ist:

Ebenso ergibt die andere Zelle mit der „1“ (neben $x_1$ und $x_2$ ) folgendes Ergebnis:

Die Zelle „2“ besagt, 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$ “ den Wert „true“ zurück, wenn eine ungerade Anzahl der Variablen wahr ist. Wir möchten, dass eine gerade Zahl (genauer gesagt zwei) wahr ist, also negieren wir mit „ $\lnot$ “:

Für sich genommen würde dieser Ausdruck entweder durch null oder durch zwei Qubits im Zustand „ $|1\rangle$ “ erfüllt sein, da es sich um eine Aussage über die Parität handelt. In Verbindung mit den beiden anderen Bedingungen, die jeweils mindestens eine Mine erfordern, gibt es jedoch nur eine einzige Lösung, bei der genau zwei Minen vorhanden sind.

Alle drei Bedingungen müssen gleichzeitig erfüllt sein, daher verbinden wir sie mit den Symbolen „und“ $\land$ :

Schritt 1: Klassische Eingaben einem Quantenproblem zuordnen

Nun müssen wir diesen Booleschen Ausdruck in einen Quantenschaltkreis umwandeln, der als Orakel dient. Die Quantenversion von XOR lässt sich mit CX-Gattern (CNOT-Gattern) realisieren: Durch die Anwendung von zwei CX-Gattern von den Daten-Qubits auf ein Arbeitsqubit (Ancilla-Qubit) wird deren XOR-Operation effektiv berechnet und das Ergebnis im Ancilla-Qubit gespeichert.

Wir führen drei Arbeitsraum-Qubits ein – eines für jede Klausel. Wir speichern das Ergebnis jedes Booleschen Ausdrucks in dem entsprechenden Arbeitsraum-Qubit und verwenden dann ein mehrfach gesteuertes Z-Gatter, um die Phase des Drei-Qubit-Zustands umzukehren, der bewirkt, dass alle drei Arbeitsraum-Qubits den Zustand „ $|1\rangle$ “ annehmen (was bedeutet, dass alle Klauseln gleichzeitig erfüllt sind).

In der ersten Codezelle unten erstellen wir die „Rechen“-Hälfte des Orakels – den Teil, der jede Klausel auswertet und das Ergebnis in die Qubits des Arbeitsbereichs 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 dieser Stelle wird das Ergebnis jeder Klausel im zugehörigen Arbeitsqubit gespeichert. Nun benötigen wir den 3-Qubit-Datenzustand, der bewirkt, dass alle drei Arbeitsraum-Qubits $|1\rangle$ ein Minuszeichen annehmen. Dazu verwenden wir ein mehrfach gesteuertes Z-Gatter (das als MCX-Gatter umgesetzt ist, das von Hadamard-Gattern auf der Zielseite eingerahmt wird).

Nach dem Anwenden der Phasenumkehr müssen wir die Berechnung rückgängig machen – also alle Schritte der Klauselauswertung in umgekehrter Reihenfolge rückgängig machen –, um die Arbeitsbereichs-Qubits wieder auf „ $|0\rangle$ “ zurückzusetzen. Dies ist unerlässlich, damit die Arbeitsbereichs-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")

Diese Schaltung ist unser Orakel: Sie kehrt die Phase des Daten-Qubit-Zustands um, der alle drei „Minesweeper“-Bedingungen erfüllt, und belässt die Arbeitsbereichs-Qubits in der „ $|0\rangle$ “.

Nun konstruieren wir aus diesem Orakel den vollständigen Grover-Operator. xBeachten Sie das reflection_qubits Argument: Wir übergeben nur die Daten-Qubits, da die Arbeitsraum-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")

Bei drei Datenqubits und einem Lösungszustand beträgt die optimale Anzahl von Grover-Iterationen $t \approx \frac{\pi}{4}\sqrt{8} - \frac{1}{2} \approx 1.7$, daher verwenden wir zwei Iterationen. Wir wenden Hadamard-Gatter auf die Daten-Qubits an, um die anfängliche Überlagerung zu erzeugen, wenden den Grover-Operator zweimal an 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: Optimierung des Problems für die Ausführung auf Quantenhardware

Wie zuvor transpilieren wir die Schaltung 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)

Nun können wir die Tiefe der transpilierten Schaltung überprüfen. Da das „Minesweeper“-Orakel Arbeitsbereichs-Qubits und mehrere CX-Gatter verwendet, wird die transpilierte Schaltung tiefer sein als die in den vorherigen Übungen.

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: Ausführung mithilfe von „ IBM Quantum “-Primitiven

# 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 weitaus höherer Wahrscheinlichkeit auftreten als jeder andere, was darauf hindeutet, dass sich Minen unter $x_0$ und $x_2$ befinden. Wir haben einen Quantencomputer eingesetzt, um eine kleine Partie „Minesweeper“ 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 Rasters aus. Grovers Algorithmus würde nur bei extrem schwierigen Spielfeldern, die auf maximale Mehrdeutigkeit ausgelegt sind, einen Vorteil bieten, und selbst dann bedeutet die quadratische Beschleunigung, dass er mit dem exponentiellen Wachstum nicht auf Dauer Schritt halten kann. Das Wesentliche ist jedoch die Methode: Die Kodierung von Problembedingungen in ein Quantenorakel ist ein leistungsstarkes Muster, das sich auf die Lösung von Beschränkungsaufgaben, die kombinatorische Optimierung und viele andere Bereiche erstreckt.

Fragen und zentrale Konzepte:

Wichtige Konzepte:

In diesem Modul haben wir einige wichtige Merkmale des Grover-Algorithmus kennen gelernt:

• Während klassische Algorithmen für die unstrukturierte Suche eine Anzahl von Abfragen erfordern, die linear mit der Größe des Raums skaliert ( $N$ ), erfordert der Grover-Algorithmus eine Anzahl von Abfragen, die wie folgt skaliert ( $\sqrt{N}$ ).
• Bei Grovers Algorithmus wird eine Abfolge von Operationen (allgemein als „Grover-Operator“ bezeichnet) ein $t$ -mal wiederholt, wobei die Anzahl der Wiederholungen so gewählt wird, dass die Zielzustände mit optimaler Wahrscheinlichkeit gemessen werden.
• Der Algorithmus von Grover kann mit weniger als $t$ Iterationen ausgeführt werden und trotzdem die Zielzustände verstärken.
• Grovers 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. Sie kann auch als Unterprogramm in anderen Quantenberechnungen nützlich sein.
• Ein Orakel kann anhand der Problembedingungen und nicht anhand der Kenntnis der Lösung erstellt werden, wie das Beispiel „Minesweeper“ zeigt.

Richtig/Falsch-Fragen:

1. T/F Der Grover-Algorithmus bietet eine exponentielle Verbesserung gegenüber klassischen Algorithmen in Bezug auf die Anzahl der Abfragen, die erforderlich sind, um einen einzigen markierten Zustand bei der unstrukturierten Suche zu finden.

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

3. T/F Je öfter man den Grover-Operator wiederholt, desto höher ist die Wahrscheinlichkeit, einen Lösungszustand zu messen.

MC-Fragen:

1. Wählen Sie die beste Option zur Vervollständigung des Satzes. Die beste Strategie zur erfolgreichen Anwendung des Grover-Algorithmus auf modernen Quantencomputern ist die Iteration des Grover-Operators...

• a. Nur einmal.
• b. Immer $t$ mal, um die Wahrscheinlichkeitsamplitude des/der Lösungszustände zu maximieren.
• c. Bis zu $t$ Mal, wobei auch weniger ausreichen kann, um die Lösungszustände hervorzuheben.
• d. Nicht weniger als 10 Mal.

2. Hier wird eine Phasenabfrage-Schaltung gezeigt, die als Orakel fungiert, um einen bestimmten Zustand mit einer Phasenumkehr zu markieren. Welche der folgenden Zustände werden durch diese Schaltung markiert?

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

3. Angenommen, Sie möchten aus einer Menge von 128 Zuständen drei markierte Zustände 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 Jahre
• F. 33

Diskussionsfragen:

1. Welche weiteren Probleme könnte man als Grover-Suche formulieren? Denken Sie an Probleme, bei denen es schwierig ist, eine Lösung zu finden, aber einfach, diese zu überprüfen.

2. Sehen Sie irgendwelche Probleme bei der Skalierung des Grover-Algorithmus auf modernen Quantencomputern?