Grovers Algorithmus

Geschätzte Nutzungsdauer: unter einer Minute auf einem Eagle r3-Prozessor (HINWEIS: Dies ist nur eine Schätzung. Deine Laufzeit kann variieren.)

Lernziele

Nach Abschluss dieses Tutorials kannst du folgende Informationen verstehen:

• Wie man Grover-Orakel erstellt, die einen oder mehrere Berechnungsbasis-Zustände markieren
• Wie man die Funktion grover_operator() aus der Qiskit Circuit Library verwendet
• Wie man die optimale Anzahl von Grover-Iterationen für ein gegebenes Problem bestimmt
• Wie man Grovers Algorithmus mit dem Qiskit Runtime Sampler Primitive ausführt

Voraussetzungen

Es wird empfohlen, dich mit diesen Themen vertraut zu machen:

• Grundlagen der Quantenalgorithmen: Grovers Algorithmus
• Grundlagen der Quanteninformation

Hintergrund

Amplitudenverstärkung ist ein allgemeiner Quantenalgorithmus bzw. eine Unterroutine, die genutzt werden kann, um einen quadratischen Speedup gegenüber einer Handvoll klassischer Algorithmen zu erzielen. Grovers Algorithmus war der erste, der diesen Speedup bei unstrukturierten Suchproblemen demonstriert hat. Die Formulierung eines Grover-Suchproblems erfordert eine Orakelfunktion, die einen oder mehrere Berechnungsbasis-Zustände als die Zustände markiert, die wir zu finden suchen, sowie einen Amplifikationsschaltkreis, der die Amplitude der markierten Zustände erhöht und dabei die übrigen Zustände unterdrückt.

Hier zeigen wir, wie man Grover-Orakel konstruiert und den grover_operator() aus der Qiskit Circuit Library verwendet, um eine Grover-Suchinstanz einfach einzurichten. Das Runtime-Sampler-Primitive ermöglicht die nahtlose Ausführung von Grover-Circuits.

Anforderungen

Bevor du dieses Tutorial beginnst, stelle sicher, dass du Folgendes installiert hast:

• Qiskit SDK v2.0 oder höher, mit Unterstützung für Visualisierung
• Qiskit Runtime v0.22 oder höher (pip install qiskit-ibm-runtime)

Setup

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

# 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

# Imports from Qiskit Runtime
from qiskit_ibm_runtime import QiskitRuntimeService
from qiskit_ibm_runtime import SamplerV2 as Sampler

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 bit-string to match Qiskit bit-ordering
        rev_target = target[::-1]
        # Find the indices of all the '0' elements in bit-string
        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 bit-string has a '0' entry
        if zero_inds:
            qc.x(zero_inds)
        qc.compose(MCMTGate(ZGate(), num_qubits - 1, 1), inplace=True)
        if zero_inds:
            qc.x(zero_inds)
    return qc

Kleines Simulator-Beispiel

In diesem Abschnitt gehen wir jeden Schritt von Grovers Algorithmus in kleinem Maßstab mit einem lokalen Simulator durch, bevor wir dasselbe Problem auf echter Quantenhardware ausführen.

Schritt 1: Klassische Eingaben auf ein Quantenproblem abbilden

Grovers Algorithmus erfordert ein Orakel, das einen oder mehrere markierte Berechnungsbasis-Zustände angibt, wobei „markiert" einen Zustand mit einer Phase von -1 bedeutet. Ein kontrolliertes-Z Gate oder seine Multi-Control-Verallgemeinerung über $N$ Qubits markiert den $2^{N}-1$ Zustand ('1'*$N$ Bit-String). Das Markieren von Basiszuständen mit einem oder mehreren '0' in der Binärdarstellung erfordert das Anwenden von X-Gates auf die entsprechenden Qubits vor und nach dem controlled-Z Gate, was dem Haben eines Open-Controls auf diesem Qubit entspricht. Im folgenden Code definieren wir ein Orakel, das einen oder mehrere Eingabe-Basiszustände markiert, die durch ihre Bitstring-Darstellung definiert sind. Das MCMT-Gate wird verwendet, um das Multi-Control-Z-Gate zu implementieren.

