Algoritmi quantistici: ricerca di Grover e applicazioni

nota

Atsushi Matsuo (10 maggio 2024)

Scarica il PDF della lezione originale. Nota che alcuni frammenti di codice potrebbero essere deprecati poiché si tratta di immagini statiche.

Il tempo QPU approssimativo per eseguire questo esperimento è di 2 secondi.

1. Introduzione all'algoritmo di Grover

Questo notebook è il quarto di una serie di lezioni sul Percorso verso l'Utilità nel Calcolo Quantistico. In questo notebook impareremo l'algoritmo di Grover.

L'algoritmo di Grover è uno degli algoritmi quantistici più noti grazie alla sua accelerazione quadratica rispetto ai metodi di ricerca classici. Nel calcolo classico, cercare in un database non ordinato di $N$ elementi richiede una complessità temporale $O(N)$, il che significa che nel caso peggiore potrebbe essere necessario esaminare ogni elemento singolarmente. Tuttavia, l'algoritmo di Grover ci permette di effettuare questa ricerca in $O(\sqrt{N})$ passi, sfruttando i principi della meccanica quantistica per identificare l'elemento target in modo più efficiente.

L'algoritmo utilizza l'amplificazione delle ampiezze, un processo che aumenta l'ampiezza di probabilità dello stato corretto in una sovrapposizione quantistica, permettendo che venga misurato con probabilità maggiore. Questa accelerazione rende l'algoritmo di Grover utile in varie applicazioni al di là della semplice ricerca in database, specialmente quando la dimensione del dataset è grande. Spiegazioni dettagliate dell'algoritmo sono fornite nel notebook sull'algoritmo di Grover.

La struttura di base dell'algoritmo di Grover

L'algoritmo di Grover è composto da quattro componenti principali:

1. Inizializzazione: configurazione della sovrapposizione su tutti gli stati possibili.
2. Oracle: applicazione di una funzione oracle che contrassegna lo stato target invertendone la fase.
3. Operatore di diffusione: applicazione di una serie di operazioni per amplificare la probabilità dello stato contrassegnato.

Ciascuno di questi passi ha un ruolo fondamentale nel far funzionare l'algoritmo in modo efficiente. Spiegazioni dettagliate di ogni passo sono fornite in seguito.

2. Implementazione dell'algoritmo di Grover

2.1 Preparazione

Importa le librerie necessarie e configura l'ambiente per eseguire il circuito quantistico.

# Added by doQumentation — required packages for this notebook
!pip install -q qiskit qiskit-aer qiskit-ibm-runtime

%config InlineBackend.figure_format = 'svg' # Makes the images look nice

# importing Qiskit
from qiskit import QuantumCircuit, ClassicalRegister, QuantumRegister

# import basic plot tools
from qiskit.visualization import plot_histogram

Passo 1: mappare il problema in circuito e operatori quantistici

Considera una lista di 4 elementi, dove il nostro obiettivo è identificare l'indice di un elemento che soddisfa una condizione specifica. Ad esempio, vogliamo trovare l'indice dell'elemento uguale a 2. In questo esempio, lo stato quantistico $|01\rangle$ rappresenta l'indice dell'elemento che soddisfa questa condizione, poiché punta alla posizione in cui si trova il valore 2.

Passo 2: ottimizzare per l'hardware target

1: Inizializzazione

Nel passo di inizializzazione, creiamo una sovrapposizione di tutti gli stati possibili. Ciò si ottiene applicando un gate di Hadamard a ogni qubit in un registro di n qubit, che produce una sovrapposizione uniforme di $2^n$ stati. Matematicamente, questo può essere rappresentato come:

$$\frac{1}{\sqrt{N}} \sum_{x=0}^{N-1} |x\rangle$$

dove $N = 2^n$ è il numero totale di stati possibili. Cambiamo anche lo stato del qubit ancilla in $|-\rangle$.

def initialization(circuit):
    # Initialization
    n = circuit.num_qubits
    # For input qubits
    for qubit in range(n - 1):
        circuit.h(qubit)
    # For the ancilla bit
    circuit.x(n - 1)
    circuit.h(n - 1)
    circuit.barrier()
    return circuit

n = 2
qr = QuantumRegister(n, "q")
anc = QuantumRegister(1, "ancillary")
initialization_circuit = QuantumCircuit(qr, anc)

initialization(initialization_circuit)
initialization_circuit.draw(output="mpl", idle_wires=False)

2: Oracle

L'oracle è una componente chiave dell'algoritmo di Grover. Contrassegna lo stato target applicando uno sfasamento, tipicamente invertendo il segno dell'ampiezza associata a quello stato. L'oracle è spesso specifico per il problema e viene costruito in base ai criteri per identificare lo stato target. In termini matematici, l'oracle applica la seguente trasformazione:

f(x) = \begin\{cases\} 1, & \text\{if \} x = x_\{\text\{target}\} \\ 0, & \text\{otherwise\} \end\{cases\}

