Algoritmo di Grover

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

Contesto

L'amplificazione di ampiezza è un algoritmo quantistico o subroutine di 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 v1.4 o successivo, con supporto per la visualizzazione
• Qiskit Runtime (pip install qiskit-ibm-runtime) v0.36 o successivo

Configurazione

# 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

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; equivalente ad avere un controllo aperto su quel qubit. Nel codice seguente definiamo un oracolo che fa esattamente questo, contrassegnando 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.

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

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

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

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

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

Passo 3: Eseguire utilizzando le primitive Qiskit

L'amplificazione di ampiezza è un problema di campionamento adatto per l'esecuzione con la primitiva Sampler del runtime.

Nota che il metodo run() del Qiskit Runtime SamplerV2 accetta un iterabile di primitive unified blocks (PUBs). Per il sampler, ogni PUB è un iterabile nel formato (circuit, parameter_values). Tuttavia, come minimo, accetta una lista di circuiti quantistici.

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

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

plot_distribution(dist)

Sondaggio sul tutorial

Ti preghiamo di completare questo breve sondaggio per fornire feedback su questo tutorial. Il tuo feedback ci aiuterà a migliorare i nostri contenuti e l'esperienza utente.

Link al sondaggio