Grovers Algorithmus

Nutzigssschätzig: under enere Minute uf emne Eagle r3-Prozessor (HIWIS: Das isch nur e Schätzig. Dini Laufzyt cha variierä.)

Hingergrund

Amplitudeverstärkig isch en universelle Quantealgorithmus oder Unterroutine, wo mir chönd bruchä, zum e quadratischi Bschleunigung gegenüber ere Handvoll klassische Algorithme z'erreichä. Grovers Algorithmus isch de erschti gsi, wo dä Bschleunigung bi unstrukturierte Suechproblem zeigt het. Zum es Groversches Suechproblem z'formulierä brucht's e Orakelfunktion, wo eis oder mehreri Basiszueständ als die Zueständ markiert, wo mir wönd finde, und en Verstärkigsschaltkreis, wo d'Amplitude vo de markierte Zueständ erhöht und drmet di üübrige Zueständ underdruckt.

Do zeige mir, wie mir Grover-Orakel konstruiere und de grover_operator() us de Qiskit-Schaltkreisbibliothek verwände, zum eifach e Groversche Suechinstanz ufz'setze. S Runtime Sampler-Primitiv ermöglicht di nahtlosi Usfüehrig vo Grover-Schaltkreis.

Aaforderige

Bevor du mit dem Tutorial aafangsch, lueg dass du das Folgendi installiert hesch:

• Qiskit SDK v1.4 oder neuer, mit visualization-Understützig
• Qiskit Runtime (pip install qiskit-ibm-runtime) v0.36 oder neuer

Setup

# 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: Klassischi Iigabe uf es Quanteproblem abbilde

Grovers Algorithmus brucht es Orakel, wo eis oder mehreri markierti Basiszueständ spezifiziert, wobei "markiert" en Zuestand mit ere Phase vo -1 bedütet. Es Controlled-Z-Gate, oder sini mehrfach kontrollierti Verallgemeinierig über $N$ Qubits, markiert de $2^{N}-1$-Zuestand ('1'*$N$ Bit-String). Zum Basiszueständ z'markiere mit eim oder mehrere '0' i de binäre Darstellig muen mir X-Gates uf de entsprechende Qubits vor und nach em Controlled-Z-Gate aawände; das entspricht ere offene Kontrolli uf dem Qubit. Im folgende Code definiered mir es Orakel, wo genau das macht und eis oder mehreri Iigab-Basiszueständ markiert, wo dürch ihri Bit-String-Darstellig definiert sind. S MCMT-Gate wird brucht, zum s 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'

Spezifischi Grover-Instanz

Jetzt wo mir d'Orakelfunktion händ, chönd mir e spezifischi Instanz vo de Groversche Sueche definierä. I dem Bispiel wänd mir zwei Rächnigsszueständ us de acht verfüegbare i emne Drei-Qubit-Rächnigsruum markierä:

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

De iibuti Qiskit grover_operator() nimmt en Orakel-Schaltkreis und git en Schaltkreis zrügg, wo us em Orakel-Schaltkreis selber und emne Schaltkreis bestaht, wo di vom Orakel markierte Zueständ verstärkt. Do verwände mir di decompose()-Methode vom Schaltkreis, zum d'Gates innerhalb vom Operator z'gseh:

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

Widerholteni Aawändige vo dem grover_op-Schaltkreis verstärked di markierte Zueständ und mached si zu de wahrscheinlichste Bit-Strings i de Usgabeverteijig vom Schaltkreis. Es git e optimali Aazahl vo sötige Aawändige, wo dürch s Verhältnis vo markierte Zueständ zur Gsamtzahl möögliche Rächnigsszuestä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

Es vollständigs Grover-Experiment fangt aa mit emne Hadamard-Gate uf jedem Qubit; das erzüügt e glichmässigi Überlaagerig vo allne Rächnigsbasiszueständ, gfolgt vom Grover-Operator (grover_op), wo di optimali Aazahl Mol widerholt wird. Do verwände mir di QuantumCircuit.power(INT)-Methode, zum de Grover-Operator widerholt aaz'wände.

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'Usfüehrig uf Quantehardware optimierä

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: Mit Qiskit-Primitive usfüehre

Amplitudeverstärkig isch es Sampling-Problem, wo für d'Usfüehrig mit em Sampler-Runtime-Primitiv geignet isch.

Merk dir, dass di run()-Methode vom Qiskit Runtime SamplerV2 es Iterable vo primitive unified blocks (PUBs) akzeptiert. Für de Sampler isch jedes PUB es Iterable im Format (circuit, parameter_values). Mindestens muess mer aber e Lischte vo Quanteschaltkreis(e) übergää.

# 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: Nachbearbeitig und Rückgab vom Ergebnis im gwünschte klassische Format

plot_distribution(dist)

Tutorial-Umfraag

Bitte mach bi dere churze Umfraag mit, zum Feedback zu dem Tutorial z'gää. Dini Erkenntnis helfed üüs, üüsi Inhaltsaagebot und Benutzererfahrig z'verbessere.

Link zur Umfraag