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.

Mathematik

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

Lies die Frage unten, denke über deine Antwort nach, dann klicke auf das Dreieck, um die Lösung zu enthüllen.

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

Antwort:

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.

Offensichtlicher Vorbehalt

Um den Grover-Algorithmus anzuwenden, mussten wir den Grover-Operator konstruieren, was bedeutet, dass wir in der Lage sein müssen, die Phase an Zuständen umzudrehen, die unsere Lösungskriterien erfüllen. Dies wirft die Frage auf: Wenn wir unsere Lösungsmenge so gut kennen, dass wir einen Quantenschaltkreis entwerfen können, um jeden zu beschriften, wonach suchen wir dann?! Die Antwort ist dreifach, und wir werden dies im gesamten Tutorial noch einmal aufgreifen:

(1) Diese Arten von Abfragealgorithmen beinhalten oft zwei Parteien: eine, die das Orakel hat, das die Lösungskriterien festlegt, und eine andere, die versucht, einen Lösungszustand zu erraten/zu finden. Die Tatsache, dass eine Person das Orakel bauen kann, negiert nicht die Notwendigkeit für die Suche.

(2) Es gibt Probleme, für die es einfacher ist, ein Lösungskriterium anzugeben, als es ist, die Lösung zu finden. Das bekannteste Beispiel hierfür ist wahrscheinlich die Identifizierung von Primfaktoren großer Zahlen. Der Grover-Algorithmus ist nicht besonders effektiv beim Lösen dieses spezifischen Problems; wir würden den Shor-Algorithmus für die Primfaktorisierung verwenden. Dies ist nur ein Beispiel, um darauf hinzuweisen, dass das Kennen des Kriteriums für das Verhalten eines Zustands nicht immer dasselbe ist wie das Kennen des Zustands.

(3) Der Grover-Algorithmus gibt nicht nur klassische Daten zurück. Wenn wir eine Messung des Endzustands nach $t$ Wiederholungen des Grover-Operators vornehmen, erhalten wir wahrscheinlich klassische Informationen, die den Lösungszustand identifizieren. Aber was ist, wenn wir keine klassischen Informationen wollen; was ist, wenn wir einen auf einem Quantencomputer vorbereiteten Lösungszustand für die weitere Verwendung in einem anderen Algorithmus wollen? Der Grover-Algorithmus erzeugt tatsächlich einen Quantenzustand mit stark gewichteten Lösungen. Du kannst also erwarten, den Grover-Algorithmus als Unterroutine in komplizierteren Quantenalgorithmen zu finden.

Mit diesen 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, und wir werden zu Beispielen übergehen, bei denen die Nützlichkeit des Grover-Algorithmus deutlicher 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
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 oben argumentiert 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, kann aus diesem Ausdruck erhalten werden:

$$(2t+1)\theta = (2t+1)\sin^{-1}\left( \sqrt{\frac{|A_1|}{N}}\right) \approx (2t+1)\sqrt{\frac{|A_1|}{N}} \approx \frac{\pi}{2}\\ t\approx \frac{\pi}{4} \sqrt{\frac{N}{|A_1|}}-\frac{1}{2}$$

Hier ist $A_1$ die Anzahl der Lösungen oder Zielzustände. 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.

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

Lies die Fragen unten, denke über deine Antwort nach, dann klicke auf das Dreieck, um die Lösung zu enthüllen.

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?

Antwort:

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?

Antwort:

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

Lies die Fragen oder Aufforderungen unten, denke über deine Antwort nach oder besprich den Prozess mit deinem Partner. Klicke auf das Dreieck für Hinweise oder Vorschläge.

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.

Hinweise:

• 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.

Hinweise:

• 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?

Anleitung:

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

Antwort:

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: Kriterium anders als ein spezifischer Bitstring

