Algoritmul lui Grover

Estimare de utilizare: sub un minut pe un procesor Eagle r3 (NOTĂ: Aceasta este doar o estimare. Timpul tău de execuție poate varia.)

Rezultate de învățare

După finalizarea acestui tutorial, te poți aștepta să înțelegi următoarele informații:

• Cum să construiești oracole Grover care marchează una sau mai multe stări ale bazei computaționale
• Cum să folosești funcția grover_operator() din biblioteca de circuite Qiskit
• Cum să determini numărul optim de iterații Grover pentru o problemă dată
• Cum să execuți algoritmul lui Grover folosind primitiva Sampler din Qiskit Runtime

Condiții prealabile

Se recomandă să te familiarizezi cu aceste subiecte:

• Fundamentals of quantum algorithms: Grover's algorithm
• Basics of quantum information

Fundal

Amplificarea amplitudinii este un algoritm cuantic de uz general (general-purpose), sau subrutină, care poate fi utilizat pentru a obține o accelerare pătratică față de o serie de algoritmi clasici. Algoritmul lui Grover a fost primul care a demonstrat această accelerare pe probleme de căutare nestructurată. Formularea unei probleme de căutare Grover necesită o funcție oracle care marchează una sau mai multe stări ale bazei computaționale ca fiind stările pe care dorim să le găsim, și un circuit de amplificare care crește amplitudinea stărilor marcate, suprimând astfel stările rămase.

Aici demonstrăm cum să construiești oracole Grover și să folosești grover_operator() din biblioteca de circuite Qiskit pentru a configura cu ușurință o instanță de căutare Grover. Primitiva runtime Sampler permite execuția fără probleme a circuitelor Grover.

Cerințe

Înainte de a începe acest tutorial, asigură-te că ai instalat următoarele:

• Qiskit SDK v2.0 sau mai recent, cu suport pentru vizualizare
• Qiskit Runtime v0.22 sau mai recent (pip install qiskit-ibm-runtime)

Configurare

# 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

Exemplu cu simulator la scară mică

În această secțiune, parcurgem fiecare pas al algoritmului lui Grover la o scară mică folosind un simulator local, înainte de a rula aceeași problemă pe hardware cuantic real.

Pasul 1: Mapează intrările clasice la o problemă cuantică

Algoritmul lui Grover necesită un oracle care specifică una sau mai multe stări marcate ale bazei computaționale, unde „marcat" înseamnă o stare cu o fază de -1. Un poartă controlled-Z, sau generalizarea sa multi-controlată peste $N$ Qubiți, marchează starea $2^{N}-1$ ('1'*$N$ bit-string). Marcarea stărilor bazei cu unul sau mai mulți '0' în reprezentarea binară necesită aplicarea X-Gate-urilor pe Qubiții corespunzători înainte și după Gate-ul controlled-Z, ceea ce este echivalent cu a avea un control deschis pe acel qubit. În codul următor, definim un oracle care marchează una sau mai multe stări ale bazei de intrare definite prin reprezentarea lor ca șir de biți. Gate-ul MCMT este folosit pentru a implementa Gate-ul Z multi-controlat.

Instanță specifică Grover

Acum că avem funcția oracle, putem defini o instanță specifică de căutare Grover. În acest exemplu vom marca două stări computaționale din cele opt disponibile într-un spațiu computațional de trei Qubiți:

marked_states = ["011", "100"]

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

Operatorul Grover

Funcția built-in Qiskit grover_operator() primește un circuit oracle și returnează un circuit compus din Circuit-ul oracle însuși și un circuit care amplifică stările marcate de oracle. Aici folosim metoda decompose() a Circuit-ului pentru a vedea Gate-urile din cadrul operatorului:

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

Aplicările repetate ale acestui Circuit grover_op amplifică stările marcate, făcându-le cele mai probabile șiruri de biți în distribuția de ieșire a Circuit-ului. Există un număr optim de astfel de aplicări, determinat de raportul dintre stările marcate și numărul total de stări computaționale posibile:

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

Circuit Grover complet

Un experiment Grover complet începe cu un Hadamard Gate pe fiecare qubit; creând o superpoziție uniformă a tuturor stărilor bazei computaționale, urmată de operatorul Grover (grover_op) repetat de numărul optim de ori. Aici folosim metoda QuantumCircuit.power(INT) pentru a aplica în mod repetat operatorul Grover.

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

Pasul 2: Optimizează problema pentru execuția pe hardware cuantic

Pentru simularea la scară mică, transpilăm circuitul fără a viza hardware specific.

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

Pasul 3: Execuție folosind primitivele Qiskit

Amplificarea amplitudinii este o problemă de eșantionare potrivită pentru execuție cu primitiva SamplerV2. Aici folosim StatevectorSampler din qiskit.primitives pentru simulare locală.

from qiskit.primitives import StatevectorSampler

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

Pasul 4: Post-procesare și returnarea rezultatului în formatul clasic dorit

plot_distribution(dist)

Exemplu pe hardware

Pașii 1-4

Algoritmul lui Grover este în mod fundamental un algoritm tolerant la erori — Gate-urile Z multi-controlate din centrul oracolului și al operatorului de difuzie duc la adâncimi ale Gate-urilor cu doi qubiți care cresc foarte rapid odată cu numărul de qubiți (după cum vom arăta în secțiunea următoare). Aceasta înseamnă că algoritmul nu se scalează bine pe hardware-ul zgomotos de astăzi. Din acest motiv, demonstrăm execuția pe hardware la aceeași scară mică ca exemplul cu simulatorul de mai sus, în loc să încercăm o dimensiune mai mare a problemei.

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

Discuție: Scalarea adâncimii Gate-urilor cu doi qubiți

Un motiv cheie pentru care algoritmul lui Grover este considerat un algoritm tolerant la erori este creșterea rapidă a adâncimii Gate-urilor cu doi qubiți ale circuitului pe măsură ce numărul de qubiți crește. Gate-ul Z multi-controlat din nucleul atât al oracolului, cât și al operatorului de difuzie se descompune într-un număr de poartă-uri cu doi qubiți care crește exponențial cu numărul de qubiți de control. Combinat cu faptul că numărul optim de iterații Grover însuși crește ca $O(\sqrt{2^n})$, adâncimea totală cu doi qubiți devine rapid impractică pentru hardware-ul zgomotos.

Mai jos, construim circuite Grover pentru numere crescătoare de qubiți, le transpilăm și reprezentăm grafic adâncimea rezultată a Gate-urilor cu doi qubiți pentru a ilustra această scalare.

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

După cum arată graficul, adâncimea Gate-urilor cu doi qubiți crește extrem de rapid odată cu numărul de qubiți — aproximativ exponențial. Acest lucru face algoritmul lui Grover impractical pe hardware-ul cuantic zgomotos actual pentru dimensiuni de probleme mai mari decât cele foarte mici. Algoritmul rămâne o țintă importantă pentru viitoarele computere cuantice tolerante la erori, unde corectarea erorilor va permite executarea de circuite adânci în mod fiabil.

Pași următori

Recomandări

Dacă ai găsit această lucrare interesantă, s-ar putea să fii interesat de următoarele materiale:

• Biblioteca de circuite Qiskit: referință API grover_operator()
• Tutorialul QAOA și lecția QAOA la scară de utilitate oferă exemple pe termen scurt de optimizare cu computere cuantice
• Pentru o privire mai aprofundată asupra algoritmilor pe termen scurt, consultați cursul Quantum computing in practice