Questo sfasamento di fase viene ottenuto applicando un segno negativo all'ampiezza dello stato target tramite phase kickback.

def oracle(circuit):
    circuit.x(1)
    circuit.ccx(0, 1, 2)
    circuit.x(1)
    circuit.barrier()

n = 2
qr = QuantumRegister(n, "q")
anc = QuantumRegister(1, "ancillary")
oracle_circuit = QuantumCircuit(qr, anc)

oracle(oracle_circuit)
oracle_circuit.draw(output="mpl", idle_wires=False)

3: Operatore di diffusione

Il processo di amplificazione delle ampiezze è ciò che differenzia l'algoritmo di Grover da una ricerca classica. Dopo che l'oracle ha contrassegnato lo stato target, applichiamo una serie di operazioni che aumentano l'ampiezza di questo stato contrassegnato, rendendolo più probabile da osservare alla misurazione. Questo processo viene realizzato tramite l'operatore di diffusione, che effettivamente esegue un'inversione rispetto all'ampiezza media. L'operazione matematica è la seguente:

$D = 2|\psi\rangle\langle\psi| - I$

dove $D$ è l'operatore di diffusione, $I$ è la matrice identità e $|\psi\rangle$ è lo stato di sovrapposizione uniforme. La combinazione dell'oracle e dell'operatore di diffusione viene applicata circa $\sqrt{N}$ volte per ottenere la massima probabilità di misurare lo stato contrassegnato.

def diffusion(circuit):
    input_qubits = circuit.num_qubits - 1
    circuit.h(range(0, input_qubits))
    circuit.x(range(0, input_qubits))
    circuit.h(input_qubits - 1)
    circuit.mcx([i for i in range(0, input_qubits - 1)], input_qubits - 1)
    circuit.h(input_qubits - 1)
    circuit.x(range(0, input_qubits))
    circuit.h(range(0, input_qubits))
    circuit.barrier()

n = 2
qr = QuantumRegister(n, "q")
anc = QuantumRegister(1, "ancillary")
diffusion_circuit = QuantumCircuit(qr, anc)

diffusion(diffusion_circuit)
diffusion_circuit.draw(output="mpl", idle_wires=False)

2.2 Un esempio di ricerca di Grover a 2 qubit

n = 2
qr = QuantumRegister(n, "q")
anc = QuantumRegister(1, "ancillary")
meas = ClassicalRegister(3, "meas")
grover_circuit = QuantumCircuit(qr, anc, meas)

# the number of iterations
num_iterations = 1

# Let's do Grover search
initialization(grover_circuit)

for i in range(0, num_iterations):
    oracle(grover_circuit)
    diffusion(grover_circuit)

# Clear the ancilla bit
grover_circuit.h(n)
grover_circuit.x(n)
grover_circuit.measure_all(add_bits=False)

grover_circuit.draw(output="mpl", idle_wires=False)

2.3 Esperimento con simulatori

Passo 3: esecuzione del circuito.

from qiskit_aer import AerSimulator
from qiskit_ibm_runtime import Sampler
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager

# Define backend
backend = AerSimulator()

# Transpile to backend
pm = generate_preset_pass_manager(backend=backend, optimization_level=1)
isa_qc = pm.run(grover_circuit)

# Run the job
sampler = Sampler(mode=backend)
job = sampler.run([isa_qc])
result = job.result()

Passo 4: post-elaborazione dei risultati.

# Print the results
counts = result[0].data.meas.get_counts()
print(counts)

# Plot the counts in a histogram
plot_histogram(counts)

{'001': 1024}

Abbiamo ottenuto la risposta corretta $|01\rangle$. Nota che bisogna prestare attenzione all'ordine dei qubit.

3. Esperimento con dispositivi reali

Passo 2: ottimizzare per l'hardware target

from qiskit_ibm_runtime import QiskitRuntimeService

service = QiskitRuntimeService()
real_backend = service.backend("ENTER-QPU-NAME-HERE")

# You can also identify the least busy device

real_backend = service.least_busy(simulator=False, operational=True)
print("The least busy device is ", real_backend)

# Transpile the circuit into basis gates executable on the hardware
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager

pm = generate_preset_pass_manager(backend=real_backend, optimization_level=1)
target_circuit = pm.run(grover_circuit)

target_circuit.draw(output="mpl", idle_wires=False)

Transpilando il circuito, è stato convertito in un circuito che utilizza i gate nativi del dispositivo.

Passo 3: esecuzione del circuito.

sampler = Sampler(real_backend)
job_real = sampler.run([target_circuit])
job_id = job_real.job_id()
print("job id:", job_id)

job id: cw69csv19rzg0080yfkg

# Check the job status
job_real.status()

'QUEUED'

# If the Notebook session got disconnected you can also check your job status by running the following code
job_real = service.job(job_id)  # Input your job-id between the quotations
job_real.status()

'DONE'

# Execute after job has successfully run
result_real = job_real.result()
print(result_real[0].data.meas.get_counts())

