Algoritmo di Grover

Per questo modulo Qiskit in Classrooms, gli studenti devono disporre di un ambiente Python funzionante con i seguenti pacchetti installati:

• qiskit v2.1.0 o successivo
• qiskit-ibm-runtime v0.40.1 o successivo
• qiskit-aer v0.17.0 o successivo
• qiskit.visualization
• numpy
• pylatexenc

Per configurare e installare i pacchetti sopra indicati, consulta la guida Installa Qiskit. Per eseguire job su computer quantistici reali, gli studenti dovranno creare un account IBM Quantum® seguendo i passaggi descritti nella guida Configura il tuo account IBM Cloud.

Questo modulo è stato testato e ha utilizzato 12 secondi di tempo QPU. Si tratta di una stima indicativa; l'utilizzo effettivo può variare.

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

# Uncomment and modify this line as needed to install dependencies
#!pip install 'qiskit>=2.1.0' 'qiskit-ibm-runtime>=0.40.1' 'qiskit-aer>=0.17.0' 'numpy' 'pylatexenc'

Introduzione

L'algoritmo di Grover è un algoritmo quantistico fondamentale che affronta il problema della ricerca non strutturata: dato un insieme di $N$ elementi e un modo per verificare se un determinato elemento è quello che cerchi, quanto velocemente puoi trovare l'elemento desiderato? Nel calcolo classico, se i dati non sono ordinati e non c'è struttura da sfruttare, l'approccio migliore è verificare gli elementi uno per uno, portando a una complessità di query di $O(N)$ — in media, sarà necessario controllare circa metà degli elementi prima di trovare il bersaglio.

L'algoritmo di Grover, introdotto da Lov Grover nel 1996, dimostra come un computer quantistico possa risolvere questo problema in modo molto più efficiente, richiedendo solo $O(\sqrt{N})$ passi per trovare l'elemento marcato con alta probabilità. Questo rappresenta un incremento di velocità quadratico rispetto ai metodi classici, significativo per grandi dataset.

L'algoritmo opera nel seguente contesto:

