QAOA su scala utility

Guarda il video sul QAOA su scala utility di Olivia Lanes, oppure apri il video in una finestra separata su YouTube.

Panoramica della lezione:

Finora in questo corso, speriamo di averti fornito una solida base del framework e degli strumenti necessari per risolvere problemi su scala utility su un computer quantistico. Ora vedremo finalmente questi strumenti in azione.

In questa lezione, ci sporcheremo le mani con un esempio su scala utility del problema Max-Cut, che è un famoso problema di teoria dei grafi che riguarda come partizionare al meglio un grafo in due parti. Inizieremo con un semplice grafo a cinque nodi per costruire la nostra intuizione su come un computer quantistico possa aiutarci a risolvere il problema, per poi applicarlo a una versione su scala utility del problema.

Questa lezione servirà come panoramica generale dell'approccio che adottiamo per risolvere questo problema. Non si tratterà di una guida al codice passo dopo passo. A corredo di questa lezione, però, è disponibile un tutorial con codice effettivo che puoi eseguire per risolvere il problema Max-Cut su un computer quantistico.

Il problema

Come promemoria, non tutti i problemi computazionali sono adatti al calcolo quantistico. I "problemi facili" non trarranno alcun vantaggio da questa tecnologia, perché i computer classici li risolvono già perfettamente.

I tre casi d'uso su cui siamo più ottimisti da esplorare sono:

1. simulare la natura
2. elaborare dati con struttura complessa
3. ottimizzazione

Oggi ci concentreremo sul terzo caso d'uso: l'ottimizzazione. In un problema di ottimizzazione, stiamo generalmente cercando il valore più grande o più piccolo possibile per una data funzione. La difficoltà di trovare questi estremi con metodi classici può crescere esponenzialmente all'aumentare della dimensione del problema.

Il problema di ottimizzazione che ci interessa oggi si chiama Max-Cut, che risolveremo usando un algoritmo chiamato Quantum Approximate Optimization Algorithm (QAOA).

Cos'è il Max-Cut?

Partiamo da un grafo, che consiste in una collezione di vertici (o nodi), alcuni dei quali sono collegati da archi. Nel problema, ci viene chiesto di dividere i nodi del grafo in due sottoinsiemi "tagliando" gli archi che li collegano. Vogliamo trovare la partizione che massimizza il numero di archi tagliati in questo modo — da cui il nome "Max-Cut".

Ad esempio, la figura sopra mostra un grafo a cinque nodi con una soluzione Max-Cut a destra. Taglia cinque archi, che è il massimo ottenibile con questo grafo.

Poiché un grafo a cinque nodi è così piccolo, non è troppo difficile calcolare il Max-Cut a mente o provando qualche taglio su un foglio di carta. Ma come puoi immaginare, il problema diventa sempre più difficile all'aumentare del numero di vertici — in parte perché il numero di possibili tagli da considerare cresce esponenzialmente con il numero di nodi. E a un certo punto, questo diventa difficile persino per i supercomputer con qualsiasi algoritmo classico noto.

Vorremmo un modo per risolvere il problema Max-Cut per questi grafi più grandi e complicati, perché il problema ha molte applicazioni pratiche, tra cui il rilevamento di frodi in finanza, il clustering di grafi, la progettazione di reti e l'analisi dei social media. Il Max-Cut si incontra spesso come sottoproblema all'interno di un particolare approccio a un problema più ampio. Quindi, è molto più comune di quanto potremmo pensare ingenuamente.

La soluzione

Ora illustreremo l'approccio che usiamo per risolvere il problema Max-Cut su un computer quantistico. Lo faremo con un semplice grafo a cinque nodi. Puoi seguire usando il tutorial con il notebook Python. Dopo quell'esempio semplice, il tutorial ti guiderà attraverso un esempio su scala utility del problema.

Il primo passo è creare il nostro grafo definendo il numero di nodi e gli archi che collegano due nodi. Puoi farlo importando un pacchetto chiamato rustworkx, come dimostrato nel tutorial. Il risultato sarà un grafo simile a questo:

Useremo il framework Qiskit patterns per trovare le soluzioni Max-Cut per questo grafo sul nostro computer quantistico.

Mappatura