{'101': 540, '001': 2253, '011': 476, '000': 251, '110': 105, '100': 100, '010': 168, '111': 203}

Passo 4: post-elaborazione dei risultati.

plot_histogram(result_real[0].data.meas.get_counts())

4. Una ricerca di Grover a 3 qubit

Ora proviamo un esempio di ricerca di Grover a 3 qubit.

n = 3
qr = QuantumRegister(n, "q")
anc = QuantumRegister(1, "ancilla")
grover_circuit = QuantumCircuit(qr, anc)

# the number of iterations
num_iterations = 2

def oracle(circuit):
    circuit.mcx([0, 1, 2], 3)
    circuit.barrier()

Questa volta, $|111\rangle$ è lo stato "buono".

# Let's do Grover search
initialization(grover_circuit)

for i in range(0, num_iterations):
    oracle(grover_circuit)
    diffusion(grover_circuit)

# Clear the ancilla bit
grover_circuit.h(n)
grover_circuit.x(n)

grover_circuit.draw(output="mpl", idle_wires=False)

grover_circuit.measure_all()

# Define backend
backend = AerSimulator()

# Transpile to backend
pm = generate_preset_pass_manager(backend=backend, optimization_level=1)
isa_qc = pm.run(grover_circuit)

# Run the job
sampler = Sampler(backend)
job = sampler.run([isa_qc], shots=1024)
result = job.result()

# Print the results
counts = result[0].data.meas.get_counts()
print(counts)

# Plot the counts in a histogram
plot_histogram(counts)

{'0111': 977, '0100': 11, '0001': 8, '0000': 8, '0011': 5, '0010': 12, '0110': 3}

$|0111\rangle$ viene osservato con la probabilità più alta, come previsto. Nota che due iterazioni sono ottimali in questo caso. Tuttavia, la probabilità di ottenere la risposta corretta non è del 100%, il che è normale nella ricerca di Grover.

Cosa succede se iteriamo 3 volte?

Ora proviamo a iterare 3 volte.

n = 3
qr = QuantumRegister(n, "q")
anc = QuantumRegister(1, "ancillary")
grover_circuit = QuantumCircuit(qr, anc)

# the number of iterations
num_iterations = 3

# Let's do Grover search
initialization(grover_circuit)

for i in range(0, num_iterations):
    oracle(grover_circuit)
    diffusion(grover_circuit)

# Clear the ancilla bit
grover_circuit.h(n)
grover_circuit.x(n)

grover_circuit.draw(output="mpl", idle_wires=False, fold=-1, scale=0.5)

grover_circuit.measure_all()

# Define backend
backend = AerSimulator()

# Transpile to backend
pm = generate_preset_pass_manager(backend=backend, optimization_level=1)
isa_qc = pm.run(grover_circuit)

# Run the job
sampler = Sampler(backend)
job = sampler.run([isa_qc], shots=1024)
result = job.result()

# Print the results
counts = result[0].data.meas.get_counts()
print(counts)

# Plot the counts in a histogram
plot_histogram(counts)

{'0010': 88, '0001': 103, '0000': 94, '0111': 334, '0100': 112, '0110': 106, '0101': 99, '0011': 88}

$|0111\rangle$ viene ancora osservato con la probabilità più alta, sebbene la probabilità di ottenere la risposta corretta sia leggermente diminuita.

E con 4 iterazioni?

Ora proviamo a iterare 4 volte.

n = 3
qr = QuantumRegister(n, "q")
anc = QuantumRegister(1, "ancillary")
grover_circuit = QuantumCircuit(qr, anc)

# the number of iterations
num_iterations = 4

# Let's do Grover search
initialization(grover_circuit)

for i in range(0, num_iterations):
    oracle(grover_circuit)
    diffusion(grover_circuit)

# Clear the ancilla bit
grover_circuit.h(n)
grover_circuit.x(n)

grover_circuit.draw(output="mpl", idle_wires=False, fold=-1, scale=0.5)

grover_circuit.measure_all()

# Define backend
backend = AerSimulator()

# Transpile to backend
pm = generate_preset_pass_manager(backend=backend, optimization_level=1)
isa_qc = pm.run(grover_circuit)

# Run the job
sampler = Sampler(backend)
job = sampler.run([isa_qc])
result = job.result()

# Print the results
counts = result[0].data.meas.get_counts()
print(counts)

# Plot the counts in a histogram
plot_histogram(counts)

{'0110': 127, '0000': 135, '0001': 150, '0101': 164, '0010': 153, '0011': 131, '0100': 150, '0111': 14}

$|0111\rangle$ viene osservato con la probabilità più bassa, e la probabilità di ottenere la risposta corretta è diminuita ulteriormente. Questo dimostra l'importanza di scegliere il numero ottimale di iterazioni per l'algoritmo di Grover al fine di ottenere i migliori risultati.

# See the version of Qiskit
import qiskit

qiskit.__version__

'2.0.2'