Algoritmo di Grover

Stima di utilizzo: meno di un minuto su un processore Eagle r3 (NOTA: Questa è solo una stima. Il tuo tempo di esecuzione potrebbe variare.)

Obiettivi di apprendimento

Dopo aver completato questo tutorial, potrai comprendere le seguenti informazioni:

• Come costruire oracoli di Grover che contrassegnino uno o più stati della base computazionale
• Come usare la funzione grover_operator() dalla libreria di circuiti Qiskit
• Come determinare il numero ottimale di iterazioni di Grover per un dato problema
• Come eseguire l'algoritmo di Grover usando la primitiva Sampler di Qiskit Runtime

Prerequisiti

È consigliabile familiarizzare con questi argomenti:

• Fondamenti degli algoritmi quantistici: algoritmo di Grover
• Basi dell'informazione quantistica

Contesto

L'amplificazione di ampiezza è un algoritmo quantistico o subroutine per uso generale che può essere utilizzato per ottenere un'accelerazione quadratica rispetto a una serie di algoritmi classici. L'algoritmo di Grover è stato il primo a dimostrare questa accelerazione su problemi di ricerca non strutturati. La formulazione di un problema di ricerca di Grover richiede una funzione oracolo che contrassegni uno o più stati della base computazionale come gli stati che siamo interessati a trovare, e un circuito di amplificazione che aumenti l'ampiezza degli stati contrassegnati, sopprimendo di conseguenza gli stati rimanenti.

Qui dimostriamo come costruire oracoli di Grover e utilizzare grover_operator() dalla libreria di circuiti Qiskit per configurare facilmente un'istanza di ricerca di Grover. La primitiva Sampler del runtime consente l'esecuzione senza soluzione di continuità dei circuiti di Grover.

Requisiti

Prima di iniziare questo tutorial, assicurati di avere installato quanto segue:

• Qiskit SDK v2.0 o successivo, con supporto per la visualizzazione
• Qiskit Runtime v0.22 o successivo (pip install qiskit-ibm-runtime)

Configurazione

# 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

Esempio con simulatore su piccola scala

In questa sezione, percorriamo ciascun passo dell'algoritmo di Grover su piccola scala usando un simulatore locale, prima di eseguire lo stesso problema su hardware quantistico reale.

Passo 1: Mappare gli input classici a un problema quantistico

L'algoritmo di Grover richiede un oracolo che specifichi uno o più stati della base computazionale contrassegnati, dove "contrassegnato" significa uno stato con una fase di -1. Un gate controlled-Z, o la sua generalizzazione multi-controllata su $N$ qubit, contrassegna lo stato $2^{N}-1$ (stringa di bit '1'*$N$). Contrassegnare stati della base con uno o più '0' nella rappresentazione binaria richiede l'applicazione di gate X sui qubit corrispondenti prima e dopo il gate controlled-Z, il che è equivalente ad avere un controllo aperto su quel qubit. Nel codice seguente definiamo un oracolo che contrassegna uno o più stati della base di input definiti attraverso la loro rappresentazione in stringa di bit. Il gate MCMT viene utilizzato per implementare il gate Z multi-controllato.

Istanza specifica di Grover

Ora che abbiamo la funzione oracolo, possiamo definire un'istanza specifica di ricerca di Grover. In questo esempio contrassegneremo due stati computazionali su otto disponibili in uno spazio computazionale a tre qubit:

marked_states = ["011", "100"]

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

Operatore di Grover

La funzione grover_operator() integrata in Qiskit prende un circuito oracolo e restituisce un circuito composto dal circuito oracolo stesso e da un circuito che amplifica gli stati contrassegnati dall'oracolo. Qui utilizziamo il metodo decompose() del circuito per vedere i gate all'interno dell'operatore:

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

Le applicazioni ripetute di questo circuito grover_op amplificano gli stati contrassegnati, rendendoli le stringhe di bit più probabili nella distribuzione di output del circuito. Esiste un numero ottimale di tali applicazioni che è determinato dal rapporto tra stati contrassegnati e numero totale di possibili stati computazionali:

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

Circuito di Grover completo

Un esperimento di Grover completo inizia con un gate Hadamard su ogni qubit; creando una sovrapposizione uniforme di tutti gli stati della base computazionale, seguita dall'operatore di Grover (grover_op) ripetuto il numero ottimale di volte. Qui utilizziamo il metodo QuantumCircuit.power(INT) per applicare ripetutamente l'operatore di 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")

Passo 2: Ottimizzare il problema per l'esecuzione su hardware quantistico

Per la simulazione su piccola scala, transpiliamo il circuito senza mirare a hardware specifico.

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

Passo 3: Eseguire utilizzando le primitive Qiskit

L'amplificazione di ampiezza è un problema di campionamento adatto per l'esecuzione con la primitiva SamplerV2. Qui usiamo StatevectorSampler da qiskit.primitives per la simulazione locale.

from qiskit.primitives import StatevectorSampler

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

Passo 4: Post-processare e restituire il risultato nel formato classico desiderato

plot_distribution(dist)

Esempio su hardware reale

Passi 1-4

L'algoritmo di Grover è fondamentalmente un algoritmo a tolleranza di errore — i gate Z multi-controllati al cuore dell'oracolo e dell'operatore di diffusione portano a profondità di gate a due qubit che crescono molto rapidamente con il numero di qubit (come mostreremo nella prossima sezione). Ciò significa che l'algoritmo non scala bene sull'hardware rumoroso odierno. Per questo motivo, dimostriamo l'esecuzione hardware alla stessa piccola scala dell'esempio con il simulatore, anziché tentare una dimensione del problema maggiore.

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

Discussione: scalabilità della profondità dei gate a due qubit

Un motivo chiave per cui l'algoritmo di Grover è considerato un algoritmo a tolleranza di errore è la rapida crescita della profondità dei gate a due qubit del circuito all'aumentare del numero di qubit. Il gate Z multi-controllato al cuore sia dell'oracolo che dell'operatore di diffusione si decompone in un numero di gate a due qubit che cresce esponenzialmente con il numero di qubit di controllo. Combinato con il fatto che il numero ottimale di iterazioni di Grover stesso cresce come $O(\sqrt{2^n})$, la profondità a due qubit complessiva diventa rapidamente impraticabile per l'hardware rumoroso.

Di seguito costruiamo circuiti di Grover per un numero crescente di qubit, li transpiliamo e tracciamo la profondità dei gate a due qubit risultante per illustrare questa scalabilità.

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

Come mostra il grafico, la profondità dei gate a due qubit cresce estremamente rapidamente con il numero di qubit — approssimativamente in modo esponenziale. Ciò rende l'algoritmo di Grover impraticabile sull'hardware quantistico rumoroso attuale oltre dimensioni di problema molto piccole. L'algoritmo rimane un obiettivo importante per i futuri computer quantistici a tolleranza di errore, dove la correzione degli errori consentirà l'esecuzione affidabile di circuiti profondi.

Prossimi passi

Consigli

Se hai trovato questo lavoro interessante, potresti essere interessato al seguente materiale:

• Libreria di circuiti Qiskit: riferimento API grover_operator()
• Il tutorial QAOA e la lezione QAOA su scala utility forniscono esempi a breve termine di ottimizzazione con computer quantistici
• Per uno sguardo più approfondito agli algoritmi a breve termine, consulta il corso Il calcolo quantistico in pratica