Als abschließende Illustration, wie der Grover-Algorithmus im Kontext einer Unterroutine nützlich sein könnte, stellen wir uns vor, dass wir Quantenzustände mit einer bestimmten Anzahl von 1en in der Bitstring-Darstellung benötigen. Dies ist üblich in Situationen, in denen Erhaltungsgesetze beteiligt sind. Zum Beispiel ordnet man im Kontext der Quantenchemie oft einen 1-Zustand eines Qubits einer Besetzung eines elektronischen Orbitals zu. Damit die Ladung erhalten bleibt, muss die Gesamtzahl der 1en ebenfalls konstant bleiben. Solche Einschränkungen sind so üblich, dass sie einen besonderen Namen haben: Hamming-Gewichtsbeschränkungen, und die Anzahl der 1en im Zustand wird Hamming-Gewicht genannt.

Schritt 1:

Schreiben wir zunächst eine Funktion, die Zustände mit dem gewünschten Hamming-Gewicht markiert. Wir werden dies allgemein für eine nicht spezifizierte Anzahl von Qubits num_qubits und Ziel-Hamming-Gewicht target_weight schreiben.

from qiskit import QuantumCircuit

def grover_oracle_hamming_weight(num_qubits, target_weight):
    """
    Build a Grover oracle that marks all states with Hamming weight == target_weight.

    Parameters:
        num_qubits (int): Number of qubits in the circuit.
        target_weight (int): The Hamming weight to mark.

    Returns:
        QuantumCircuit: Quantum circuit representing Grover oracle.
    """
    qc = QuantumCircuit(num_qubits)
    marked_count = 0
    marked_list = []
    for x in range(2**num_qubits):
        bitstr = format(x, f"0{num_qubits}b")
        if bitstr.count("1") == target_weight:
            # Count the number of target states
            marked_count = marked_count + 1
            marked_list.append(bitstr)
            # Reverse for Qiskit bit order (qubit 0 is rightmost)
            rev_target = bitstr[::-1]
            zero_inds = [i for i, b in enumerate(rev_target) if b == "0"]
            # Apply X gates to 'open' controls (where bit is 0)
            qc.x(zero_inds)
            # Multi-controlled Z (as MCX conjugated by H)
            if num_qubits == 1:
                qc.z(0)
            else:
                qc.h(num_qubits - 1)
                qc.mcx(list(range(num_qubits - 1)), num_qubits - 1)
                qc.h(num_qubits - 1)
            # Undo X gates
            qc.x(zero_inds)
    return qc, marked_count, marked_list

# Completing step 1
oracle, num_marked_states, marked_states = grover_oracle_hamming_weight(3, 2)
print(marked_states)
oracle.draw(output="mpl", style="iqp")

['011', '101', '110']

Von hier aus ist der gesamte Prozess identisch mit dem aus den vorherigen beiden Aktivitäten. Der Kürze halber werden die Qiskit-Musterschritte hier nur in Code-Kommentaren gezeigt.

from qiskit_ibm_runtime import SamplerV2 as Sampler

# Completing step 1
oracle, num_marked_states, marked_states = grover_oracle_hamming_weight(4, 2)
oracle.draw(output="mpl", style="iqp")

grover_op = grover_operator(oracle)
grover_op.decompose().draw(output="mpl", style="iqp")
optimal_num_iterations = math.floor(
    math.pi / (4 * math.asin(math.sqrt(len(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()
qc.draw(output="mpl", style="iqp")

# Step 2: Optimize for running on real quantum computers

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)

# Step 3: Execute using Qiskit primitives
# To run on a real quantum computer (this was tested on a Heron r2 processor and used 4 seconds of QPU time)

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

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

ibm_brisbane

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  502
The depth of two-qubit gates is  130

num_marked_states

6

plot_distribution(dist)

Hier hat der Grover-Algorithmus tatsächlich die Zustände mit Hamming-Gewicht 2 so vorbereitet, dass sie viel wahrscheinlicher gemessen werden als alle anderen Zustände, ungefähr eine Größenordnung wahrscheinlicher.

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.

Fragen

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 Bedingungen könntest du in einem Quanten-Orakel verwenden? Berücksichtige Bedingungen, die einfach zu formulieren oder auf einen Bitstring anzuwenden sind, aber nicht bloß das Aufschreiben der markierten Bitstrings sind.

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