Fair sampling with temperature-targeted QAOA based on quantum-classical correspondence theory

Questo articolo propone SBO-QAOA, un algoritmo quantistico a target di temperatura basato sulla teoria della corrispondenza quantistico-classica che ottiene un campionamento equo degli stati fondamentali degeneri convergendo verso una distribuzione di Gibbs uniforme, superando i bias intrinseci del QAOA standard anche con parametri variazionali minimi.

L'essenziale

Il Grande Problema: Trovare il Vincitore "Equo"

Immaginate di gestire un concorso per trovare la migliore soluzione a un puzzle complesso. In molti casi, non esiste un'unica risposta perfetta; esistono diverse risposte differenti che sono tutte ugualmente perfette. Chiamiamole "stati fondamentali degeneri".

Nel mondo reale, se avete cinque diverse squadre che si classificano tutte a pari merito al primo posto, volete sceglierne una a caso in modo che nessuna squadra si senta imbrogliata. Questo si chiama campionamento equo (fair sampling). Volete che il computer scelga la Squadra A, la Squadra B o la Squadra C con uguale probabilità, non favorendo una solo perché il computer funziona in un certo modo.

Il problema è che l'attuale metodo principale per risolvere questi puzzle sui computer quantistici (chiamato QAOA) è un po' come un arbitro parziale. Man mano che il computer approfondisce il calcolo (aumentando la "profondità del circuito"), inizia ad avare accidentalmente certe squadre vincitrici rispetto ad altre, anche se sono tutte matematicamente uguali. Smette di essere equo.

Il Vecchio Modo vs Il Nuovo Modo

I ricercatori, Tetsuro Abe e Shu Tanaka, hanno studiato come risolvere il problema.

• Il Vecchio Modo (Standard QAOA): Pensate a questo come al tentativo di trovare il fondo di una valle. Il computer usa uno strumento di "scuotimento" standard (un mixer a campo trasverso) per aiutare la pallina a rotolare verso il basso. Il problema è che questo strumento di scuotimento spinge la pallina verso punti specifici sul fondo della valle, ignorando gli altri punti altrettanto profondi. È come un vento che soffia in una sola direzione, spingendo la pallina verso un lato del fondo della valle.
• Il Nuovo Modo (SBO-QAOA): Invece di cambiare lo strumento di "scuotimento", i ricercatori hanno deciso di cambiare la forma della valle stessa. Hanno usato un astuto trucco matematico basato sulla "corrispondenza quantistico-classica".

L'Analogia Creativa: La Mappa Mirata alla Temperatura

Immaginate di voler simulare una folla di persone in una stanza.

• Lo Standard QAOA è come cercare di far sedere tutti sulla singola sedia più confortevole. Funziona, ma costringe tutti in un unico punto, o rischia di favorire una sedia rispetto a un'altra.
• Lo SBO-QAOA è come impostare la temperatura della stanza.
  • Se la stanza è molto fredda (temperatura bassa), tutti vogliono sedersi nei posti migliori in assoluto.
  • Se la stanza è calda (temperatura più alta), le persone sono più rilassate e sparse, sedendosi in vari posti ottimi con una probabilità che corrisponde a quanto sono confortevoli.

I ricercatori hanno progettato una nuova "mappa" (chiamata SBO Hamiltonian) che codifica questo concetto di temperatura direttamente nelle regole del computer quantistico. Invece di cercare solo il singolo punto di energia più bassa, il computer è programmato per assestarsi naturalmente in una distribuzione che somiglia a una stanza calda dove tutti hanno la stessa probabilità di sedersi in uno dei "migliori" posti.