Spezifische Grover-Instanz

Jetzt, da wir die Orakelfunktion haben, können wir eine spezifische Instanz der Grover-Suche definieren. In diesem Beispiel markieren wir zwei Berechnungszustände von den acht verfügbaren in einem Drei-Qubit-Berechnungsraum:

marked_states = ["011", "100"]

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

Grover Operator

Der eingebaute Qiskit grover_operator() nimmt einen Orakel-Circuit und gibt einen Circuit zurück, der aus dem Orakel-Circuit selbst und einem Circuit besteht, der die vom Orakel markierten Zustände amplifiziert. Hier verwenden wir die decompose()-Methode des Circuits, um die Gates innerhalb des Operators zu sehen:

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

Wiederholte Anwendungen dieses grover_op-Circuits amplifizieren die markierten Zustände und machen sie zu den wahrscheinlichsten Bit-Strings in der Ausgabeverteilung des Circuits. Es gibt eine optimale Anzahl solcher Anwendungen, die durch das Verhältnis der markierten Zustände zur Gesamtzahl der möglichen Berechnungszustände bestimmt wird:

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

Vollständiger Grover Circuit

Ein vollständiges Grover-Experiment beginnt mit einem Hadamard Gate auf jedem Qubit, das eine gleichmäßige Superposition aller Berechnungsbasis-Zustände erzeugt, gefolgt vom Grover-Operator (grover_op), der die optimale Anzahl von Malen wiederholt wird. Hier nutzen wir die Methode QuantumCircuit.power(INT), um den Grover-Operator wiederholt anzuwenden.

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

Schritt 2: Problem für die Ausführung auf Quantenhardware optimieren

Für die kleinmaßstäbige Simulation transpilieren wir den Circuit ohne Ausrichtung auf spezifische Hardware.

pm = generate_preset_pass_manager(optimization_level=3)
circuit_isa = pm.run(qc)
circuit_isa.draw(output="mpl", idle_wires=False, style="iqp")

Schritt 3: Ausführung mit Qiskit Primitives

Amplitudenverstärkung ist ein Sampling-Problem, das für die Ausführung mit dem SamplerV2-Primitive geeignet ist. Hier verwenden wir den StatevectorSampler aus qiskit.primitives für die lokale Simulation.

from qiskit.primitives import StatevectorSampler

sampler = StatevectorSampler()
result = sampler.run([circuit_isa], shots=10_000).result()
dist = result[0].data.meas.get_counts()

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

plot_distribution(dist)

Hardware-Beispiel

Schritte 1–4

Grovers Algorithmus ist grundlegend ein fehlertoleranter Algorithmus — die Multi-Control-Z-Gates im Kern des Orakels und des Diffusionsoperators führen zu Zwei-Qubit-Gate-Tiefen, die mit der Anzahl der Qubits sehr schnell wachsen (wie wir im nächsten Abschnitt zeigen werden). Das bedeutet, dass der Algorithmus auf der heutigen verrauschten Hardware nicht gut skaliert. Aus diesem Grund demonstrieren wir die Hardware-Ausführung auf demselben kleinen Maßstab wie das Simulator-Beispiel oben, anstatt eine größere Problemgröße zu versuchen.

# -------------------------Step 1-------------------------
marked_states = ["011", "100"]

oracle = grover_oracle(marked_states)
grover_op = grover_operator(oracle)

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

# -------------------------Step 2-------------------------
service = QiskitRuntimeService()
backend = service.least_busy(
    operational=True, simulator=False, min_num_qubits=127
)

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

# -------------------------Step 3-------------------------
sampler = Sampler(mode=backend)
sampler.options.default_shots = 10_000
sampler.options.environment.job_tags = ["TUT-GA"]
result = sampler.run([circuit_isa]).result()
dist = result[0].data.meas.get_counts()

# -------------------------Step 4-------------------------
plot_distribution(dist)

Diskussion: Skalierung der Zwei-Qubit-Gate-Tiefe

