Grovers Algorithmus

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

Hintergrund

Amplitudenverstärkung ist ein universeller Quantenalgorithmus oder eine Unterroutine, die verwendet werden kann, um eine quadratische Beschleunigung gegenüber einer Handvoll klassischer Algorithmen zu erzielen. Grovers Algorithmus war der erste, der diese Beschleunigung bei unstrukturierten Suchproblemen demonstrierte. Die Formulierung eines Groverschen Suchproblems erfordert eine Orakelfunktion, die einen oder mehrere Basiszustände als die Zustände markiert, die wir finden möchten, und einen Verstärkungsschaltkreis, der die Amplitude der markierten Zustände erhöht und folglich die verbleibenden Zustände unterdrückt.

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

Anforderungen

Stelle vor Beginn dieses Tutorials sicher, dass du Folgendes installiert hast:

• Qiskit SDK v1.4 oder neuer, mit Visualisierung-Unterstützung
• Qiskit Runtime (pip install qiskit-ibm-runtime) v0.36 oder neuer

Einrichtung

# Added by doQumentation — required packages for this notebook
!pip install -q 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

Schritt 1: Klassische Eingaben auf ein Quantenproblem abbilden

Grovers Algorithmus benötigt ein Orakel, das einen oder mehrere markierte Basiszustände spezifiziert, wobei "markiert" einen Zustand mit einer Phase von -1 bedeutet. Ein Controlled-Z-Gate oder seine mehrfach kontrollierte 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ären Darstellung erfordert das Anwenden von X-Gates auf die entsprechenden Qubits vor und nach dem Controlled-Z-Gate; dies entspricht einer offenen Kontrolle auf diesem Qubit. Im folgenden Code definieren wir ein Orakel, das genau das tut und einen oder mehrere Eingabe-Basiszustände markiert, die durch ihre Bit-String-Darstellung definiert sind. Das MCMT-Gate wird verwendet, um das mehrfach kontrollierte Z-Gate zu implementieren.

# 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, min_num_qubits=127
)
backend.name

'ibm_brisbane'

Spezifische Grover-Instanz

Da wir nun die Orakelfunktion haben, können wir eine spezifische Instanz der Groverschen Suche definieren. In diesem Beispiel werden wir zwei Berechnungszustände aus den acht verfügbaren in einem Drei-Qubit-Berechnungsraum markieren:

marked_states = ["011", "100"]

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

marked_states = ["011", "100"]

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

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-Schaltkreis entgegen und gibt einen Schaltkreis zurück, der aus dem Orakel-Schaltkreis selbst und einem Schaltkreis besteht, der die vom Orakel markierten Zustände verstärkt. Hier verwenden wir die decompose()-Methode des Schaltkreises, 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-Schaltkreises verstärken die markierten Zustände und machen sie zu den wahrscheinlichsten Bit-Strings in der Ausgabeverteilung des Schaltkreises. Es gibt eine optimale Anzahl solcher Anwendungen, die durch das Verhältnis markierter Zustände zur Gesamtzahl möglicher 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-Schaltkreis

Ein vollständiges Grover-Experiment beginnt mit einem Hadamard-Gate auf jedem Qubit; dies erzeugt eine gleichmäßige Überlagerung aller Berechnungsbasisstände, gefolgt vom Grover-Operator (grover_op), der die optimale Anzahl von Malen wiederholt wird. Hier verwenden wir die QuantumCircuit.power(INT)-Methode, 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

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

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

Schritt 3: Ausführen mit Qiskit-Primitiven

Amplitudenverstärkung ist ein Sampling-Problem, das für die Ausführung mit dem Sampler-Runtime-Primitiv geeignet ist.

Beachte, dass die run()-Methode des Qiskit Runtime SamplerV2 ein Iterable von primitive unified blocks (PUBs) akzeptiert. Für den Sampler ist jedes PUB ein Iterable im Format (circuit, parameter_values). Mindestens akzeptiert er jedoch eine Liste von Quantenschaltkreis(en).

# To run on local simulator:
#   1. Use the StatevectorSampler from qiskit.primitives instead
sampler = Sampler(mode=backend)
sampler.options.default_shots = 10_000
result = sampler.run([circuit_isa]).result()
dist = result[0].data.meas.get_counts()

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

plot_distribution(dist)

Tutorial-Umfrage

Bitte nimm an dieser kurzen Umfrage teil, um Feedback zu diesem Tutorial zu geben. Deine Erkenntnisse helfen uns, unsere Inhaltsangebote und Benutzererfahrung zu verbessern.

Link zur Umfrage