Cosa Hanno Fatto (L'Esperimento)

Per testare questo, hanno utilizzato un piccolo "modello giocattolo" con soli 5 spin (come 5 piccoli magneti). Questo modello è stato progettato per avere sei diverse soluzioni che sono tutte ugualmente buone (un pareggio a sei vie).

Hanno eseguito due tipi di simulazioni:

1. Standard QAOA: Hanno aumentato la complessità (profondità del circuito) per vedere se riusciva a trovare i vincitori.
2. SBO-QAOA: Hanno utilizzato la loro nuova "mappa mirata alla temperatura".

I Risultati

• Standard QAOA: Man mano che rendevano il calcolo più profondo, il computer trovava le soluzioni vincenti molto spesso (quasi il 100% delle volte). Tuttavia, era ingiusto. Continuava a scegliere due soluzioni vincenti specifiche e ignorava le altre quattro. L'arbitro era parziale.
• SBO-QAOA: Il computer ha trovato le soluzioni vincenti circa l'83% delle volte (che è esattamente ciò che la fisica prevede per una stanza a quella specifica "temperatura"). Fondamentalmente, quando trovava un vincitore, lo sceglieva tra tutte e sei le soluzioni con uguale probabilità. Era perfettamente equo.

Ancor meglio, hanno testato una versione "semplificata" del loro nuovo metodo in cui hanno ridotto il numero di impostazioni che il computer doveva regolare a soli quattro manopole. Anche con questa configurazione semplice, il computer rimaneva equo e mirato alla temperatura.

Il Punto Chiave

L'articolo sostiene che non è necessario inventare un complicato nuovo strumento di "scuotimento" per ottenere risultati equi. Inveve, se si cambia l'obiettivo verso cui il computer punta (usando l'SBO Hamiltonian), il computer impara naturalmente a scegliere tutti i vincitori in pareggio in modo equo, proprio come le persone che si disperdono in una stanza a una determinata temperatura.

Questo funziona anche se si mantengono le impostazioni semplici (linear schedule), suggerendo che un campionamento equo è possibile senza rendere eccessivamente complesso il circuito del computer quantistico. Gli autori osservano che, sebbene questo funzioni molto bene nelle piccole simulazioni, il passo successivo è capire come costruire questo metodo in modo efficiente su macchine quantistiche reali e su larga scala, poiché la nuova "mappa" comporta interazioni complesse che sono difficili da costruire fisicamente.

Sommario tecnico

Sintesi Tecnica: Campionamento Equo con QAOA a Target di Temperatura

Enunciato del Problema
Nei problemi di ottimizzazione combinatoria caratterizzati da stati fondamentali degeneri, la capacità di eseguire un "campionamento equo" (fair sampling) — ovvero ottenere una distribuzione uniforme su tutti i soluzoni degeneri senza bias — è critica. Sebbene l'Annealing Quantistico (QA) e il Quantum Approximate Optimization Algorithm (QAOA) siano metaeuristiche promettenti per questi problemi, le implementazioni standard che utilizzano un mixer a campo trasversale spesso non riescono a ottenere un campionamento equo. Prove teoriche ed esperimenti suggeriscono che, all'aumentare della profondità del circuito, il QAOA standard induce bias tra gli stati degeneri, favorendo soluzioni specifiche anche quando il rapporto di approssimazione converge all'unità. Le soluzioni esistenti, come mixer specializzati o post-elaborazione ibrida, spesso aumentano la complessità del circuito o richiedono ulteriori passaggi computazionali classici.

Metodologia
Gli autori propongono SBO-QAOA, una variante del QAOA che affronta il bias di campionamento non modificando il mixer, ma ridisegnando l'Hamiltoniana target (cost) basandosi sulla teoria della corrispondenza quantistico-classica.

• Framework Teorico: Invece di puntare allo stato fondamentale dell'Hamiltoniana di Ising classica $\hat{H}_0$, SBO-QAOA punta allo stato fondamentale di un'Hamiltoniana effettiva, $\hat{H}_S(T)$, derivata da Somma et al. Questa Hamiltoniana è costruita in modo che il suo stato fondamentale unico corrisponda a uno stato quantistico $|\psi_{Gibbs}(T)\rangle$, dove le ampiezze di probabilità sono le radici quadrate dei fattori di Boltzmann del sistema classico a una specifica temperatura $T$.
• Costruzione dell'Hamiltoniana: L'Hamiltoniana SBO è definita come:
  $$\hat{H}_S(T) = -e^{-\alpha/T} \sum_{i=1}^N \left( \hat{\sigma}_i^x - e^{\hat{H}_i/T} \right)$$
  dove $\hat{H}_i$ rappresenta i termini locali di $\hat{H}_0$ dipendenti dallo spin $i$, e $\alpha$ è un fattore di scala che previene la divergenza per $T \to 0$. In SBO-QAOA, $\hat{H}_C$ è impostato come $\hat{H}_S(T)$, mentre il mixer a campo trasversale standard $\hat{H}_X$ viene mantenuto.
• Schemi di Parametrizzazione: Lo studio valuta due strategie di parametrizzazione per gli angoli variazionali $\{\gamma_k, \beta_k\}$:
  1. Full-parameter: $2p$ variabili indipendenti per la profondità del circuito $p$.
  2. Linearizzata: Uno schema di riduzione in cui gli angoli sono funzioni lineari dell'indice di profondità, riducendo le variabili di ottimizzazione a quattro ($\gamma_{slope}, \gamma_{intcp}, \beta_{slope}, \beta_{intcp}$) indipendentemente dalla profondità.
• Setup Sperimentale: Simulazioni numeriche sono state eseguite su un modello toy di Ising frustrato a 5 spin con degenerazione dello stato fondamentale a sei vie. Il sistema è stato simulato esattamente (evoluzione della matrice completa) per confrontare il QAOA standard e SBO-QAOA attraverso diverse profondità di circuito ($p=1$ a $100$) e temperature.

Risultati Chiave

• Bias del QAOA Standard: Nel QAOA standard (che punta a $\hat{H}_0$), l'aumento della profondità del circuito $p$ spinge la probabilità totale dello stato fondamentale ($P_{GS}$) verso l'unità. Tuttavia, la distribuzione all'interno dello spazio degenero rimane polarizzata; coppie di stati specifiche diventano dominanti mentre altre vengono soppresse, indipendentamente dall'uso di parametri full o linearizzati.
• Equità di SBO-QAOA: Quando punta a $\hat{H}_S(T)$, SBO-QAOA esibisce un comportamento fondamentalmente diverso:
  • Targeting della Temperatura: La probabilità totale dello stato fondamentale $P_{GS}$ non si avvicina all'unità ma si satura a un valore coerente con la probabilità della distribuzione di Gibbs alla temperatura $T$ specificata (ad esempio, $\approx 0.83$ per $T=1$).
  • Campionamento Uniforme: All'aumentare di $p$, la distribuzione di probabilità attraverso gli stati fondamentali degeneri diventa uniforme. Le probabilità di distinte coppie di stati convergono verso valori identici, confermando un campionamento equo.
  • Distanza di Variazione Totale (TVD): La TVD tra la distribuzione di output e la distribuzione di Gibbs target diminuisce all'aumentare di $p$, convergendo vicino allo zero. Ciò conferma che l'algoritmo riproduce l'intera distribuzione a temperatura finita, non solo gli stati fondamentali.
• Robustezza alla Riduzione dei Parametri: La proprietà di campionamento equo e di targeting della temperatura di SBO-QAOA è preservata anche sotto lo schema linearizzato, dove il numero di parametri variazionali è ridotto da $2p$ a soli quattro.

Significatività e Rivendicazioni
Il documento afferma che il campionamento equo nel QAOA può essere ottenuto senza aumentare la complessità del mixer o aggiungere passaggi di post-elaborazione classica. Sostituendo l'Hamiltoniana target con l'Hamiltoniana SBO, l'algoritolo codifica intrinsecamente la distribuzione di Gibbs come suo stato fondamentale. Gli autori dimostrano che questo approccio consente:

1. Campionamento Equo: Raggiungere una distribuzione uniforme sugli stati fondamentali degeneri.
2. Targeting della Temperatura: Controllare la distribuzione di campionamento tramite il parametro $T$.
3. Efficienza: Mantenere queste proprietà con un set minimo di parametri variazionali (quattro), rendendo l'approccio potenzialmente scalabile in termini di complessità di ottimizzazione.

Gli autori osservano che, sebbene il presente lavoro validi queste proprietà su un sistema piccolo tramite diagonalizzazione esatta, il lavoro futuro dovrà affrontare la scalabilità. Nello specifico, l'implementazione di $\hat{H}_S(T)$ su dispositivi gate-based richiede espansioni in stringhe di Pauli efficienti e decomposizioni di circuiti, poiché l'Hamiltoniana generalmente induce interazioni a molti corpi.