Dobbiamo mappare il problema sul nostro computer quantistico. Per farlo, notiamo prima che massimizzare il numero di tagli in un grafo può essere scritto matematicamente come:

$$\max\limits_{x\in\{0,1\}^n} \sum\limits_{(i,j)} {x_i + x_j - 2x_ix_j}$$

Dove $i$ e $j$ sono nodi nel grafo, e $x_i$ e $x_j$ valgono 0 o 1, a seconda di quale lato della partizione si trova ciascun nodo (un gruppo è etichettato "0" e uno è etichettato "1"). Quando $x_i$ e $x_j$ si trovano sullo stesso lato della partizione, l'espressione nella somma è uguale a zero. Quando si trovano su lati opposti, quindi c'è un taglio tra loro, l'espressione è uguale a uno. Quindi, massimizzare il numero di tagli massimizzerà la somma.

Possiamo anche invertire il ragionamento e cercare il minimo moltiplicando ciascuno dei valori per meno uno.

$$\min\limits_{x\in\{0,1\}^n} \sum\limits_{(i,j)} {2x_ix_j - x_i - x_j}$$

Ora siamo pronti a mappare. Può sembrare un po' scoraggiante pensare a come passare da un grafo come quello che abbiamo appena disegnato a un circuito quantistico. Ma lo faremo un passo alla volta.

