Algoritmo di Grover

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

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

Per configurare e installare i pacchetti di cui sopra, consultare la guida Installare Qiskit. Per poter eseguire lavori su veri computer quantistici, gli studenti dovranno creare un account con IBM Quantum® seguendo i passaggi della guida Set up your IBM Cloud account.

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

# 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 dato elemento è quello che stai cercando, quanto velocemente puoi trovare l'elemento desiderato? Nell'informatica classica, se i dati non sono ordinati e non c'è una struttura da sfruttare, l'approccio migliore è quello di controllare ogni elemento uno per uno, il che porta a una complessità di interrogazione di $O(N)$ - in media, è necessario controllare circa la metà degli elementi prima di trovare l'obiettivo.

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})$ passaggi per trovare l'oggetto contrassegnato con alta probabilità. Ciò rappresenta una velocità quadratica rispetto ai metodi classici, che è significativa per i grandi insiemi di dati.

L'algoritmo opera nel seguente contesto:

• Impostazione del problema: Si dispone di una funzione $f(x)$ che restituisce 1 se $x$ è l'elemento desiderato e 0 altrimenti. Questa funzione è spesso chiamata oracolo o scatola nera, poiché è possibile conoscere i dati solo interrogando $f(x)$.
• Utilità dei quanti: Mentre gli algoritmi classici per questo problema richiedono, in media, $N/2$ interrogazioni, l'algoritmo di Grover può trovare la soluzione in circa $\pi\sqrt{N}/4$ interrogazioni, che è molto più veloce per grandi $N$.
• Come funziona (ad alto livello):
  • Il computer quantistico crea innanzitutto una sovrapposizione di tutti gli stati possibili, rappresentando tutti gli elementi possibili in una sola volta.
  • Quindi applica ripetutamente una sequenza di operazioni quantistiche (l'iterazione di Grover) che amplifica la probabilità della risposta corretta e diminuisce le altre.
  • Dopo un numero sufficiente di iterazioni, la misurazione dello stato quantistico fornisce la risposta corretta con alta probabilità.

Ecco un diagramma molto elementare dell'algoritmo di Grover che salta molte sfumature. Per un diagramma più dettagliato, si veda questo documento.

Alcune cose da notare sull'algoritmo di Grover:

• È ottimale per la ricerca non strutturata: nessun algoritmo quantistico può risolvere il problema con meno di $O(\sqrt{N})$ query.
• Fornisce solo una velocità quadratica, non esponenziale, a differenza di altri algoritmi quantistici (ad esempio, l'algoritmo di Shor per la fattorizzazione).
• Ha implicazioni pratiche, come la possibilità di accelerare gli attacchi di forza bruta ai sistemi crittografici, anche se l'accelerazione non è sufficiente a rompere la maggior parte delle crittografie moderne.

Per gli studenti universitari che hanno familiarità con i concetti di base dell'informatica e con i modelli di interrogazione, l'algoritmo di Grover offre una chiara illustrazione di come l'informatica quantistica possa superare gli approcci classici per alcuni problemi, anche quando il miglioramento è "solo" quadratico. È anche una porta d'accesso alla comprensione di algoritmi quantistici più avanzati e al più ampio potenziale dell'informatica quantistica.

L'amplificazione di ampiezza è un algoritmo quantistico di uso generale, o una subroutine, che può essere utilizzata per ottenere una velocità quadratica rispetto a una manciata 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 contrassegna uno o più stati della base computazionale come gli stati che ci interessa trovare e un circuito di amplificazione che aumenta l'ampiezza degli stati contrassegnati, sopprimendo di conseguenza gli stati rimanenti.

In questa sede illustriamo come costruire oracoli di Grover e come utilizzare la libreria di circuiti di GroverOperator Qiskit per configurare facilmente un'istanza della ricerca di Grover. La primitiva Sampler IBM Quantum consente l'esecuzione senza interruzioni dei circuiti di Grover.

Teoria

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

Un esempio definito su $\Sigma^6$ è

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

Il compito è quello di trovare gli stati quantici corrispondenti agli argomenti $x$ di $f(x)$ che sono mappati a 1. In altre parole, trovare tutti i $\{x_1\}\in \Sigma^n$ tali che $f(x_1)=1$ (o se non c'è soluzione, segnalarlo). Ci riferiremo alle non soluzioni come $x_0$. Naturalmente, faremo tutto questo su un computer quantistico, usando gli stati quantistici, quindi è utile esprimere queste stringhe binarie come stati:

Utilizzando la notazione degli stati quantistici (Dirac), cerchiamo 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 denotate $\{|x_0\rangle\}.$

Possiamo pensare alla funzione $f$ come se fosse fornita da un oracolo: una scatola nera che possiamo interrogare per determinare il suo 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 interrogazioni 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 tale che non conosciamo la funzione dell'oracolo, ma conosciamo solo la sua azione su particolari stati grazie all'interrogazione.

Si tratta di un "problema di ricerca non strutturato", in quanto non c'è nulla di speciale in $f$ che ci aiuti nella ricerca. Le uscite non sono ordinate, né si sa che le soluzioni si raggruppano, e così via. Considerate l'uso di vecchi elenchi telefonici cartacei come analogia. Questa ricerca non strutturata sarebbe come una scansione alla ricerca di un determinato numero, e non come una ricerca in un elenco alfabetico di nomi.

Nel caso in cui si cerchi una singola soluzione, classicamente ciò richiede un numero di interrogazioni lineare in $N$. È chiaro che si può trovare una soluzione al primo tentativo, oppure che non si trova alcuna soluzione nelle prime $N-1$ ipotesi, per cui è necessario interrogare l'input $N^{th}$ per vedere se c'è qualche soluzione. Dal momento che le funzioni non hanno una struttura sfruttabile, in media sono necessarie $N/2$ ipotesi. L'algoritmo di Grover richiede un numero di interrogazioni o di calcoli di $f$ che varia a seconda dei casi $\sqrt{N}.$

Schizzo dei circuiti nell'algoritmo di Grover

Una spiegazione matematica completa dell'algoritmo di Grover si trova, ad esempio, in Fundamentals of quantum algorithms, un corso di John Watrous su IBM Quantum Learning. Una trattazione sintetica è riportata in appendice alla fine di questo modulo. Ma per ora ci limiteremo a esaminare 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 superposizione iniziale (applicando le porte di Hadamard a tutti i qubit)
• "Marcatura" dello stato (o degli stati) di destinazione con un capovolgimento di fase
• Una fase di "diffusione" in cui le porte di Hadamard e un capovolgimento di fase vengono applicati a tutti i qubit.
• Possibili ripetizioni delle fasi di marcatura e di diffusione per massimizzare la probabilità di misurare lo stato target
• Misurazione

Spesso, la porta di marcatura $Z_f$ e gli strati di diffusione costituiti da $H,$ $Z_{\text{OR}},$ e $H$ sono indicati collettivamente come "operatore Grover". In questo diagramma è mostrata una sola ripetizione dell'operatore Grover.

Le porte di Hadamard $H$ sono ben note e ampiamente utilizzate nell'informatica quantistica. La porta di Hadamard crea stati di sovrapposizione. In particolare, è definito da

Il suo funzionamento su qualsiasi altro stato è definito dalla linearità. In particolare, uno strato di porte di Hadamard ci permette di passare dallo stato iniziale con tutti i qubit in $|0\rangle$ (indicato con $|0\rangle^{\otimes n}$ ) a uno stato in cui ogni qubit ha una certa probabilità di essere misurato in $|0\rangle$ o $|1\rangle;$ Questo ci permette di sondare lo spazio di tutti gli stati possibili in modo diverso da quello dell'informatica classica.

Un'importante proprietà corollaria della porta di Hadamard è che agendo una seconda volta si possono annullare tali stati di sovrapposizione:

Questo aspetto sarà importante tra poco.

Verifica la tua comprensione

Partendo dalla definizione di porta di Hadamard, dimostrate che una seconda applicazione della porta di Hadamard annulla tali sovrapposizioni come affermato sopra.

• Risposta

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

Il gate $Z_\text{OR}$ è meno comune ed è definito in base a

Infine, il gate $Z_f$ è definito da

Si noti che l'effetto è che $Z_f$ inverte il segno su uno stato bersaglio per il quale $f(x) = 1$ e lascia inalterati gli altri stati.

A un livello molto alto e astratto si può pensare alle fasi del circuito nei seguenti modi:

• Primo strato di Hadamard: mette i qubit in una sovrapposizione di tutti gli stati possibili.
• $Z_f$ : contrassegnare lo stato o gli stati di destinazione aggiungendo un segno "-" davanti. Questo non modifica immediatamente le probabilità di misurazione, ma cambia il comportamento dello stato target nelle fasi successive.
• Un altro strato di Hadamard: Il segno "-" introdotto nel passaggio precedente cambierà il segno relativo tra alcuni termini. Poiché le porte di Hadamard trasformano una miscela di stati computazionali $(|0\rangle+|1\rangle)/\sqrt{2}$ in uno stato computazionale, $|0\rangle,$ e trasformano $(|0\rangle-|1\rangle)/\sqrt{2}$ in $|1\rangle$, questa differenza di segno relativo può ora iniziare a svolgere un ruolo nella misurazione degli stati.
• Si applica un ultimo strato di porte di Hadamard e si effettuano le misurazioni. Vedremo in dettaglio come funziona nella prossima sezione.

Esempio

Per capire meglio come funziona l'algoritmo di Grover, facciamo un piccolo esempio a due qubit. Questo può essere considerato opzionale per coloro che non si concentrano sulla meccanica quantistica e sulla notazione di Dirac. Ma per coloro che sperano di lavorare in modo sostanziale con i computer quantistici, questo è altamente raccomandato.

Ecco lo schema del circuito con gli stati quantici etichettati in varie posizioni. Si noti che con due soli qubit, ci sono solo quattro possibili stati che possono essere misurati in qualsiasi circostanza: $|00\rangle$, $|01\rangle$, $|10\rangle$, e $|11\rangle$.

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

Utilizzando la definizione di porte di Hadamard, abbiamo

Ora l'oracolo contrassegna lo stato di destinazione:

Si noti che in questo stato, tutti e quattro i possibili risultati hanno la stessa probabilità di essere misurati. Tutti hanno un peso di magnitudo $1/2,$, il che significa che ognuno di essi ha una probabilità $|1/2|^2=1/4$ di essere misurato. Quindi, mentre lo stato $|01\rangle$ è contrassegnato dalla fase "-", ciò non ha ancora comportato un aumento della probabilità di misurare quello stato. Continuiamo applicando il livello successivo di porte di Hadamard.

Combinando i termini simili, troviamo

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

Infine, applichiamo l'ultimo strato di porte di Hadamard:

Vale la pena di lavorare sulla combinazione di questi termini per convincersi che il risultato è effettivamente tale:

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

L'esempio dei due qubit è stato un caso particolarmente pulito; l'algoritmo di Grover non sempre riesce a produrre una probabilità del 100% di misurare lo stato target. Piuttosto, amplificherà la probabilità di misurare lo stato target. Inoltre, potrebbe essere necessario ripetere l'operatore Grover più di una volta.

Nella prossima sezione metteremo in pratica questo algoritmo utilizzando computer quantistici reali IBM®.

L'immagine geometrica

L'esempio a due qubit riportato sopra ha illustrato come funziona l'algebra in un caso semplice, ma esiste un modo molto più intuitivo per comprendere l'algoritmo di Grover: come una sequenza di riflessioni geometriche su un piano bidimensionale. Di seguito descriviamo questa immagine. Per ulteriori dettagli, puoi anche consultare il corso di John Watrous intitolato "Fondamenti degli algoritmi quantistici".

Preparazione dell'aereo. Possiamo scomporre lo stato di sovrapposizione iniziale $|\psi\rangle$ in due componenti. Lo stato corretto — quello che stiamo cercando — lo chiamiamo « $|A_1\rangle$ ». Tutti gli altri stati, considerati nel loro insieme, li chiamiamo « $|A_0\rangle$ ». Per definizione, « $|A_1\rangle$ » e « $|A_0\rangle$ » sono ortogonali tra loro, quindi possiamo rappresentarli come assi perpendicolari in uno spazio astratto bidimensionale. Poiché $|\psi\rangle$ è una combinazione lineare di queste due componenti, forma un angolo minimo $\theta$ rispetto all'asse $|A_0\rangle$ — vicino a $|A_0\rangle$, poiché all'inizio solo una minuscola frazione dello stato si trova nella componente corretta $|A_1\rangle$.

Riflessioni. Il fatto matematico fondamentale di cui abbiamo bisogno è che un operatore della forma

riflette qualsiasi stato lungo l'asse definito da $|v\rangle.$ Per capirne il motivo, si considerino due casi: uno stato lungo $|v\rangle$ rimane invariato, mentre uno stato perpendicolare a $|v\rangle$ subisce un'inversione di segno. Qualsiasi altro stato può essere scomposto in queste due componenti, e l'operatore agisce su ciascuna di esse di conseguenza — il che è esattamente una riflessione sull' $|v\rangle$ o.

Risulta che sia la fase dell'oracolo che quella di diffusione nell'algoritmo di Grover possano essere rappresentate come riflessioni in questo schema geometrico.

L'oracolo come riflesso. L'oracolo inverte il segno dello stato " $|A_1\rangle$ " e lascia tutto il resto invariato. È come un riflesso sull'asse dell' $|A_0\rangle$ e.

La diffusione come riflesso. È un po' più complicato capire come l'operatore di diffusione sia anche una riflessione. L'operatore di diffusione è

$Z_{\text{OR}}$ di per sé rappresenta una riflessione sullo stato tutto a zero, poiché inverte il segno di ogni stato che non sia un " $|0\rangle^{\otimes n}$ ". Ciò può essere scritto come $2|0\rangle\langle 0| - I$. Gli strati di Hadamard circostanti effettuano di fatto un cambio di base, trasformando l'asse di riflessione. Ricordiamo che l'operatore di Hadamard ( $H^{\otimes n}$ ) mappa l'operatore di Hadamard ( $|0\rangle^{\otimes n}$ ) sulla sovrapposizione uniforme ( $|u\rangle = \frac{1}{\sqrt{N}}\sum_{x}|x\rangle$ ). Poiché l'operatore di Hadamard è il proprio inverso, l'espressione completa diventa

che è una riflessione su $|u\rangle$. Poiché $|u\rangle$ è molto vicino a $|\psi\rangle$ (entrambi si trovano quasi in linea con $|A_0\rangle$ ), questa seconda riflessione invia lo stato a un angolo $2\theta$ rispetto al punto di partenza.

Rotazione di $2\theta$. L'effetto combinato di questi due riflessi è una rotazione di $2\theta$ in direzione di $|A_1\rangle$. Ogni iterazione successiva dell'operatore di Grover ruota lo stato di un altro $2\theta.$

Numero ottimale di iterazioni. Il nostro obiettivo è ruotare lo stato il più possibile verso l'orientamento " $|A_1\rangle$ ", il che significa ruotarlo di circa $\pi/2$ radianti (un quarto di giro). Se ogni iterazione contribuisce con un valore pari a $2\theta$, il numero ottimale di iterazioni $t$ soddisfa

Per una soluzione singola tra gli stati di un sistema a un' $N$ e, l'angolo iniziale è $\theta \approx \sin^{-1}(1/\sqrt{N}) \approx 1/\sqrt{N}$ (per $N$ molto grande). Sostituendo,

È da qui che deriva il famoso miglioramento di velocità dell'algoritmo " $\sqrt{N}$ ": bastano infatti solo $O(\sqrt{N})$ iterazioni per raggiungere l'obiettivo, anziché le $O(N)$ verifiche che richiederebbe una ricerca classica.

Più in generale, se tra gli $N$ i stati possibili ve ne sono $|A_1|$, il numero ottimale di iterazioni è

Si noti che, se si applicano troppe iterazioni, si supera l' $|A_1\rangle$ e e la probabilità di trovare lo stato desiderato ricomincerà a diminuire. È importante individuare il numero corretto di iterazioni, anche se su hardware quantistico soggetto a rumore il numero ottimale dal punto di vista sperimentale potrebbe differire da questa formula ideale.

Perché l'algoritmo di Grover è utile?

A questo punto vi starete forse chiedendo: abbiamo appena creato un oracolo che indica uno stato finale, ma per farlo dovevamo conoscere lo stato finale. Ma cosa stiamo cercando, in realtà?

È una domanda legittima, e ci sono diverse risposte valide.

• Il modello di interrogazione è uno strumento teorico. Il modello di calcolo basato sulle query non è mai stato concepito per essere direttamente applicabile. Il suo scopo è quello di fornirci un metodo chiaro per analizzare la complessità algoritmica, suddividendo un problema in due parti: l'oracolo e tutto il resto. Quanto è difficile la ricerca, visto che la verifica è gratuita? In che modo il numero di query varia in funzione delle dimensioni dei dati in ingresso? Si tratta di domande utili, anche se nessun sistema reale funziona esattamente in questo modo.

• Si può anche considerarla un 'attività a due: una persona conosce lo stato finale e costruisce l'oracolo; il compito dell'altra persona è trovare la risposta utilizzando l'oracolo come una scatola nera, senza sbirciare all'interno. Nell'attività 2 qui sotto, farete proprio questo con un compagno.

• L'amplificazione dell'ampiezza è una subroutine di ampia utilità. Anche se questa prima dimostrazione può sembrare un circolo vizioso, il meccanismo alla base — chiamato amplificazione di ampiezza — ricorre continuamente nell'informatica quantistica. Ciò che stiamo realmente sviluppando qui è una comprensione intuitiva di uno strumento che compare come subroutine in molti algoritmi quantistici più complessi.

• Ci sono problemi per i quali è possibile costruire un oracolo senza conoscere la risposta. L'idea fondamentale è che esiste un'intera classe di problemi per i quali è molto difficile trovare una soluzione, ma molto facile verificare che una data soluzione sia corretta. Il factoring ne è un esempio: dato il prodotto di due grandi numeri primi, è estremamente difficile individuare quali siano tali numeri primi, ma una volta individuati, è possibile moltiplicarli facilmente per verificare il risultato. (Abbiamo un algoritmo migliore di quello di Grover proprio per la fattorizzazione — vedi l'algoritmo di Shor — ma questo è ben lungi dall'essere l'unico problema di questa funzione.) Il Sudoku, la soddisfazione dei vincoli e persino il classico gioco "Campo minato" sono tutti problemi difficili da risolvere ma facili da verificare.

Perché è importante? Ciò significa che possiamo conoscere tutte le condizioni e i requisiti che una soluzione deve soddisfare e che possiamo codificare tali requisiti in un circuito quantistico che funge da oracolo, anche se non conosciamo la soluzione stessa. L'algoritmo di Grover lo troverà per noi.

Tenendo presenti questi concetti, esaminiamo alcuni esempi. Inizieremo con un esempio in cui lo stato della soluzione è chiaramente definito, in modo da poter seguire la logica dell'algoritmo. Passeremo quindi a un'attività a due parti e, infine, a un esempio in cui l'oracolo viene costruito sulla base dei vincoli del problema piuttosto che sulla conoscenza della risposta.

Importazioni generali e approccio

Si inizia importando alcuni pacchetti necessari.

# Built-in modules
import math

# Imports from Qiskit
from qiskit import QuantumCircuit, QuantumRegister, ClassicalRegister
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

In questa e in altre esercitazioni, utilizzeremo un quadro di riferimento per l'informatica quantistica noto come "schemi Qiskit", che suddivide i flussi di lavoro nelle seguenti fasi:

• Fase 1: mappare gli input classici in un problema quantistico
• Fase 2: Ottimizzazione del problema per l'esecuzione quantistica
• Fase 3: Esecuzione tramite le primitive " IBM Quantum "
• Fase 4: post-elaborazione e analisi classica

In genere seguiamo questi passaggi, anche se non sempre li indichiamo esplicitamente.

Attività 1: Individuare un unico stato target prestabilito

Fase 1: mappare gli input classici su un problema quantistico

È necessario che il gate di interrogazione di fase inserisca una fase complessiva (-1) sugli stati di soluzione, lasciando inalterati gli stati di non soluzione. Un altro modo per dirlo è che l'algoritmo di Grover richiede un oracolo che specifichi uno o più stati base computazionali marcati, dove "marcato" significa uno stato con una fase di -1. Per farlo si utilizza una porta Z controllata, o la sua generalizzazione multicontrollata su $N$ qubit. Per vedere come funziona, consideriamo un esempio specifico di una stringa di bit {110}. Vorremmo 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).

Pertanto, vogliamo un circuito $Z_f$ che realizzi

Possiamo usare il gate a controllo multiplo e target multiplo (MCMTGate) per applicare un gate Z controllato da tutti i qubit (capovolgendo la fase se tutti i qubit sono nello stato $|1\rangle$ ). Naturalmente, alcuni dei qubit nel nostro stato desiderato possono essere $|0\rangle$. Pertanto, per questi qubit dobbiamo prima applicare un gate X, poi eseguire il gate Z controllato dalla moltiplicazione, quindi applicare un altro gate X per annullare la nostra modifica. Il sito MCMTGate si presenta così:

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

Output:

Si noti che molti qubit possono essere coinvolti nel processo di controllo (in questo caso tre qubit), ma nessun singolo qubit è indicato come bersaglio. Questo perché l'intero stato riceve un segno "-" complessivo (phase flip); il gate agisce su tutti i qubit in modo equivalente. Questo è diverso da molti altri gate a qubit multipli, come il gate CX , che ha un singolo qubit di controllo e un singolo qubit di destinazione.

Nel codice che segue, definiamo un gate di interrogazione di fase (o oracolo) che fa ciò che abbiamo appena descritto sopra: contrassegna uno o più stati base in ingresso definiti attraverso la loro rappresentazione in bitstring. Il gate MCMT viene utilizzato per implementare la porta Z multicontrollata.

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 specifico stato "marcato" come obiettivo e applichiamo la funzione appena definita. Vediamo che tipo di circuito ha creato.

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

Output:

Se i qubit 1-3 sono nello stato $|1\rangle$ e il qubit 0 è inizialmente nello stato $|0\rangle$, il primo gate X capovolgerà il qubit 0 in $|1\rangle$ e tutti i qubit saranno in $|1\rangle.$ Ciò significa che il gate MCMT applicherà un cambio di segno complessivo o un capovolgimento di fase, come desiderato. In qualsiasi altro caso, o i qubit 1-3 si trovano nello stato $|0\rangle$, o il qubit 0 è ribaltato nello stato $|0\rangle$, e il flip di fase non verrà applicato. Vediamo che questo circuito segna effettivamente il nostro stato desiderato $|0111\rangle,$ o la stringa di bit {1110}.

L'operatore di Grover completo consiste nella porta di interrogazione di fase (oracolo), negli strati di Hadamard e nell'operatore $Z_\text{OR}$. Possiamo usare il built-in grover_operator per costruirlo a partire dall'oracolo che abbiamo definito in precedenza.

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

Output:

Come abbiamo visto nell'immagine geometrica qui sopra, potrebbe essere necessario applicare l'operatore di Grover più volte. Il numero ottimale di iterazioni $t$ per massimizzare l'ampiezza dello stato di destinazione in assenza di rumore è

dove $|A_1|$ è il numero di stati di soluzione e $N=2^n$ è il numero totale di stati. Sui moderni computer quantistici soggetti a rumore, il numero ottimale di iterazioni potrebbe essere diverso; tuttavia, in questo caso calcoliamo e utilizziamo tale numero ottimale teorico ricorrendo a un metodo di ottimizzazione ( $|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)

Output:

3

Costruiamo ora un circuito che includa le porte di Hadamard 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")

Output:

Abbiamo costruito il nostro circuito Grover!

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

Abbiamo definito il nostro circuito quantistico astratto, ma dobbiamo riscriverlo in termini di porte native del computer quantistico che vogliamo utilizzare. Dobbiamo anche specificare quali qubit del computer quantistico devono essere utilizzati. Per questi motivi e per altri ancora, ora dobbiamo trasporre il nostro circuito. Innanzitutto, specifichiamo il computer quantistico che vogliamo utilizzare.

Di seguito è riportato un codice per salvare le credenziali al primo utilizzo. Assicurarsi di eliminare queste informazioni dal blocco note dopo averlo salvato nel proprio ambiente, in modo che le credenziali non vengano accidentalmente condivise quando si condivide il blocco note. Per ulteriori informazioni, vedere Configurazione dell'account IBM Cloud e Inizializzazione del servizio in un ambiente non attendibile.

# 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

Output:

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 utilizziamo un gestore di passaggi preimpostati 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 di notare che la profondità del circuito quantistico transpilato è notevole.

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

Output:

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

Si tratta di numeri piuttosto grandi, anche per questo caso semplice. Poiché tutte le porte quantistiche (e in particolare quelle a due qubit) presentano errori e sono soggette a rumore, una serie di oltre 100 porte a due qubit non produrrebbe altro che rumore se i qubit non fossero estremamente performanti. Vediamo come si comportano.

Fase 3: Esecuzione tramite le primitive " IBM Quantum "

Vogliamo effettuare molte misurazioni e vedere quale stato sia il più probabile. Tale amplificazione dell'ampiezza è un problema di campionamento che si presta all'esecuzione con Sampler la primitiva IBM Quantum.

Si noti che il metodo run() di IBM Quantum SamplerV2 accetta un iterabile di blocchi unificati primitivi (PUB). Per Sampler, ogni PUB è un iterabile nel formato (circuito, valori_parametri). Tuttavia, come minimo, occorre 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 ottenere il massimo da questa esperienza, vi consigliamo di eseguire i vostri esperimenti sui veri computer quantistici disponibili su IBM Quantum. Tuttavia, se avete esaurito il tempo a disposizione per la QPU, potete decommentare le righe sottostanti per completare questa attività utilizzando 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()

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

Ora possiamo tracciare i risultati del nostro campionamento in un istogramma.

plot_distribution(dist)

Output:

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 alle altre opzioni. Nella prossima attività, utilizzeremo l'algoritmo in un modo più coerente con il flusso di lavoro a due parti di un algoritmo di interrogazione.

Verifica la tua comprensione

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 delle diverse soluzioni o (b) una singola soluzione in uno spazio di più stati possibili?

• Risposta

  Ricordiamo che, finché il numero di soluzioni è piccolo rispetto all'intero spazio delle soluzioni, possiamo espandere la funzione seno attorno a piccoli angoli 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 si evince che aumentando il numero di stati di soluzione diminuisce il numero di iterazioni. A condizione che la frazione $\frac{|\mathcal{A}_1|}{N}$ sia ancora piccola, possiamo descrivere come $t$ diminuisca: $t~\frac{1}{\sqrt{|\mathcal{A}_1|}}.$

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

Supponiamo di poter aumentare la dimensione della stringa di bit bersaglio fino a renderla arbitrariamente lunga e di ottenere comunque il risultato che lo stato bersaglio ha un'ampiezza di probabilità superiore di almeno un ordine di grandezza rispetto a qualsiasi altro stato. Questo significa che possiamo usare l'algoritmo di Grover per trovare in modo affidabile lo stato di destinazione?

• Risposta

  Num. Supponiamo di aver ripetuto la prima attività con 20 qubit e di aver eseguito il circuito quantistico un certo 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 una sola volta. Se la probabilità di misurare lo stato target fosse 10 volte quella delle non-soluzioni (e la probabilità di ogni non-soluzione fosse corrispondentemente leggermente diminuita), ci sarebbe solo il 10% circa 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 molti stati non risolutivi ottenuti casualmente. La buona notizia è che possiamo ottenere risultati ancora più fedeli utilizzando la soppressione e la mitigazione degli errori.

Attività 2: Un accurato flusso di lavoro dell'algoritmo di query

Inizieremo questa attività esattamente come la prima, solo che ora farete coppia con un altro appassionato di Qiskit. Voi sceglierete una bitstring segreta e il vostro partner una bitstring (generalmente) diversa. Ciascuno di voi genererà un circuito quantistico che funziona come un oracolo e lo scambierete. Si utilizzerà quindi l'algoritmo di Grover con quell'oracolo per determinare la bitstring segreta del partner.

Fase 1: mappare gli input classici su un problema quantistico

Utilizzando la funzione grover_oracle definita sopra, costruire un circuito oracolo per uno o più stati marcati. Assicuratevi di dire al vostro partner quanti stati avete segnato, in modo che possa applicare l'operatore Grover il numero ottimale di volte. Non allungate troppo la vostra stringa di bit. 3-5 bit dovrebbero funzionare senza difficoltà. Le stringhe di bit più lunghe comporterebbero 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 avete creato un circuito quantistico che inverte la fase del vostro stato target. È possibile salvare questo circuito come my_circuit.qpy utilizzando 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 inviate questo file al vostro partner (tramite e-mail, servizio di messaggistica, una repo condivisa e così via). Chiedete al vostro partner di inviarvi anche il suo circuito. Assicuratevi di salvare il file in un posto dove possiate trovarlo facilmente. Una volta ottenuto il circuito del vostro interlocutore, potreste visualizzarlo, ma questo rompe il modello di query. In altre parole, stiamo modellando una situazione in cui è possibile interrogare l'oracolo (utilizzare il circuito dell'oracolo), ma non esaminarlo per determinare quale sia lo stato a cui si rivolge.

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

Chiedete al vostro compagno quanti stati target ha codificato e inseritelo qui sotto.

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

Questo dato viene utilizzato nella prossima espressione 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()

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

Si procede esattamente come in precedenza.

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

Fase 3: Esecuzione tramite le primitive " IBM Quantum "

Anche questo procedimento è identico a quello della 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()

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

Visualizzare ora un istogramma dei risultati del campionamento. Uno o più stati dovrebbero avere una probabilità di misurazione molto più alta degli altri. Riferiteli al vostro partner e verificate se avete determinato correttamente gli stati target. Per impostazione predefinita, l'istogramma visualizzato è quello dello stesso circuito della prima attività. Dovreste ottenere risultati diversi dal circuito del vostro partner.

plot_distribution(dist)

Output:

Verifica la tua comprensione

Dovreste aver ottenuto correttamente lo stato o gli stati di destinazione del vostro partner. In caso contrario, collaborate con il vostro partner per individuare cosa è andato storto. Cliccate qui sotto per alcune idee.

• Suggerimenti
  • Visualizzate/disegnate il circuito del vostro partner e assicuratevi che sia stato caricato correttamente.
  • Confrontate i circuiti utilizzati e confrontate il risultato atteso con quello ottenuto.
  • Controllare la profondità dei circuiti utilizzati per assicurarsi che la stringa di bit non sia troppo lunga o che il numero di iterazioni di Grover sia proibitivo.

Se non l'avete ancora fatto, disegnate il circuito dell'oracolo che vi ha inviato il vostro partner. Vedete se riuscite a descrivere l'effetto di ciascun cancello e ad argomentare quale doveva essere lo stato di destinazione. Questo sarà molto più facile nel caso di un singolo stato marcato che nel caso di più stati.

• Suggerimenti
  • Ricordiamo che il compito dell'oracolo è quello di invertire il segno sullo stato di destinazione.
  • Ricordiamo che il MCMTGate inverte il segno di uno stato se e solo se tutti i qubit coinvolti nel controllo sono nello stato $|1\rangle$.
  • Se il vostro stato di destinazione avrà già un $|1\rangle$ su un particolare qubit, non dovrete fare nulla a quel qubit. Se il vostro obiettivo ha un $|0\rangle$ su un particolare qubit e volete che l'MCMTGate inverta il segno, dovete applicare un gate X a quel qubit nel vostro oracolo (e poi annullare il gate X dopo l'MCMTGate).

Ripetere l'esperimento con un'iterazione in meno dell'operatore Grover. Ottenete comunque la risposta corretta? Perché o perché no?

• Indicazioni

  Probabilmente sì, anche se potrebbe dipendere dal numero di soluzioni codificate. Questo evidenzia una sottigliezza: il numero "ottimale" di iterazioni di Grover è quello che rende la probabilità di misurare lo stato marcato la più alta possibile. Ma un numero inferiore di iterazioni potrebbe comunque rendere lo stato contrassegnato sostanzialmente più probabile di altri stati. Pertanto, si potrebbe riuscire a fare a meno di un numero di iterazioni inferiore a quello ottimale. In questo modo si riduce la profondità del circuito e quindi il tasso di errore.

Perché qualcuno potrebbe voler utilizzare un numero di iterazioni di Grover inferiore al "numero ottimale" qui individuato?

• Risposta

  Il numero "ottimale" di iterazioni di Grover è quello che rende la probabilità di misurare lo stato marcato la più alta possibile in assenza di rumore. Ma un numero inferiore di iterazioni potrebbe comunque rendere lo stato contrassegnato sostanzialmente più probabile di altri stati. Pertanto, è possibile che si riesca a ottenere un numero di iterazioni inferiore a quello ottimale. In questo modo si riduce la profondità del circuito e quindi il tasso di errore.

Attività 3: Risolvere una griglia di Campo minato con l'algoritmo di Grover

Nella sezione precedente abbiamo osservato che l'algoritmo di Grover diventa davvero utile quando è possibile costruire un oracolo a partire dai vincoli di un problema, piuttosto che dalla conoscenza della risposta. Il gioco "Campo minato" ne è un esempio perfetto: le caselle numerate ci indicano quante mine si trovano nelle caselle adiacenti, e questi vincoli determinano interamente la posizione delle mine — ma per trovare la configurazione è necessario effettuare una ricerca.

È stato dimostrato che il gioco "Campo minato" è NP-completo: è difficile da risolvere ma facile da verificare. Questo lo rende un candidato naturale per l'algoritmo di Grover. Ovviamente, non siamo ancora in grado di risolvere una griglia completa di 9× $\times$ 9 su un computer quantistico soggetto a rumore: i circuiti sarebbero troppo complessi. Useremo invece una griglia molto piccola come esempio illustrativo di come ci si potrebbe approcciare a una scheda più grande su una futura macchina a tolleranza di guasti.

Alcune precisazioni importanti. L'algoritmo di Grover offre solo un miglioramento quadratico rispetto alla ricerca classica non strutturata. È quasi certo che il gioco "Campo minato" presenti una struttura sfruttabile che un algoritmo classico ben congegnato potrebbe utilizzare. E in un ambito di ricerca in crescita esponenziale, anche il miglioramento offerto dall' $\sqrt{N}$ e ha i suoi limiti. Ma mettiamo da parte queste preoccupazioni e utilizziamo questo problema di esempio per illustrare come i vincoli del problema vengono codificati in un oracolo quantistico.

La rete

Ecco la griglia del nostro Campo Minato per bambini:

Ogni casella vuota può essere rappresentata da una variabile binaria che indica se contiene una mina. Li indichiamo con le sigle $x_0$, $x_1$ e $x_2$, dove $x_i = 1$ indica che in quella casella c'è una mina e $x_i = 0$ indica che non ce n'è:

Potremmo risolverlo a mente in circa mezzo secondo, ma stiamo usando questo semplice esempio per illustrare come si potrebbe affrontare un problema molto più complesso con un computer quantistico.

Codificare i vincoli

Ogni cella numerata impone una condizione alle celle vuote adiacenti. Dobbiamo esprimere queste condizioni sotto forma di espressioni booleane che possano essere codificate in un circuito quantistico.

La casella con il numero "1" adiacente a $x_0$ e $x_1$ indica che esattamente uno dei due siti contiene una mina. Si tratta proprio dell'operazione OR esclusivo (XOR), $\oplus$, che restituisce vero quando esattamente uno dei suoi argomenti è vero:

Allo stesso modo, l'altra cella contenente "1" (adiacente a $x_1$ e $x_2$ ) ci dà:

La casella "2" indica che due delle tre caselle vuote devono contenere delle mine. Poiché l'operazione XOR è un'operazione di parità, l' $x_0 \oplus x_1 \oplus x_2$ e restituisce vero quando un numero dispari di variabili è vero. Vogliamo che sia vero un numero pari (in particolare due), quindi neghiamo con l' $\lnot$ e:

Di per sé, questa espressione sarebbe soddisfatta sia da zero che da due qubit nello stato " $|1\rangle$ ", poiché si tratta di un'affermazione relativa alla parità. Ma se si considerano le altre due condizioni, che richiedono ciascuna almeno una mina, l'unica soluzione valida prevede esattamente due mine.

Tutte e tre le condizioni devono essere soddisfatte contemporaneamente, quindi le uniamo con i simboli "e" $\land$ :

Fase 1: mappare gli input classici su un problema quantistico

Ora dobbiamo codificare questa espressione booleana in un circuito quantistico che funga da oracolo. La versione quantistica dell'operazione XOR può essere realizzata utilizzando porte CX (CNOT): applicando due porte CX dai qubit di dati a un qubit dello spazio di lavoro (ancilla) si calcola di fatto la loro operazione XOR e si memorizza il risultato nell'ancilla.

Introduciamo tre qubit di spazio di lavoro: uno per ogni clausola. Memorizziamo il risultato di ciascuna espressione booleana nel corrispondente qubit dello spazio di lavoro, quindi utilizziamo un gate Z a controllo multiplo per invertire la fase dello stato a tre qubit in modo che tutti e tre i qubit dello spazio di lavoro siano in uno stato " $|1\rangle$ " (il che significa che tutte le clausole sono soddisfatte contemporaneamente).

Nella prima cella di codice qui sotto, realizziamo la parte "di calcolo" dell'oracolo, ovvero quella che valuta ogni clausola e scrive il risultato nei qubit dell'area di lavoro.

x = QuantumRegister(3, "x")
a = QuantumRegister(3, "a")
qc = QuantumCircuit(x, a)

# Clause 1: x0 XOR x1 -> stored in a[0]
qc.cx(x[0], a[0])
qc.cx(x[1], a[0])

# Clause 2: x1 XOR x2 -> stored in a[1]
qc.cx(x[1], a[1])
qc.cx(x[2], a[1])

# Clause 3: NOT(x0 XOR x1 XOR x2) -> stored in a[2]
qc.cx(x[0], a[2])
qc.cx(x[1], a[2])
qc.cx(x[2], a[2])
qc.x(a[2])  # The NOT

qc.draw("mpl", style="iqp")

A questo punto, il risultato di ciascuna clausola viene memorizzato nel qubit dell'area di lavoro corrispondente. Ora ci serve lo stato di dati a tre qubit che faccia sì che tutti e tre i qubit dello spazio di lavoro si trovino in una posizi $|1\rangle$ e da assumere un segno negativo. A tal fine utilizziamo una porta Z a controlli multipli (implementata come porta MCX inserita tra due porte di Hadamard sul lato di destinazione).

Dopo aver applicato l'inversione di fase, dobbiamo eseguire l'«uncompute» — ovvero annullare tutti i passaggi di valutazione delle clausole in ordine inverso — per riportare i qubit dello spazio di lavoro allo stato « $|0\rangle.$ ». Ciò è fondamentale affinché i qubit dello spazio di lavoro siano «puliti» per le successive iterazioni dell'operatore di Grover.

# Multi-controlled Z: flip phase if all workspace qubits are |1>
qc.h(a[2])
qc.mcx([a[0], a[1]], a[2])
qc.h(a[2])

# Uncompute clause 3: NOT(x0 XOR x1 XOR x2)
qc.x(a[2])
qc.cx(x[2], a[2])
qc.cx(x[1], a[2])
qc.cx(x[0], a[2])

# Uncompute clause 2: x1 XOR x2
qc.cx(x[2], a[1])
qc.cx(x[1], a[1])

# Uncompute clause 1: x0 XOR x1
qc.cx(x[1], a[0])
qc.cx(x[0], a[0])

qc.draw("mpl", style="iqp")

Questo circuito è il nostro oracolo: inverte la fase dello stato del qubit di dati che soddisfa tutti e tre i vincoli del "Campo minato" e riporta i qubit dell'area di lavoro in uno stato di " $|0\rangle.$ "

Ora costruiamo l'operatore di Grover completo a partire da questo oracolo. xDa notare l'argomento reflection_qubits : passiamo solo i qubit di dati, poiché i qubit dello spazio di lavoro non fanno parte dello spazio di ricerca. Il loro compito è terminato una volta che l'oracolo è stato applicato.

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

Con tre qubit di dati e uno stato di soluzione, il numero ottimale di iterazioni di Grover è pari a $t \approx \frac{\pi}{4}\sqrt{8} - \frac{1}{2} \approx 1.7$, quindi utilizziamo due iterazioni. Applichiamo le porte di Hadamard ai qubit di dati per creare la sovrapposizione iniziale, componiamo due volte l'operatore di Grover e misuriamo solo i qubit di dati.

x = QuantumRegister(3, "x")
a = QuantumRegister(4, "a")
meas = ClassicalRegister(3, "meas")

qc = QuantumCircuit(x, a, meas)
# Create superposition over the data qubits only
qc.h(x)
# Apply 2 iterations of the Grover operator
qc.compose(grover_op.power(2), inplace=True)
# Measure only the data qubits
qc.measure(x, meas)
qc.decompose().draw(output="mpl", style="iqp")

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

Come in precedenza, compiliamo il circuito per il backend di destinazione.

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)

Ora possiamo verificare la profondità del circuito transpilato. Poiché l'oracolo Minesweeper utilizza qubit di workspace e più porte CX, il circuito transpilato risulterà più complesso rispetto a quelli delle attività precedenti.

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

Fase 3: Esecuzione tramite le primitive " IBM Quantum "

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

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

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

plot_distribution(dist)

Lo 101 stato dovrebbe comparire con una probabilità di gran lunga superiore rispetto a qualsiasi altro, il che indica che le mine si trovano su $x_0$ e $x_2$. Abbiamo usato un computer quantistico per risolvere una minuscola partita a Campo minato!

Ovviamente, i migliori algoritmi classici per il gioco del campo minato sono più efficaci di una ricerca per forza bruta su tutte le possibili configurazioni delle mine: sfruttano infatti la struttura della griglia. L'algoritmo di Grover offrirebbe un vantaggio solo su tabelle estremamente complesse, progettate per essere il più ambigue possibile, e anche in quel caso, l'accelerazione quadratica implica che non possa tenere il passo con la crescita esponenziale all'infinito. Ma il vero punto fondamentale è la tecnica: codificare i vincoli di un problema in un oracolo quantistico è un modello potente che si estende alla soddisfazione dei vincoli, all'ottimizzazione combinatoria e a molti altri ambiti.

Domande e concetti chiave:

Concetti fondamentali:

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

• Mentre i classici algoritmi di ricerca non strutturata richiedono un numero di interrogazioni che scala linearmente nella dimensione dello spazio, l'algoritmo di $N,$ Grover richiede un numero di interrogazioni che scala come $\sqrt{N}.$
• L'algoritmo di Grover prevede la ripetizione di una serie di operazioni (comunemente chiamate "operatore di Grover") per un numero di volte $t,$ scelto per rendere ottimale la probabilità di misurare gli stati target.
• L'algoritmo di Grover può essere eseguito con meno di $t$ iterazioni e continuare ad amplificare gli stati target.
• L'algoritmo di Grover si adatta al modello di query della computazione e ha più senso quando una persona controlla la ricerca e un'altra controlla/costruisce l'oracolo. Può anche essere utile come subroutine in altri calcoli quantistici.
• È possibile costruire un oracolo partendo dai vincoli del problema piuttosto che dalla conoscenza della soluzione, come dimostrato dall'esempio del Campo minato.

Domande vero/falso:

1. T/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. T/F L'algoritmo di Grover funziona aumentando iterativamente la probabilità che venga misurato uno stato di soluzione.

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

Domande del moderatore:

1. Selezionate l'opzione migliore per completare la frase. La strategia migliore per utilizzare con successo l'algoritmo di Grover sui moderni computer quantistici è quella di iterare l'operatore di Grover...

• a. Solo una volta.
• b. Sempre $t$ volte, per massimizzare l'ampiezza di probabilità dello stato (o degli stati) di soluzione.
• c. Fino a $t$ volte, anche se un numero inferiore può essere sufficiente per far risaltare gli stati di soluzione.
• d. Non meno di 10 volte.

2. Viene mostrato un circuito di interrogazione di fase che funziona come un oracolo per contrassegnare un determinato stato con un salto di fase. Quali dei seguenti stati sono contrassegnati da questo circuito?

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

3. Supponiamo di voler cercare tre stati marcati da 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 altri problemi potresti formulare come ricerca di Grover? Pensa a quei problemi per i quali è difficile trovare una soluzione, ma è facile verificarne la correttezza.

2. Si possono riscontrare problemi di scalabilità dell'algoritmo di Grover sui moderni computer quantistici?