Algoritmo di Grover

Stima dei tempi di esecuzione: meno di un minuto su un processore Eagle r3 (NOTA: si tratta solo di una stima). (La durata potrebbe variare.)

Risultati di apprendimento

Una volta completato questo tutorial, avrai acquisito le seguenti conoscenze:

• Come costruire oracoli di Grover che contrassegnano uno o più stati della base computazionale
• Come utilizzare la grover_operator() funzione della libreria di circuiti Qiskit
• Come determinare il numero ottimale di iterazioni di Grover per un dato problema
• Come eseguire l'algoritmo di Grover utilizzando la primitiva " IBM Quantum " del Sampler

Prerequisiti

Si consiglia di approfondire i seguenti argomenti:

• Nozioni fondamentali sugli algoritmi quantistici: l'algoritmo di Grover
• Fondamenti dell'informazione quantistica

Sfondo

L'amplificazione dell'ampiezza è un algoritmo quantistico generico, o subroutine, che può essere utilizzato per ottenere un aumento quadratico della velocità rispetto a una serie di algoritmi classici. L'algoritmo di Grover è stato il primo a dimostrare questo aumento di velocità nei problemi di ricerca non strutturati. Per formulare un problema di ricerca di Grover occorre una funzione oracolo che identifichi uno o più stati della base computazionale come gli stati che ci interessa individuare, nonché un circuito di amplificazione che aumenti l'ampiezza degli stati identificati, sopprimendo di conseguenza gli stati rimanenti.

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

Requisiti

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

• Qiskit SDK v2.0 o versioni successive, con supporto alla visualizzazione
• Qiskit Runtime v0.22 o versioni successive (pip install qiskit-ibm-runtime)

Configura

# 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-ibm-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 di simulatore su piccola scala

In questa sezione, analizzeremo passo dopo passo l'algoritmo di Grover su scala ridotta utilizzando un simulatore locale, prima di eseguire lo stesso problema su un hardware quantistico reale.

Fase 1: mappare gli input classici su un problema quantistico

L'algoritmo di Grover richiede un oracolo che specifichi uno o più stati della base computazionale contrassegnati, dove per "contrassegnati" si intendono stati con una fase pari a -1. Un gate a Z controllato, o la sua generalizzazione multi-controllata su qubit di tipo " $N$ ", definisce lo stato " $2^{N}-1$ " ('1'*stringa di bit $N$ ). Per contrassegnare gli stati di base con uno o più 1 '0' nella rappresentazione binaria è necessario applicare porte X ai qubit corrispondenti prima e dopo la porta Z controllata, il che equivale ad applicare un comando di controllo aperto a quel qubit. Nel codice seguente, definiamo un oracolo che identifica uno o più stati di base in ingresso definiti tramite la loro rappresentazione in stringa di bit. Il MCMT gate viene utilizzato per realizzare il gate Z a controllo multiplo.

Caso specifico di Grover

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

marked_states = ["011", "100"]

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

Output:

Operatore Grover

Il built-in Qiskit grover_operator() prende un circuito oracolo e restituisce un circuito composto dal circuito oracolo stesso e da un circuito che amplifica gli stati contrassegnati dall'oracolo. In questo caso, utilizziamo il metodo decompose() per vedere le porte all'interno dell'operatore:

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

Output:

Applicazioni ripetute di questo circuito grover_op amplificano gli stati contrassegnati, rendendoli le stringhe di bit più probabili nella distribuzione in uscita dal circuito. Esiste un numero ottimale di tali applicazioni, determinato dal rapporto tra gli stati contrassegnati e il numero totale di stati computazionali possibili:

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

Circuito Grover completo

Un esperimento di Grover completo inizia con un gate Hadamard su ogni qubit; si crea 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")

Output:

Fase 2: Ottimizzazione del problema per l'esecuzione su hardware quantistico

Per la simulazione su piccola scala, compiliamo il circuito senza specificare un hardware particolare.

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

Output:

Passaggio 3: eseguire utilizzando Qiskit primitives

L'amplificazione dell'ampiezza è un problema di campionamento che si presta all'esecuzione con la SamplerV2 primitiva. Qui utilizziamo il 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()

Fase 4: Post-elaborazione e restituzione del risultato nel formato classico desiderato

plot_distribution(dist)

Output:

Esempio di hardware

Passaggi da 1 a 4

L'algoritmo di Grover è fondamentalmente un algoritmo tollerante ai guasti: i gate Z a controllo multiplo che costituiscono il cuore dell'oracolo e dell'operatore di diffusione comportano una profondità dei gate a due qubit che cresce molto rapidamente con il numero di qubit (come mostreremo nella prossima sezione). Ciò significa che l'algoritmo non si adatta bene all'hardware odierno, soggetto a interferenze. Per questo motivo, illustriamo l'esecuzione hardware su una scala ridotta, analoga a quella dell'esempio del simulatore riportato sopra, anziché tentare di affrontare un problema di dimensioni maggiori.

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

Output:

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

Uno dei motivi principali per cui l'algoritmo di Grover è considerato un algoritmo tollerante ai guasti è la rapida crescita della profondità delle porte a due qubit del circuito all'aumentare del numero di qubit. Il gate Z a controllo multiplo, che costituisce il nucleo sia dell'oracolo che dell'operatore di diffusione, si scompone in un numero di gate a due qubit che cresce in modo esponenziale con il numero di qubit di controllo. Se a ciò si aggiunge il fatto che il numero ottimale di iterazioni di Grover cresce esso stesso come un $O(\sqrt{2^n})$ e, la profondità complessiva a due qubit diventa ben presto impraticabile per un hardware soggetto a rumore.

Di seguito, costruiamo circuiti di Grover per un numero crescente di qubit, li trasponiamo e tracciamo la profondità delle porte a due qubit risultante per illustrare tale 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()

Output:

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à del gate a due qubit cresce in modo estremamente rapido con l'aumentare del numero di qubit — all'incirca in modo esponenziale. Ciò rende l'algoritmo di Grover poco pratico sull'attuale hardware quantistico soggetto a rumore, a meno che i problemi non siano di dimensioni molto ridotte. L'algoritmo rimane un obiettivo importante per i futuri computer quantistici a tolleranza di errore, nei quali la correzione degli errori consentirà l'esecuzione affidabile di circuiti complessi.

Passi successivi