Grovers Algorithmus

Nutzungsschätzung: unter aner Minute auf emm Eagle r3-Prozessor (HINWEIS: Des isch nur a Schätzung. Dei Laufzeit ka variiere.)

Hintergrund

Amplitudenverstärkung isch a universeller Quantenalgorithmus oder a Unterroutine, wo mer verwende ka, um a quadratische Beschleunigung gegenüber aner Handvoll klassische Algorithmen z'erziela. Grovers Algorithmus war dr erschte, wo diese Beschleunigung bei unstrukturierte Suchproblemen demonstriert hend. D'Formulierung vo amm Groverschen Suchproblem erfordert a Orakelfunktion, wo oiner oder mehrere Basiszuständ als die Zuständ markiert, wo mir finde möchtet, und an Verstärkungsschaltkreis, wo d'Amplitude vo de markierte Zuständ erhöht und folglich d'verbleibende Zuständ unterdrückt.

Do demonstriere mir, wie mer Grover-Orakel konstruiert und den grover_operator() aus dr Qiskit-Schaltkreisbibliothek verwendet, um einfach a Groversche Suchinstanz einzurichte. Des Runtime Sampler-Primitiv ermöglicht d'nahtlose Ausführung vo Grover-Schaltkreisen.

Anforderungen

Schau vor dem Aafange vo diesem Tutorial, dass des Folgende installiert isch:

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

Setup

# 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 a Quantenproblem abbilden

Grovers Algorithmus braucht a Orakel, wo oinen oder mehrere markierte Basiszuständ spezifiziert, wobei "markiert" an Zustand mit anerer Phase vo -1 bedeutet. A Controlled-Z-Gate oder sei mehrfach kontrollierte Verallgemeinerung über $N$ Qubits markiert de $2^{N}-1$-Zustand ('1'*$N$ Bit-String). Des Markiere vo Basiszuständen mit oimm oder mehrere '0' in dr binäre Darstellung erfordert des Aawendem vo X-Gates auf d'entsprechende Qubits vor und nach dem Controlled-Z-Gate; des entspricht anerer offene Kontrolle auf diesem Qubit. Im nachfolgende Code definiere mir a Orakel, wo genau des macht und oine oder mehrere Eingabe-Basiszuständ markiert, wo durch ihre Bit-String-Darstellung definiert send. Des MCMT-Gate wird verwendet, um des mehrfach kontrollierte Z-Gate z'implementiere.

# 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 mir jetzt d'Orakelfunktion hend, könne mir a spezifische Instanz vo dr Groverschen Suche definiere. In diesem Beispiel werre mir zwei Berechnungszuständ aus de acht verfügbare in amm Drei-Qubit-Berechnungsraum markiere:

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

Dr eingebaute Qiskit grover_operator() nimmt an Orakel-Schaltkreis entgege und gibt an Schaltkreis zruck, wo aus dem Orakel-Schaltkreis selber und amm Schaltkreis besteht, wo d'vom Orakel markierte Zuständ verstärkt. Do verwende mir d'decompose()-Methode vo dem Schaltkreis, um d'Gates innerhalb vo dem Operator z'sehe:

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

Wiederholte Anwendunge vo diesem grover_op-Schaltkreis verstärke d'markierte Zuständ und mache se zu de wahrscheinlichste Bit-Strings in dr Ausgabeverteilung vo dem Schaltkreis. Es gibt a optimale Anzahl selle Anwendungen, wo durch des Verhältnis vo markierte Zuständen zur Gesamtzahl möglicher Berechnungszuständ bestimmt wird:

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

Vollständige Grover-Schaltkreis

A vollständiges Grover-Experiment aafangt mit amm Hadamard-Gate auf jedem Qubit; des erzeugt a gleichmäßige Überlagerung aller Berechnungsbasisstände, gefolgt vo dem Grover-Operator (grover_op), wo d'optimale Anzahl vo Male widderholt wird. Do verwende mir d'QuantumCircuit.power(INT)-Methode, um de Grover-Operator wiederholt aazuwende.

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 d'Ausführung auf Quantenhardware optimiere

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ühre mit Qiskit-Primitiven

Amplitudenverstärkung isch a Sampling-Problem, wo für d'Ausführung mit dem Sampler-Runtime-Primitiv geeignet isch.

Beachte, dass d'run()-Methode vo dem Qiskit Runtime SamplerV2 a Iterable vo primitive unified blocks (PUBs) akzeptiert. Für de Sampler isch jedes PUB a Iterable im Format (circuit, parameter_values). Mindestens akzeptiert er aber a Liste vo 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 vo em Ergebnis im gewünschte klassische Format

plot_distribution(dist)

Tutorial-Umfrage

Bitte nemm an derer kurze Umfrage teil, um Feedback zu diesem Tutorial z'gebe. Dei Erkenntnisse helfet ons, unsre Inhaltsangebote und Benutzererfahrung z'verbessere.

Link zur Umfrage