Ricorda, utilizzeremo QAOA per risolvere il Max-Cut. Nella metodologia QAOA, vogliamo in definitiva avere un operatore (o in altre parole un Hamiltoniano) che verrà usato per rappresentare la funzione di costo del nostro algoritmo ibrido, nonché un circuito parametrizzato (l'ansatz) che usiamo per rappresentare le possibili soluzioni al problema.

QUBO

Possiamo campionare da queste soluzioni candidate e poi valutarle usando la funzione di costo. Per farlo, sfruttiamo una serie di riformulazioni matematiche, tra cui la notazione Quadratic Unconstrained Binary Optimization — o QUBO in breve — che è un modo utile per codificare problemi di ottimizzazione combinatoria. In QUBO, vogliamo trovare:

$$\min\limits_{x\in\{0,1\}^n} x^TQx$$

dove $Q$ è una matrice $n\times n$ di numeri reali, $n$ corrisponde al numero di nodi nel nostro grafo, qui cinque.

Per applicare QAOA, dobbiamo formulare il nostro problema come Hamiltoniano — che è una funzione o matrice che rappresenta l'energia totale di un sistema. In particolare, vogliamo creare un Hamiltoniano della funzione di costo che abbia la proprietà che lo stato fondamentale corrisponda al valore minimo della funzione. Quindi, per risolvere il nostro problema di ottimizzazione, cercheremo di preparare lo stato fondamentale di $H$ su un computer quantistico. Poi, il campionamento da questo stato produrrà la soluzione a $\min 𝑓(𝑥)$ con alta probabilità.

Mappatura all'Hamiltoniano della funzione di costo

Si scopre che siamo fortunati, perché il problema QUBO è strettamente correlato, e in realtà computazionalmente equivalente, a uno degli Hamiltoniani più famosi e onnipresenti in fisica: l'Hamiltoniano di Ising.

Per scrivere il problema QUBO come Hamiltoniano di Ising, tutto ciò che dobbiamo fare è effettuare un semplice cambio di variabili:

$$x_i = \frac{1-z_i}{2}.$$

Non percorreremo tutti i passaggi qui, ma sono spiegati nel notebook allegato. Alla fine, la minimizzazione dell'espressione QUBO equivale alla minimizzazione di questa espressione:

$$\min_{x\in\{0,1\}^n} x^TQx\Longleftrightarrow \min_{z\in\{-1,1\}^n}z^TQz + b^Tz$$

Riscrivendo ancora leggermente otteniamo il nostro Hamiltoniano della funzione di costo, dove il minimo dell'espressione rappresenta lo stato fondamentale, Z è l'operatore di Pauli Z, e $b$ è un coefficiente scalare reale:

$$H_C=\sum_{ij}Q_{ij}Z_iZ_j + \sum_i b_i Z_i$$

Ora che abbiamo il nostro Hamiltoniano, dobbiamo riscriverlo in termini di operatori ZZ di Pauli a due locali, che possiamo facilmente convertire in gate a due qubit nel nostro circuito quantistico. Finiremo con sei oggetti — o stringhe di Pauli — dove ciascuno corrisponde a ciascuno dei sei archi nel grafo. Ciascuno dei cinque elementi in una stringa rappresenta un'operazione su un nodo — l'identità se il nodo non è connesso a quell'arco particolare, e l'operatore Pauli Z se lo è. In Qiskit, le stringhe di bit che rappresentano i qubit sono indicizzate al contrario. Ad esempio, un arco tra i nodi 0 e 1 è codificato come IIIZZ, e un arco tra 2 e 4 è codificato come ZIZII.

Costruire il circuito quantistico

Con il nostro Hamiltoniano scritto in termini di operatori di Pauli, siamo pronti a costruire il nostro circuito quantistico, che ci permette di campionare buone soluzioni usando un computer quantistico:

L'algoritmo QAOA si ispira al Teorema Adiabatico, che afferma che se iniziamo nello stato fondamentale di un Hamiltoniano dipendente dal tempo, se l'Hamiltoniano evolve abbastanza lentamente e dato abbastanza tempo, lo stato finale sarà lo stato fondamentale dell'Hamiltoniano finale. Il QAOA può essere pensato come la versione discreta e trotterizzata di questo Quantum Adiabatic Algorithm, dove ogni passo di Trotter rappresenta un livello dell'algoritmo QAOA. Quindi, invece di evolvere da uno stato all'altro, in ogni livello passeremo alternativamente tra il nostro Hamiltoniano della funzione di costo e un cosiddetto Hamiltoniano "mixer", di cui parleremo più avanti in questa lezione.

Il vantaggio del QAOA è che è più veloce dell'algoritmo quantistico adiabatico, ma restituisce soluzioni approssimate piuttosto che ottimali. Nel limite in cui il numero di livelli tende all'infinito, il QAOA converge al caso QAA, ma ovviamente questo è molto costoso computazionalmente.

Per creare il nostro circuito quantistico, applicheremo operatori alternati, parametrizzati da $\gamma$ e $\beta$, che rappresenteranno la discretizzazione dell'evoluzione temporale.

Quindi, le tre parti principali del circuito QAOA sono:

1. lo stato di prova iniziale, in grigio, che è lo stato fondamentale del mixer, creato applicando un gate di Hadamard a ogni qubit
2. l'evoluzione della funzione di costo, di cui abbiamo discusso in precedenza, in viola scuro
3. l'evoluzione sotto l'Hamiltoniano mixer, che non abbiamo ancora trattato, in viola chiaro.

Il nostro Hamiltoniano iniziale è chiamato Mixer perché il suo stato fondamentale è la sovrapposizione di tutte le possibili stringhe di bit di interesse: imponendo così una miscela di tutte le soluzioni possibili all'inizio.

L'Hamiltoniano mixer è la semplice somma di operazioni Pauli-X su ogni nodo del grafo. Qiskit ti permette di usare un operatore mixer personalizzato diverso se lo desideri, ma noi utilizzeremo quello standard. Quindi, anche in questo caso, puoi vedere che con Qiskit, molto del lavoro viene eliminato, rendendo banale trovare l'Hamiltoniano mixer e lo stato iniziale. L'unico lavoro che abbiamo dovuto fare è stato trovare la funzione di costo.

Ogni iterazione di questi operatori è chiamata livello. Questi livelli possono essere visti come discretizzazione dell'evoluzione temporale del sistema, come descritto in precedenza. Il pattern alternato deriva dalla decomposizione di Trotter e approssima le funzioni esponenziali di matrici non commutanti. In generale, più livelli o passi includiamo, più ci avviciniamo all'evoluzione temporale continua, come nel QAA, quindi in teoria il risultato sarà più accurato. Ma per questo esempio, inizieremo campionando con un solo livello. Ricorda, sia l'Hamiltoniano della funzione di costo che il mixer sono parametrizzati; dobbiamo ancora trovare i valori ottimali per $\gamma$ e $\beta.$

Ottimizzazione

Sebbene il circuito che abbiamo appena creato sembri piuttosto semplice e sia utile per costruire una comprensione intuitiva, ricorda che il chip quantistico non capisce cos'è il gate QAOA. Dobbiamo convertirlo in una serie di gate "nativi" a singolo e doppio qubit che possono essere eseguiti direttamente sull'hardware. I gate nativi sono quelli che possono essere eseguiti direttamente sui qubit. Si dice che tali circuit siano scritti nell'Instruction Set Architecture (ISA) del Backend.

La libreria Qiskit offre una serie di pass di transpilazione che soddisfano un'ampia gamma di trasformazioni di circuit. Vogliamo assicurarci che il circuito sia ottimizzato per il nostro scopo.

Ricorda dalla nostra lezione precedente che il processo di transpilazione prevede diversi passaggi:

• Mappatura iniziale dei qubit nel circuito (cioè le variabili decisionali) ai qubit fisici sul dispositivo.
• Srotolamento delle istruzioni nel circuito quantistico alle istruzioni native dell'hardware che il Backend comprende.
• Routing di eventuali qubit nel circuito che interagiscono verso qubit fisici adiacenti tra loro.

E come sempre, maggiori dettagli si possono trovare nella documentazione.

Prima di transpilare, però, dobbiamo scegliere su quale Backend eseguire il nostro circuito, poiché il Transpiler ottimizza in modo diverso per processori diversi. Questa è un'ulteriore ragione per cui è importante utilizzare un Transpiler automatizzato — non vorresti passare attraverso il processo dispendioso in termini di tempo di ottimizzare il tuo circuito a mano, solo per renderti conto che vuoi eseguirlo su un processore diverso con proprietà diverse.

Passa il tuo Backend preferito attraverso la funzione del Transpiler e specifica il livello di ottimizzazione. Nel tutorial, selezionerai il livello 3, che è il più alto e più approfondito.

E con questo, abbiamo un circuito transpilato pronto per essere eseguito sull'hardware!

Esecuzione

Finora abbiamo transpilato il circuito lasciando i parametri gamma e beta invariati — ma non possiamo effettivamente eseguire il circuito senza specificare questi parametri. Nel flusso di lavoro QAOA, i parametri QAOA ottimali vengono trovati in un ciclo di ottimizzazione iterativo, dove eseguiamo una serie di valutazioni del circuito e poi usiamo un ottimizzatore classico per trovare i parametri ottimali 𝛽 e 𝛾. Tuttavia, dobbiamo iniziare da qualche parte, quindi facciamo un'ipotesi iniziale di $\gamma=\pi/2$ e $\beta=\pi.$

Modalità di esecuzione

Ora siamo quasi pronti a eseguire il circuito — promesso! Ma prima è importante notare che puoi inviare il tuo job in vari modi diversi, chiamati modalità di esecuzione.

• Modalità Job: Una singola richiesta primitiva dell'estimatore o del sampler viene effettuata senza un context manager. I circuit e gli input sono confezionati come primitive unified blocs (PUB) e inviati come task di esecuzione sul computer quantistico.

• Modalità Batch: Un gestore multi-job per eseguire in modo efficiente un esperimento composto da un insieme di job indipendenti. Usa la modalità batch per inviare più job primitivi simultaneamente.

• Modalità Session: Una finestra dedicata per eseguire un carico di lavoro multi-job. Questo permette agli utenti di sperimentare con algoritmi variazionali in modo più prevedibile, e persino di eseguire più esperimenti simultaneamente, sfruttando il parallelismo nello stack. Usa le session per carichi di lavoro iterativi o esperimenti che richiedono accesso dedicato. Consulta Run jobs in a session per esempi.

Per un esperimento QAOA, una session sarebbe una buona scelta se ne hai accesso, poiché dobbiamo campionare il nostro circuito molte volte con valori di parametri diversi per trovare l'ottimo.

Torniamo al problema di ottimizzazione. Dobbiamo trovare valori migliori di gamma e beta rispetto alle nostre prime ipotesi approssimative. Lo faremo inserendo la nostra funzione di costo e queste ipotesi iniziali in un ottimizzatore scipy COBYLA.

Qui puoi vedere il valore della funzione di costo nel corso delle iterazioni. Inizia un po' irregolare e sale e scende, ma poi si stabilizza su un valore basso. Useremo i valori trovati da scipy che corrispondono alla valutazione più bassa della funzione di costo.

Ora che siamo riusciti a ridurre la nostra funzione di costo trovando valori migliori per i nostri parametri, eseguiremo il nostro circuito usando i nuovi valori trovati per gamma e beta. Ho elencato i valori specifici che sto usando qui, ma ricorda, quando provi tu stesso o anche solo riesegui lo stesso notebook del tutorial, questi valori potrebbero cambiare leggermente. Ora eseguiremo il nostro circuito ottimizzato con questi valori e troveremo la nostra soluzione candidata al problema Max-Cut.

Nella fase di post-elaborazione, analizzeremo i dati e visualizzeremo questi risultati per vedere se il nostro algoritmo quantistico ha trovato le soluzioni corrette.

Post-elaborazione

Ora tracciamo un istogramma dei dati per esaminare la soluzione finale:

Le stringhe di bit rappresentano come ciascuno dei nodi è stato partizionato in due gruppi (etichettati "0" e "1") dal taglio. Dovrebbero esserci quattro soluzioni che danno tutte il valore massimo di archi tagliati. Queste quattro sono mostrate in viola. Puoi vedere subito che 4 soluzioni sono molto più probabili di tutte le altre. La stringa di bit più alta, e quindi più probabile, è 0,1,0,1,1. (Ricorda — l'ordine dei qubit è invertito nelle stringhe di bit del grafico!)

Da questo grafico, possiamo prendere la stringa di bit più probabile e rappresentarla come un grafo partizionato, con il taglio che attraversa cinque archi:

Quindi, questa è effettivamente una soluzione Max-Cut. Ma non è l'unica! A causa della simmetria di questo grafo, esistono più soluzioni corrette. Invece di avere i nodi 0 e 3 all'interno del taglio, potremmo avere i nodi 2 e 4 inclusi. Puoi vedere che tutto ciò che ho dovuto fare è stato ruotare il mio taglio per includere questi nuovi punti. Il numero di archi tagliati rimane cinque. Si scopre che ci sono quattro soluzioni max cut, poiché ciascuna delle due soluzioni che abbiamo notato ha anche un "partner opposto", dove i nodi viola sono grigi e i nodi grigi sono viola — quindi il taglio rimane lo stesso, ma ogni nodo si scambia effettivamente al lato opposto della partizione.

Guardiamo di nuovo l'istogramma e le quattro soluzioni più probabili per un momento. Idealmente, sarebbero ciascuna delle quattro vere soluzioni Max-Cut. Il problema è che l'algoritmo non ha effettivamente identificato la quarta e ultima soluzione come una delle 4 risposte più probabili. Era la quinta più probabile. La quarta soluzione identificata dall'algoritmo è errata — se la disegnassi, vedresti che la soluzione ha solo quattro tagli.

Ma ricorda: questo è un algoritmo approssimato. Non è infallibile, e non è corretto al 100% delle volte. Devi impiegare alcune delle tue conoscenze e comprensione per verificare la correttezza delle soluzioni.

Questo errore può derivare da diversi fattori:

1. Potrebbe essere la natura approssimata dell'algoritmo stesso, e il piccolo numero di livelli che ho utilizzato.
2. Potrebbe essere un errore di campionamento finito; questo potrebbe essere ridotto aumentando il numero di shots nell'esperimento.
3. Potrebbe anche essere un errore di readout, poiché la quarta soluzione reale differisce di un solo bit.

Questo tipo di analisi degli errori è ciò che serve per diventare un professionista del calcolo quantistico. Devi capire le prestazioni dell'hardware e come questo possa contribuire a certi tipi di errori e come correggerli.

Tuttavia, non dimentichiamo che c'erano 32 possibili stringhe di bit, e che le quattro soluzioni reali erano incluse nei cinque migliori candidati. E abbiamo usato solo due livelli per trovarlo. In generale, se volessimo aumentare le nostre possibilità di trovare il miglior Max-Cut ogni volta, potremmo aumentare la profondità dei livelli. Ci sono alcune sottigliezze in questo, ma le vedremo in una lezione successiva.

Su scala utility

Ora che hai avuto un assaggio del processo di risoluzione di un piccolo problema Max-Cut su un computer quantistico, ti sfido a farlo su larga scala. Segui il tutorial collegato per vedere quanti tagli riesci a ottenere in un grafo a 125 nodi.