Ein wesentlicher Grund, warum Grovers Algorithmus als fehlertoleranter Algorithmus gilt, ist das schnelle Wachstum der Zwei-Qubit-Gate-Tiefe des Circuits mit zunehmender Anzahl von Qubits. Das Multi-Control-Z-Gate im Kern sowohl des Orakels als auch des Diffusionsoperators zerlegt sich in eine Anzahl von Zwei-Qubit-Gates, die exponentiell mit der Anzahl der Kontroll-Qubits wächst. In Kombination mit der Tatsache, dass die optimale Anzahl der Grover-Iterationen selbst als $O(\sqrt{2^n})$ wächst, wird die gesamte Zwei-Qubit-Tiefe für verrauschte Hardware schnell unpraktisch.

Im Folgenden konstruieren wir Grover-Circuits für zunehmende Qubit-Anzahlen, transpilieren sie und stellen die resultierende Zwei-Qubit-Gate-Tiefe grafisch dar, um diese Skalierung zu veranschaulichen.

import matplotlib.pyplot as plt

num_qubits_list = list(range(3, 10))
two_q_depths = []
backend = service.least_busy(
    operational=True, simulator=False, min_num_qubits=127
)
for n in num_qubits_list:
    # Mark a single state for simplicity
    marked = ["1" * n]
    oracle_n = grover_oracle(marked)
    grover_op_n = grover_operator(oracle_n)

    # Optimal number of iterations
    num_iters = math.floor(
        math.pi / (4 * math.asin(math.sqrt(len(marked) / 2**n)))
    )

    # Build the full Grover circuit
    qc_n = QuantumCircuit(n)
    qc_n.h(range(n))
    qc_n.compose(grover_op_n.power(num_iters), inplace=True)
    qc_n.measure_all()

    # Transpile to a basis gate set and count 2Q depth
    pm_n = generate_preset_pass_manager(backend=backend, optimization_level=3)
    qc_transpiled = pm_n.run(qc_n)

    # Compute depth restricted to 2-qubit operations
    depth_2q = qc_transpiled.depth(lambda x: x.operation.num_qubits == 2)

    two_q_depths.append(depth_2q)
    print(f"n={n}: optimal_iters={num_iters}, 2Q depth={depth_2q}")

# Plot
fig, ax = plt.subplots(figsize=(8, 5))
ax.plot(
    num_qubits_list,
    two_q_depths,
    "o-",
    linewidth=2,
    markersize=8,
    color="#6929C4",
)
ax.set_xlabel("Number of qubits", fontsize=13)
ax.set_ylabel("Two-qubit gate depth", fontsize=13)
ax.set_title("Grover's algorithm: 2Q depth scaling", fontsize=14)
ax.set_yscale("log")
ax.grid(True, alpha=0.3)
ax.set_xticks(num_qubits_list)
plt.tight_layout()
plt.show()

n=3: optimal_iters=2, 2Q depth=39
n=4: optimal_iters=3, 2Q depth=111
n=5: optimal_iters=4, 2Q depth=466
n=6: optimal_iters=6, 2Q depth=1646
n=7: optimal_iters=8, 2Q depth=3550
n=8: optimal_iters=12, 2Q depth=7989
n=9: optimal_iters=17, 2Q depth=14824

Wie die Grafik zeigt, wächst die Zwei-Qubit-Gate-Tiefe mit der Anzahl der Qubits extrem schnell — ungefähr exponentiell. Dadurch wird Grovers Algorithmus auf der aktuellen verrauschten Quantenhardware jenseits sehr kleiner Problemgrößen unpraktisch. Der Algorithmus bleibt ein wichtiges Ziel für zukünftige fehlertolerante Quantencomputer, bei denen die Fehlerkorrektur die zuverlässige Ausführung tiefer Circuits ermöglichen wird.

Nächste Schritte

Empfehlungen

Wenn du diese Arbeit interessant fandest, könnte dich folgendes Material interessieren:

• Qiskit Circuit Library: grover_operator() API-Referenz
• Das QAOA-Tutorial und die QAOA-Lektion im Utility-Scale bieten kurzfristige Beispiele für die Optimierung mit Quantencomputern
• Für einen tieferen Einblick in kurzfristige Algorithmen, siehe den Kurs Quantencomputing in der Praxis