• Impostazione del problema: hai una funzione $f(x)$ che restituisce 1 se $x$ è l'elemento che cerchi, e 0 altrimenti. Questa funzione è spesso chiamata oracolo o black box, poiché puoi apprendere qualcosa sui dati solo interrogando $f(x)$.
• Utilità del quantistico: mentre gli algoritmi classici per questo problema richiedono in media $N/2$ query, l'algoritmo di Grover riesce a trovare la soluzione in circa $\pi\sqrt{N}/4$ query, il che è molto più veloce per grandi $N$.
• Come funziona (ad alto livello):
  • Il computer quantistico crea prima una sovrapposizione di tutti i possibili stati, rappresentando tutti gli elementi possibili contemporaneamente.
  • Poi applica ripetutamente una sequenza di operazioni quantistiche (l'iterazione di Grover) che amplifica la probabilità della risposta corretta e riduce le altre.
  • Dopo un numero sufficiente di iterazioni, la misurazione dello stato quantistico restituisce la risposta corretta con alta probabilità.

Ecco un diagramma molto semplificato dell'algoritmo di Grover che tralascia molti dettagli. Per un diagramma più dettagliato, consulta questo articolo.

Alcune osservazioni sull'algoritmo di Grover:

• È ottimale per la ricerca non strutturata: nessun algoritmo quantistico può risolvere il problema con meno di $O(\sqrt{N})$ query.
• Offre solo un incremento quadratico, non esponenziale — a differenza di altri algoritmi quantistici (ad esempio, l'algoritmo di Shor per la fattorizzazione).
• Ha implicazioni pratiche, come la potenziale accelerazione degli attacchi a forza bruta sui sistemi crittografici, sebbene l'incremento non sia sufficiente a violare da solo la maggior parte della crittografia moderna.

Per gli studenti universitari che hanno familiarità con i concetti di base del calcolo e i modelli di query, l'algoritmo di Grover offre una chiara illustrazione di come il calcolo quantistico possa superare gli approcci classici per determinati problemi, anche quando il miglioramento è "solo" quadratico. Serve inoltre come punto di partenza per comprendere algoritmi quantistici più avanzati e il potenziale più ampio del calcolo quantistico.

L'amplificazione dell'ampiezza è un algoritmo quantistico di uso generale, o sottoalgoritmo, che può essere usato per ottenere un incremento quadratico rispetto a un certo numero di algoritmi classici. L'algoritmo di Grover è stato il primo a dimostrare questo incremento sui problemi di ricerca non strutturata. La formulazione di un problema di ricerca di Grover richiede una funzione oracolo che contrassegna uno o più stati della base computazionale come gli stati che vogliamo trovare, e un circuito di amplificazione che aumenta l'ampiezza degli stati contrassegnati, sopprimendo di conseguenza gli stati rimanenti.

Qui mostriamo come costruire gli oracoli di Grover e usare il GroverOperator dalla libreria di circuito di Qiskit per impostare facilmente un'istanza di ricerca di Grover. La primitiva Sampler di runtime consente un'esecuzione fluida dei circuiti di Grover.

Matematica

Supponiamo che esista una funzione $f$ che mappa stringhe binarie in una singola variabile binaria, ovvero

$$f: \Sigma^n \rightarrow \Sigma$$

Un esempio definito su $\Sigma^6$ è

$$f(x)= \begin{cases} 1 \qquad \text{if }x=\{010101\}\\ 0 \qquad \text{otherwise } \end{cases}$$

Un altro esempio definito su $\Sigma^{2n}$ è

$$f(x)= \begin{cases} 1 \qquad \text{if equal numbers of 1's and 0's in string}\\ 0 \qquad \text{otherwise } \end{cases}$$

Il tuo compito è trovare gli stati quantistici corrispondenti agli argomenti $x$ di $f(x)$ che vengono mappati a 1. In altre parole, trovare tutti gli $\{x_1\}\in \Sigma^n$ tali che $f(x_1)=1$ (oppure, se non esiste soluzione, segnalarlo). Indicheremo le non-soluzioni con $x_0$. Naturalmente, questo lo faremo su un computer quantistico, usando stati quantistici, quindi è utile esprimere queste stringhe binarie come stati:

$$\{|x_1\rangle\} \in |\Sigma^n\rangle$$

Usando la notazione degli stati quantistici (notazione di Dirac), stiamo cercando uno o più stati speciali $\{|x_1\rangle\}$ in un insieme di $N=2^n$ stati possibili, dove $n$ è il numero di qubit, e con le non-soluzioni indicate da $\{|x_0\rangle\}.$

Possiamo pensare alla funzione $f$ come fornita da un oracolo: una black box che possiamo interrogare per determinarne l'effetto su uno stato $|x\rangle.$ In pratica, spesso conosceremo la funzione, ma potrebbe essere molto complicata da implementare, il che significa che ridurre il numero di query o applicazioni di $f$ potrebbe essere importante. In alternativa, possiamo immaginare un paradigma in cui una persona interroga un oracolo controllato da un'altra persona, in modo che non conosciamo la funzione oracolo, ma solo la sua azione su determinati stati dall'interrogazione.

Questo è un "problema di ricerca non strutturata", nel senso che non c'è nulla di speciale in $f$ che ci aiuti nella ricerca. Le uscite non sono ordinate né si sa che le soluzioni si raggruppino, e così via. Considera i vecchi elenchi telefonici cartacei come analogia. Questa ricerca non strutturata sarebbe come sfogliarlo cercando un certo numero, e non come scorrere un elenco alfabetico di nomi.

Nel caso in cui si cerchi una singola soluzione, classicamente, questo richiede un numero di query lineare in $N$. Chiaramente potresti trovare una soluzione al primo tentativo, oppure non trovare nessuna soluzione nei primi $N-1$ tentativi, tanto che devi interrogare il $N$-esimo input per verificare se esiste una soluzione. Poiché le funzioni non hanno struttura sfruttabile, saranno necessari $N/2$ tentativi in media. L'algoritmo di Grover richiede un numero di query o computazioni di $f$ che scala come $\sqrt{N}.$

Schema dei circuit nell'algoritmo di Grover

Una descrizione matematica completa dell'algoritmo di Grover si trova, ad esempio, in Fondamenti degli algoritmi quantistici, un corso di John Watrous su IBM Quantum Learning. Un trattamento sintetico è fornito in un'appendice alla fine di questo modulo. Per ora, esamineremo solo la struttura complessiva del circuito quantistico che implementa l'algoritmo di Grover.

L'algoritmo di Grover può essere suddiviso nelle seguenti fasi:

• Preparazione di una sovrapposizione iniziale (applicando Hadamard gate a tutti i qubit)
• "Marcatura" dello/degli stato/i bersaglio con un'inversione di fase
• Una fase di "diffusione" in cui Hadamard gate e un'inversione di fase vengono applicati a tutti i qubit.
• Possibili ripetizioni delle fasi di marcatura e diffusione per massimizzare la probabilità di misurare lo stato bersaglio
• Misurazione

Spesso, il gate di marcatura $Z_f$ e i livelli di diffusione composti da $H,$ $Z_{\text{OR}},$ e $H$ vengono collettivamente denominati "operatore di Grover". In questo diagramma è mostrata una sola ripetizione dell'operatore di Grover.

Il Hadamard gate $H$ è ben noto e ampiamente utilizzato nel calcolo quantistico. Il Hadamard gate crea stati di sovrapposizione. In particolare, è definito da

$$H|0\rangle = \frac{1}{\sqrt{2}}\left(|0\rangle+|1\rangle\right)\\ H|1\rangle = \frac{1}{\sqrt{2}}\left(|0\rangle-|1\rangle\right)$$

La sua azione su qualsiasi altro stato è definita per linearità. In particolare, un livello di Hadamard gate ci permette di passare dallo stato iniziale con tutti i qubit in $|0\rangle$ (indicato $|0\rangle^{\otimes n}$) a uno stato in cui ciascun qubit ha una certa probabilità di essere misurato in $|0\rangle$ o $|1\rangle$; questo ci consente di sondare lo spazio di tutti gli stati possibili in modo diverso rispetto al calcolo classico.

Una proprietà corollario importante del Hadamard gate è che applicarlo una seconda volta può disfare tali stati di sovrapposizione:

$$H\frac{1}{\sqrt{2}}\left(|0\rangle+|1\rangle\right)=|0\rangle\\ H\frac{1}{\sqrt{2}}\left(|0\rangle-|1\rangle\right)=|1\rangle$$

Questo sarà importante tra poco.

Verifica la tua comprensione

Leggi la domanda qui sotto, rifletti sulla tua risposta, poi clicca sul triangolo per rivelare la soluzione.

A partire dalla definizione del Hadamard gate, dimostra che una seconda applicazione del Hadamard gate disfà le sovrapposizioni come affermato sopra.

Risposta:

Quando applichiamo X allo stato $|+\rangle$, otteniamo il valore +1, e allo stato $|-\rangle$ otteniamo -1; quindi se avessimo una distribuzione 50-50, otterremmo un valore atteso di 0.

Il gate $Z_\text{OR}$ è meno comune, ed è definito da

$$\text{Z}_\text{OR}|x\rangle = \begin{cases} |x\rangle & \text{if } x = 0^n \\ -|x\rangle & \text{if } x \neq 0^n \end{cases} \qquad \forall x \in \Sigma^n$$

Infine, il gate $Z_f$ è definito da

$$Z_f:|x\rangle \rightarrow (-1)^{f(x)}|x\rangle \qquad \forall x \in \Sigma^n$$

Nota che l'effetto di $Z_f$ è invertire il segno dello stato bersaglio per cui $f(x) = 1$ e lasciare invariati gli altri stati.

A un livello molto alto e astratto, puoi pensare ai passi nel circuito nei seguenti modi:

• Primo livello di Hadamard: mette i qubit in una sovrapposizione di tutti gli stati possibili.
• $Z_f$: contrassegna lo/gli stato/i bersaglio aggiungendo un segno "-" davanti. Questo non cambia immediatamente le probabilità di misurazione, ma cambia come lo stato bersaglio si comporterà nei passi successivi.
• Un altro livello di Hadamard: il segno "-" introdotto nel passo precedente cambierà il segno relativo tra alcuni termini. Poiché i Hadamard gate trasformano una miscela di stati computazionali $(|0\rangle+|1\rangle)/\sqrt{2}$ nello stato computazionale $|0\rangle,$ e trasformano $(|0\rangle-|1\rangle)/\sqrt{2}$ in $|1\rangle$, questa differenza di segno relativo ora può iniziare a giocare un ruolo in quali stati vengono misurati.
• Viene applicato un ultimo livello di Hadamard gate, poi vengono effettuate le misurazioni. Vedremo in maggiore dettaglio come funziona questo nella prossima sezione.

Esempio

Per capire meglio come funziona l'algoritmo di Grover, lavoriamo su un piccolo esempio a due qubit. Questa parte può essere considerata facoltativa per chi non si concentra sulla meccanica quantistica e la notazione di Dirac. Ma per chi spera di lavorare in modo sostanziale con i computer quantistici, è altamente consigliata.

Ecco il diagramma del circuito con gli stati quantistici etichettati in vari punti. Nota che con soli due qubit, ci sono solo quattro stati possibili che potrebbero essere misurati in qualsiasi circostanza: $|00\rangle$, $|01\rangle$, $|10\rangle$ e $|11\rangle$.

Supponiamo che l'oracolo ($Z_f$, a noi sconosciuto) contrassegni lo stato $|01\rangle$. Esamineremo le azioni di ciascun insieme di gate quantistici, incluso l'oracolo, e vedremo quale distribuzione di stati possibili emerge al momento della misurazione. All'inizio, abbiamo

$$|\psi_0\rangle = |00\rangle$$

Usando la definizione dei Hadamard gate, abbiamo

$$|\psi_1\rangle = \frac{1}{2}\left(|0\rangle+|1\rangle\right)\left(|0\rangle+|1\rangle\right)=\frac{1}{2}\left(|00\rangle+|01\rangle+|10\rangle+|11\rangle\right)$$

Ora l'oracolo contrassegna lo stato bersaglio:

$$|\psi_2\rangle = \frac{1}{2}\left(|00\rangle-|01\rangle+|10\rangle+|11\rangle\right)$$

Nota che in questo stato, tutti e quattro i possibili risultati hanno la stessa probabilità di essere misurati. Hanno tutti un peso di magnitudine $1/2,$ il che significa che ognuno ha una probabilità $|1/2|^2=1/4$ di essere misurato. Quindi, sebbene lo stato $|01\rangle$ sia contrassegnato dalla fase "-", questo non ha ancora aumentato la probabilità di misurare quello stato. Continuiamo applicando il successivo livello di Hadamard gate.

$$\begin{aligned} |\psi_3\rangle = &\frac{1}{4}\left(|00\rangle+|01\rangle+|10\rangle+|11\rangle\right)\\ -&\frac{1}{4}\left(|00\rangle-|01\rangle+|10\rangle-|11\rangle\right)\\ +&\frac{1}{4}\left(|00\rangle+|01\rangle-|10\rangle-|11\rangle\right)\\ +&\frac{1}{4}\left(|00\rangle-|01\rangle-|10\rangle+|11\rangle\right) \end{aligned}$$

Combinando i termini simili, troviamo

$$|\psi_3\rangle = \frac{1}{2}\left(|00\rangle+|01\rangle-|10\rangle+|11\rangle\right)$$

Ora $Z_{\text{OR}}$ inverte il segno su tutti gli stati tranne $|00\rangle$:

$$|\psi_4\rangle = \frac{1}{2}\left(|00\rangle-|01\rangle+|10\rangle-|11\rangle\right)$$

E infine, applichiamo l'ultimo livello di Hadamard gate:

$$\begin{aligned} |\psi_5\rangle =&\frac{1}{4}\left(|00\rangle+|01\rangle+|10\rangle+|11\rangle\right)\\ -&\frac{1}{4}\left(|00\rangle-|01\rangle+|10\rangle-|11\rangle\right)\\ +&\frac{1}{4}\left(|00\rangle+|01\rangle-|10\rangle-|11\rangle\right)\\ -&\frac{1}{4}\left(|00\rangle-|01\rangle-|10\rangle+|11\rangle\right) \end{aligned}$$

Vale la pena combinare questi termini per convincersi che il risultato è effettivamente:

$$|\psi_5\rangle =|01\rangle$$

Ovvero, la probabilità di misurare $|01\rangle$ è del 100% (in assenza di rumore ed errori) e la probabilità di misurare qualsiasi altro stato è zero.

Questo esempio a due qubit è stato un caso particolarmente pulito; l'algoritmo di Grover non sempre porta a una probabilità del 100% di misurare lo stato bersaglio. Piuttosto, amplifica la probabilità di misurare lo stato bersaglio. Inoltre, l'operatore di Grover potrebbe dover essere ripetuto più di una volta.

Nella prossima sezione, metteremo in pratica questo algoritmo usando veri computer quantistici IBM®.

Avvertenza ovvia

Per applicare l'algoritmo di Grover, abbiamo dovuto costruire l'operatore di Grover, il che significa che dobbiamo essere in grado di invertire la fase sugli stati che soddisfano i nostri criteri di soluzione. Questo solleva la domanda: se conosciamo il nostro insieme di soluzioni così bene da poter progettare un circuito quantistico per etichettarle ciascuna, cosa stiamo cercando?! La risposta è triplice, e la rivisiteremo durante il tutorial:

(1) Questi tipi di algoritmi di query spesso coinvolgono due parti: una che possiede l'oracolo che stabilisce i criteri di soluzione, e un'altra che cerca di indovinare/trovare uno stato soluzione. Il fatto che una persona possa costruire l'oracolo non nega la necessità della ricerca.

(2) Esistono problemi per i quali è più facile specificare un criterio di soluzione che trovare la soluzione. L'esempio più noto è probabilmente l'identificazione dei fattori primi di grandi numeri. L'algoritmo di Grover non è particolarmente efficace per risolvere quel problema specifico; useremmo l'algoritmo di Shor per la fattorizzazione prima. Questo è solo un esempio per sottolineare che conoscere il criterio sul comportamento di uno stato non è sempre la stessa cosa che conoscere lo stato.

(3) L'algoritmo di Grover non restituisce solo dati classici. È vero che, se misuriamo lo stato finale dopo $t$ ripetizioni dell'operatore di Grover, otterremo probabilmente informazioni classiche che identificano lo stato soluzione. Ma cosa succede se non vogliamo informazioni classiche; cosa succede se vogliamo uno stato soluzione preparato su un computer quantistico per essere ulteriormente utilizzato in un altro algoritmo? L'algoritmo di Grover produce effettivamente uno stato quantistico con le soluzioni fortemente ponderate. Quindi potresti aspettarti di trovare l'algoritmo di Grover come sottoalgoritmo in algoritmi quantistici più complessi.

Con questo in mente, lavoriamo attraverso diversi esempi. Inizieremo con un esempio in cui lo stato soluzione è chiaramente specificato così da poter seguire la logica dell'algoritmo, e passeremo ad esempi in cui l'utilità dell'algoritmo di Grover diventa più chiara.

Importazioni generali e approccio

Iniziamo importando i pacchetti necessari.

# 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

Durante questo e altri tutorial, useremo un framework per il calcolo quantistico noto come "Qiskit patterns", che suddivide i flussi di lavoro nei seguenti passaggi:

• Passo 1: Mappa gli input classici in un problema quantistico
• Passo 2: Ottimizza il problema per l'esecuzione quantistica
• Passo 3: Esegui usando le Qiskit Runtime Primitives
• Passo 4: Post-elaborazione e analisi classica

Generalmente seguiremo questi passaggi, anche se non sempre li etichetteremo esplicitamente.

Attività 1: Trovare un singolo stato bersaglio dato

Passo 1: Mappa gli input classici in un problema quantistico

Abbiamo bisogno del gate di query di fase per applicare una fase complessiva (-1) agli stati soluzione, e lasciare invariati gli stati non-soluzione. Un altro modo per dirlo è che 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. Questo si fa usando un gate Z controllato, o la sua generalizzazione multi-controllata su $N$ qubit. Per capire come funziona, considera un esempio specifico di una bitstring {110}. Vogliamo un circuito che agisca su uno stato $|\psi\rangle = |q_2,q_1,q_0\rangle$ e applichi una fase se $|\psi\rangle = |011\rangle$ (dove abbiamo invertito l'ordine della stringa binaria, a causa della notazione in Qiskit, che mette il qubit meno significativo (spesso 0) a destra).

Quindi, vogliamo un circuito $Z_f$ che realizzi

$$Z_f|\psi\rangle = \begin{cases} -|\psi\rangle \qquad \text{if} \qquad |\psi\rangle = |011\rangle \\ |\psi\rangle \qquad \text{if} \qquad |\psi\rangle \neq |011\rangle\end{cases}$$

Possiamo usare il gate multi-controllo multi-bersaglio (MCMTGate) per applicare un gate Z controllato da tutti i qubit (inversione di fase se tutti i qubit sono nello stato $|1\rangle$). Naturalmente, alcuni dei qubit nel nostro stato desiderato potrebbero essere $|0\rangle$. Pertanto, per quei qubit dobbiamo prima applicare un gate X, poi eseguire il gate Z multi-controllato, poi applicare un altro gate X per annullare il cambiamento. Il MCMTGate ha questo aspetto:

mcmt_ex = QuantumCircuit(3)
mcmt_ex.compose(MCMTGate(ZGate(), 3 - 1, 1), inplace=True)
mcmt_ex.draw(output="mpl", style="iqp")

Nota che molti qubit possono essere coinvolti nel processo di controllo (qui tre qubit lo sono), ma nessun singolo qubit è designato come bersaglio. Questo perché l'intero stato riceve un segno "-" complessivo (inversione di fase); il gate influenza tutti i qubit in modo equivalente. Questo è diverso da molti altri gate multi-qubit, come il gate CX, che ha un singolo qubit di controllo e un singolo qubit bersaglio.

Nel codice seguente, definiamo un gate di query di fase (o oracolo) che fa quello che abbiamo appena descritto: contrassegna uno o più stati della base di input definiti attraverso la loro rappresentazione come bitstring. Il gate MCMT è usato per implementare il gate Z multi-controllato.

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 bitstring to match Qiskit bit-ordering
        rev_target = target[::-1]
        # Find the indices of all the '0' elements in bitstring
        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 bitstring has a '0' entry
        qc.x(zero_inds)
        qc.compose(MCMTGate(ZGate(), num_qubits - 1, 1), inplace=True)
        qc.x(zero_inds)
    return qc

Ora scegliamo uno stato "contrassegnato" specifico come bersaglio e applichiamo la funzione che abbiamo appena definito. Vediamo che tipo di circuito ha creato.

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

Se i qubit 1-3 sono nello stato $|1\rangle$ e il qubit 0 si trova inizialmente nello stato $|0\rangle$, il primo gate X invertirà il qubit 0 a $|1\rangle$ e tutti i qubit saranno in $|1\rangle.$ Ciò significa che il gate MCMT applicherà un cambio di segno complessivo o inversione di fase, come desiderato. Per qualsiasi altro caso, o i qubit 1-3 sono nello stato $|0\rangle$, oppure il qubit 0 viene invertito allo stato $|0\rangle$, e l'inversione di fase non verrà applicata. Vediamo che questo circuito contrassegna effettivamente il nostro stato desiderato $|0111\rangle,$ o la bitstring {1110}. L'operatore di Grover completo è composto dal gate di query di fase (oracolo), dai livelli di Hadamard gate e dall'operatore $Z_\text{OR}$. Possiamo usare il grover_operator integrato per costruire questo dall'oracolo che abbiamo definito sopra.

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

Come abbiamo argomentato in precedenza, potrebbe essere necessario applicare l'operatore di Grover più volte. Il numero ottimale di iterazioni, $t,$ per massimizzare l'ampiezza dello stato bersaglio in assenza di rumore può essere ottenuto da questa espressione:

$$(2t+1)\theta = (2t+1)\sin^{-1}\left( \sqrt{\frac{|A_1|}{N}}\right) \approx (2t+1)\sqrt{\frac{|A_1|}{N}} \approx \frac{\pi}{2}\\ t\approx \frac{\pi}{4} \sqrt{\frac{N}{|A_1|}}-\frac{1}{2}$$

Qui $A_1$ è il numero di soluzioni o stati bersaglio. Sui moderni computer quantistici rumorosi, il numero ottimale di iterazioni a livello sperimentale potrebbe essere diverso — ma qui calcoliamo e usiamo questo numero teorico ottimale usando $A_1=1$.

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

3

Costruiamo ora un circuito che include i Hadamard gate iniziali per creare una sovrapposizione di tutti gli stati possibili, e applichiamo l'operatore di Grover il numero ottimale di volte.

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

Abbiamo costruito il nostro circuito di Grover!

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

Abbiamo definito il nostro circuito quantistico astratto, ma dobbiamo riscriverlo in termini di gate nativi del computer quantistico che vogliamo effettivamente usare. Dobbiamo anche specificare quali qubit del computer quantistico utilizzare. Per queste e altre ragioni, dobbiamo ora transpilare il nostro circuito. Prima di tutto, specifichiamo il computer quantistico che desideriamo usare.

Di seguito è presente del codice per salvare le tue credenziali al primo utilizzo. Assicurati di eliminare queste informazioni dal notebook dopo averle salvate nel tuo ambiente, in modo che le tue credenziali non vengano accidentalmente condivise quando condividi il notebook. Consulta Configura il tuo account IBM Cloud e Inizializza il servizio in un ambiente non attendibile per ulteriori indicazioni.

# To run on hardware, select the backend with the fewest number of jobs in the queue
from qiskit_ibm_runtime import QiskitRuntimeService

# Syntax for first saving your token.  Delete these lines after saving your credentials.
# QiskitRuntimeService.save_account(channel='ibm_quantum_platform', instance = '<YOUR_IBM_INSTANCE_CRN>', token='<YOUR_API_KEY>', overwrite=True, set_as_default=True)
# service = QiskitRuntimeService(channel='ibm_quantum_platform')

# Load saved credentials
service = QiskitRuntimeService()

backend = service.least_busy(operational=True, simulator=False)
backend.name

qiskit_runtime_service._resolve_cloud_instances:WARNING:2025-08-08 14:14:19,931: Default instance not set. Searching all available instances.

'ibm_brisbane'

Ora usiamo un pass manager preimpostato per ottimizzare il nostro circuito quantistico per il backend selezionato.

target = backend.target
pm = generate_preset_pass_manager(target=target, optimization_level=3)

circuit_isa = pm.run(qc)
# The transpiled circuit will be very large. Only draw it if you are really curious.
# circuit_isa.draw(output="mpl", idle_wires=False, style="iqp")

Vale la pena notare che la profondità del circuito quantistico transpilato è sostanziale.

print("The total depth is ", circuit_isa.depth())
print(
    "The depth of two-qubit gates is ",
    circuit_isa.depth(lambda instruction: instruction.operation.num_qubits == 2),
)

The total depth is  439
The depth of two-qubit gates is  113

Questi sono in realtà numeri piuttosto grandi, anche per questo caso semplice. Poiché tutti i gate quantistici (e specialmente i gate a due qubit) sono soggetti a errori e rumore, una serie di oltre 100 gate a due qubit non produrrebbe altro che rumore se i qubit non fossero estremamente performanti. Vediamo come si comportano.

Esecuzione con le primitive Qiskit

Vogliamo effettuare molte misurazioni e vedere quale stato è il più probabile. Un'amplificazione dell'ampiezza di questo tipo è un problema di campionamento adatto all'esecuzione con la primitiva Qiskit Runtime Sampler.

Nota che il metodo run() di Qiskit Runtime SamplerV2 accetta un iterabile di primitive unified blocks (PUB). Per Sampler, ogni PUB è un iterabile nel formato (circuit, parameter_values). Come minimo, tuttavia, richiede un elenco di circuiti quantistici.

# To run on a real quantum computer (this was tested on a Heron r2 processor and used 4 sec. of QPU time)

from qiskit_ibm_runtime import SamplerV2 as Sampler

sampler = Sampler(mode=backend)
sampler.options.default_shots = 10_000
result = sampler.run([circuit_isa]).result()
dist = result[0].data.meas.get_counts()

Per sfruttare al meglio questa esperienza, ti raccomandiamo vivamente di eseguire i tuoi esperimenti sui veri computer quantistici disponibili da IBM Quantum. Se però hai esaurito il tuo tempo QPU, puoi decommentare le righe seguenti per completare questa attività usando un simulatore.

# To run on local simulator:
# from qiskit.primitives import StatevectorSampler as Sampler
# sampler = Sampler()
# result = sampler.run([qc]).result()
# dist = result[0].data.meas.get_counts()

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

Ora possiamo tracciare i risultati del campionamento in un istogramma.

plot_distribution(dist)

Vediamo che l'algoritmo di Grover ha restituito lo stato desiderato con la probabilità di gran lunga più alta, almeno un ordine di grandezza superiore rispetto alle altre opzioni. Nell'attività successiva, useremo l'algoritmo in un modo più coerente con il workflow a due parti di un algoritmo di query.

Verifica la tua comprensione

Leggi le domande qui sotto, pensa alla tua risposta, poi clicca sul triangolo per rivelare la soluzione.

Abbiamo appena cercato una singola soluzione in un insieme di $2^4=16$ stati possibili. Abbiamo determinato che il numero ottimale di ripetizioni dell'operatore di Grover è $t=3$. Questo numero ottimale sarebbe aumentato o diminuito se avessimo cercato (a) una qualsiasi tra più soluzioni, oppure (b) una singola soluzione in uno spazio con più stati possibili?

Risposta:

Ricorda che finché il numero di soluzioni è piccolo rispetto all'intero spazio delle soluzioni, possiamo espandere la funzione seno attorno ad angoli piccoli e usare

$$(2t+1)\theta = (2t+1) \sin^{-1}{\sqrt{\frac{|\mathcal{A}_1|}{N}}}\approx (2t+1) \sqrt{\frac{|\mathcal{A}_1|}{N}} \approx \pi/2\\ t \approx \frac{\pi}{4}\sqrt{\frac{N}{|\mathcal{A}_1|}}-\frac{1}{2}$$

(a) Dall'espressione precedente vediamo che aumentare il numero di stati soluzione diminuisce il numero di iterazioni. A condizione che la frazione $\frac{|\mathcal{A}_1|}{N}$ sia ancora piccola, possiamo descrivere come $t$ diminuirebbe: $t~\frac{1}{\sqrt{|\mathcal{A}_1|}}.$

(b) All'aumentare dello spazio delle soluzioni possibili ($N$), il numero di iterazioni richieste aumenta, ma solo come $t~\sqrt{N}$.

Supponi di poter aumentare la dimensione della stringa di bit target a piacere e di ottenere comunque che lo stato target abbia un'ampiezza di probabilità almeno un ordine di grandezza superiore a qualsiasi altro stato. Significa che potremmo usare l'algoritmo di Grover per trovare in modo affidabile lo stato target?

Risposta:

No. Supponiamo di ripetere la prima attività con 20 qubit ed eseguire il circuito quantistico un numero di volte num_shots = 10,000. Una distribuzione di probabilità uniforme significherebbe che ogni stato ha una probabilità di $10,000/2^{20}=0.00954$ di essere misurato anche solo una volta. Se la probabilità di misurare lo stato target fosse 10 volte quella dei non-soluzioni (e la probabilità di ciascuna non-soluzione fosse corrispondentemente leggermente ridotta), ci sarebbe solo circa il 10% di possibilità di misurare lo stato target anche una sola volta. Sarebbe altamente improbabile misurare lo stato target più volte, il che lo renderebbe indistinguibile dai numerosi stati non-soluzione ottenuti casualmente. La buona notizia è che possiamo ottenere risultati a fedeltà ancora maggiore usando la soppressione e la mitigazione degli errori.

Attività 2: Un workflow accurato per l'algoritmo di query

Inizieremo questa attività esattamente come la prima, tranne che ora ti accoppierai con un altro appassionato di Qiskit. Sceglierai una stringa di bit segreta, e il tuo partner ne sceglierà una (generalmente) diversa. Ognuno di voi genererà un circuito quantistico che funziona come oracolo e ve li scambierete. Utilizzerai poi l'algoritmo di Grover con quell'oracolo per determinare la stringa di bit segreta del tuo partner.

Passo 1: Mappare gli input classici in un problema quantistico

Usando la funzione grover_oracle definita sopra, costruisci un circuito oracolo per uno o più stati marcati. Assicurati di dire al tuo partner quanti stati hai marcato, in modo che possa applicare l'operatore di Grover il numero ottimale di volte. Non rendere la tua stringa di bit troppo lunga. 3-5 bit dovrebbero funzionare senza troppe difficoltà. Stringhe più lunghe risulterebbero in circuiti profondi che richiedono tecniche più avanzate come la mitigazione degli errori.

# Modify the marked states to mark those you wish to target.
marked_states = ["1000"]
oracle = grover_oracle(marked_states)

Ora hai creato un circuito quantistico che inverte la fase del tuo stato target. Puoi salvare questo circuito come my_circuit.qpy usando la sintassi seguente.

from qiskit import qpy

# Save to a QPY file at a location where you can easily find it.
# You might want to specify a global address.
with open("C:\\Users\\...put your own address here...\\my_circuit.qpy", "wb") as f:
    qpy.dump(oracle, f)

Ora invia questo file al tuo partner (via email, servizio di messaggistica, un repository condiviso, ecc.). Chiedi al tuo partner di inviarti il suo circuito. Assicurati di salvare il file in un posto facilmente accessibile. Una volta ricevuto il circuito del tuo partner, potresti visualizzarlo — ma questo viola il modello di query. Ossia, stiamo modellando una situazione in cui puoi interrogare l'oracolo (usare il circuito oracolo) ma non esaminarlo per determinare quale stato ha come target.

from qiskit import qpy

# Load the circuit from your partner's qpy file from the folder where you saved it.
with open("C:\\Users\\...file location here...\\my_circuit.qpy", "rb") as f:
    circuits = qpy.load(f)

# qpy.load always returns a list of circuits
oracle_partner = circuits[0]

# You could visualize the circuit, but this would break the model of a query algorithm.
# oracle_partner.draw("mpl")

Chiedi al tuo partner quanti stati target ha codificato e inseriscilo qui sotto.

# Update according to your partner's number of target states.
num_marked_states = 1

Questo viene usato nell'espressione successiva per determinare il numero ottimale di iterazioni di Grover.

grover_op = grover_operator(oracle_partner)
optimal_num_iterations = math.floor(
    math.pi / (4 * math.asin(math.sqrt(num_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()

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

Questo procede esattamente come prima.

# 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)
backend.name

target = backend.target
pm = generate_preset_pass_manager(target=target, optimization_level=3)
circuit_partner_isa = pm.run(qc)

Passo 3: Esecuzione con le primitive Qiskit

Anche questo è identico al processo nella prima attività.

# To run on a real quantum computer (this was tested on a Heron r2 processor and used 4 seconds of QPU time)

from qiskit_ibm_runtime import SamplerV2 as Sampler

sampler = Sampler(mode=backend)
sampler.options.default_shots = 10_000
result = sampler.run([circuit_partner_isa]).result()
dist = result[0].data.meas.get_counts()

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

Ora mostra un istogramma dei risultati del campionamento. Uno o più stati dovrebbero avere una probabilità di misurazione molto più alta rispetto agli altri. Comunicali al tuo partner e verifica se hai determinato correttamente gli stati target. Per impostazione predefinita, l'istogramma visualizzato è relativo allo stesso circuito della prima attività. Dovresti ottenere risultati diversi dal circuito del tuo partner.

plot_distribution(dist)

Verifica la tua comprensione

Leggi le domande o i prompt qui sotto, pensa alla tua risposta o discuti il processo con il tuo partner. Clicca sul triangolo per suggerimenti o indicazioni.

Dovresti aver determinato correttamente gli stati target del tuo partner. Se non è così, lavora con il tuo partner per identificare cosa è andato storto. Clicca qui sotto per alcune idee.

Suggerimenti:

• Visualizza/disegna il circuito del tuo partner e assicurati che sia stato caricato correttamente.
• Confronta i circuiti usati e confronta il risultato atteso con quello ottenuto.
• Controlla la profondità dei circuiti utilizzati per assicurarti che la stringa di bit non fosse troppo lunga o che il numero di iterazioni di Grover non fosse proibitivamente alto.

Se non l'hai già fatto, disegna il circuito oracolo che ti ha inviato il tuo partner. Vedi se riesci a ragionare sull'effetto di ogni gate e a dedurre quale doveva essere lo stato target. Questo sarà molto più facile nel caso di un singolo stato marcato rispetto a più stati.

Suggerimenti:

• Ricorda che il compito dell'oracolo è invertire il segno sullo stato target.
• Ricorda che l'MCMTGate inverte il segno su uno stato se e solo se tutti i qubit coinvolti nel controllo si trovano nello stato $|1\rangle$.
• Se il tuo stato target ha già $|1\rangle$ su un particolare qubit, non devi fare nulla su quel qubit. Se il tuo target ha $|0\rangle$ su un particolare qubit e vuoi che l'MCMTGate inverta il segno, devi applicare un gate X a quel qubit nel tuo oracolo (e poi annullare il gate X dopo l'MCMTGate).

Ripeti l'esperimento con un'iterazione in meno dell'operatore di Grover. Ottieni ancora la risposta corretta? Perché sì o perché no?

Guida:

Probabilmente sì, anche se potrebbe dipendere dal numero di soluzioni codificate. Questo mette in evidenza una sottigliezza: il numero "ottimale" di iterazioni di Grover è il numero che rende la probabilità di misurare lo stato marcato il più alta possibile. Ma un numero inferiore di iterazioni potrebbe comunque rendere lo stato marcato sostanzialmente più probabile degli altri stati. Quindi potresti riuscire a cavartela con meno iterazioni del numero ottimale. Questo riduce la profondità del circuito, e quindi riduce i tassi di errore.

Perché qualcuno potrebbe voler usare meno iterazioni di Grover rispetto al "numero ottimale" identificato qui?

Risposta:

Il numero "ottimale" di iterazioni di Grover è il numero che rende la probabilità di misurare lo stato marcato il più alta possibile in assenza di rumore. Ma un numero inferiore di iterazioni potrebbe comunque rendere lo stato marcato sostanzialmente più probabile degli altri stati. Quindi potresti riuscire a cavartela con meno iterazioni del numero ottimale. Questo riduce la profondità del circuito, e quindi riduce i tassi di errore.

Attività 3: Criteri diversi da una stringa di bit specifica

Come ultima illustrazione di come l'algoritmo di Grover possa essere utile nel contesto di una subroutine, immaginiamo di aver bisogno di stati quantistici con un certo numero di 1 nella rappresentazione come stringa di bit. Questo è comune in situazioni in cui sono coinvolte leggi di conservazione. Ad esempio, nel contesto della chimica quantistica, si mappa spesso lo stato 1 di un qubit all'occupazione di un orbitale elettronico. Affinché la carica sia conservata, il numero totale di 1 deve rimanere costante. Vincoli come questo sono così comuni da avere un nome speciale: vincoli di peso di Hamming, e il numero di 1 nello stato è chiamato peso di Hamming.

Passo 1:

Scriviamo prima una funzione che marca gli stati con il peso di Hamming desiderato. La scriveremo in generale per un numero non specificato di qubit num_qubits e un peso di Hamming target target_weight.

from qiskit import QuantumCircuit

def grover_oracle_hamming_weight(num_qubits, target_weight):
    """
    Build a Grover oracle that marks all states with Hamming weight == target_weight.

    Parameters:
        num_qubits (int): Number of qubits in the circuit.
        target_weight (int): The Hamming weight to mark.

    Returns:
        QuantumCircuit: Quantum circuit representing Grover oracle.
    """
    qc = QuantumCircuit(num_qubits)
    marked_count = 0
    marked_list = []
    for x in range(2**num_qubits):
        bitstr = format(x, f"0{num_qubits}b")
        if bitstr.count("1") == target_weight:
            # Count the number of target states
            marked_count = marked_count + 1
            marked_list.append(bitstr)
            # Reverse for Qiskit bit order (qubit 0 is rightmost)
            rev_target = bitstr[::-1]
            zero_inds = [i for i, b in enumerate(rev_target) if b == "0"]
            # Apply X gates to 'open' controls (where bit is 0)
            qc.x(zero_inds)
            # Multi-controlled Z (as MCX conjugated by H)
            if num_qubits == 1:
                qc.z(0)
            else:
                qc.h(num_qubits - 1)
                qc.mcx(list(range(num_qubits - 1)), num_qubits - 1)
                qc.h(num_qubits - 1)
            # Undo X gates
            qc.x(zero_inds)
    return qc, marked_count, marked_list

# Completing step 1
oracle, num_marked_states, marked_states = grover_oracle_hamming_weight(3, 2)
print(marked_states)
oracle.draw(output="mpl", style="iqp")

['011', '101', '110']

Da qui l'intero processo è identico a quello delle due attività precedenti. Per brevità, i passi dei pattern Qiskit sono mostrati solo nei commenti del codice.

from qiskit_ibm_runtime import SamplerV2 as Sampler

# Completing step 1
oracle, num_marked_states, marked_states = grover_oracle_hamming_weight(4, 2)
oracle.draw(output="mpl", style="iqp")

grover_op = grover_operator(oracle)
grover_op.decompose().draw(output="mpl", style="iqp")
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()
qc.draw(output="mpl", style="iqp")

# Step 2: Optimize for running on real quantum computers

service = QiskitRuntimeService()
backend = service.least_busy(operational=True, simulator=False)
print(backend.name)

target = backend.target
pm = generate_preset_pass_manager(target=target, optimization_level=3)
circuit_isa = pm.run(qc)

# Step 3: Execute using Qiskit primitives
# To run on a real quantum computer (this was tested on a Heron r2 processor and used 4 seconds of QPU time)

sampler = Sampler(mode=backend)
sampler.options.default_shots = 10_000
result = sampler.run([circuit_isa]).result()
dist = result[0].data.meas.get_counts()

# To run on local simulator:
# from qiskit.primitives import StatevectorSampler as Sampler
# sampler = Sampler()
# result = sampler.run([qc]).result()
# dist = result[0].data.meas.get_counts()

qiskit_runtime_service._resolve_cloud_instances:WARNING:2025-08-08 14:14:51,686: Default instance not set. Searching all available instances.

ibm_brisbane

print("The total depth is ", circuit_isa.depth())
print(
    "The depth of two-qubit gates is ",
    circuit_isa.depth(lambda instruction: instruction.operation.num_qubits == 2),
)

The total depth is  502
The depth of two-qubit gates is  130

num_marked_states

6

plot_distribution(dist)

Qui l'algoritmo di Grover ha effettivamente preparato gli stati con peso di Hamming 2 in modo che siano molto più probabili da misurare rispetto a qualsiasi altro stato, circa un ordine di grandezza più probabili.

Concetti chiave:

In questo modulo abbiamo appreso alcune caratteristiche fondamentali dell'algoritmo di Grover:

• Mentre gli algoritmi di ricerca non strutturata classici richiedono un numero di query che scala linearmente con la dimensione dello spazio, $N,$ l'algoritmo di Grover richiede un numero di query che scala come $\sqrt{N}.$
• L'algoritmo di Grover prevede la ripetizione di una serie di operazioni (comunemente chiamata "operatore di Grover") per un numero di volte $t,$ scelto in modo da rendere ottimalmente probabili gli stati target da misurare.
• L'algoritmo di Grover può essere eseguito con meno di $t$ iterazioni e amplificare comunque gli stati target.
• L'algoritmo di Grover si inserisce nel modello di query della computazione ed è più sensato quando una persona controlla la ricerca e un'altra controlla/costruisce l'oracolo. Può anche essere utile come subroutine in altri calcoli quantistici.

Domande

Domande V/F:

1. V/F L'algoritmo di Grover fornisce un miglioramento esponenziale rispetto agli algoritmi classici nel numero di query necessarie per trovare un singolo stato marcato nella ricerca non strutturata.

2. V/F L'algoritmo di Grover funziona aumentando iterativamente la probabilità che uno stato soluzione venga misurato.

3. V/F Più volte si itera l'operatore di Grover, più alta è la probabilità di misurare uno stato soluzione.

Domande a scelta multipla:

1. Seleziona l'opzione migliore per completare la frase. La strategia migliore per usare con successo l'algoritmo di Grover su moderni computer quantistici è iterare l'operatore di Grover...

• a. Solo una volta.
• b. Sempre $t$ volte, per massimizzare l'ampiezza di probabilità degli stati soluzione.
• c. Fino a $t$ volte, anche se un numero inferiore potrebbe essere sufficiente per far emergere gli stati soluzione.
• d. Non meno di 10 volte.

2. È mostrato qui un circuito di query di fase che funziona come oracolo per marcare un certo stato con un'inversione di fase. Quale dei seguenti stati viene marcato da questo circuito?

• a. $|0000\rangle$
• b. $|0101\rangle$
• c. $|0110\rangle$
• d. $|1001\rangle$
• e. $|1010\rangle$
• f. $|1111\rangle$

3. Supponi di voler cercare tre stati marcati in un insieme di 128. Qual è il numero ottimale di iterazioni dell'operatore di Grover per massimizzare le ampiezze degli stati marcati?

• a. 1
• b. 3
• c. 5
• d. 6
• e. 20
• f. 33

Domande di discussione:

1. Quali altre condizioni potresti usare in un oracolo quantistico? Considera condizioni che sono facili da enunciare o imporre su una stringa di bit ma che non consistono semplicemente nello scrivere le stringhe di bit marcate.