Scaling QAOA: transferring optimal adiabatic schedules from small-scale to large-scale variational circuits

1. Il Problema

L'algoritmo di Ottimizzazione Quantistica Approssimata (QAOA) è un approccio promettente per la risoluzione di problemi di ottimizzazione combinatoria sui dispositivi quantistici attuali (NISQ). Tuttavia, la sua scalabilità è fortemente limitata da due fattori principali:

• Complessità di ottimizzazione classica: Per un circuito con $p$ strati (layer), QAOA richiede l'ottimizzazione di $2p$ parametri variazionali (angoli $\gamma$ e $\beta$). All'aumentare della profondità del circuito ($p$), lo spazio dei parametri diventa ad alta dimensionalità.
• Barren Plateaus: I landscape di ottimizzazione per circuiti profondi sono spesso affetti da "barren plateaus" (altipiani sterili), dove i gradienti svaniscono esponenzialmente, rendendo il training classico degli angoli intrattabile.

Recenti studi empirici hanno mostrato che gli angoli ottimali di QAOA tendono a concentrarsi e sono trasferibili tra diverse dimensioni del problema. Il paper si pone l'obiettivo di sfruttare questa osservazione per ridurre drasticamente la complessità dell'ottimizzazione.

2. Metodologia

Gli autori propongono un framework di apprendimento dello schedule (schedule-learning) che trasferisce strategie di controllo adiabatico ottimali, derivate da istanze piccole, a sistemi più grandi.

A. Fondamenti Teorici

Il metodo si basa sul teorema adiabatico e sulla relazione tra l'evoluzione adiabatica e QAOA (visto come un'approssimazione Trotterizzata dell'evoluzione adiabatica).

• L'efficienza dell'evoluzione adiabatica è governata dal gap spettrale istantaneo $g(s) = E_1(s) - E_0(s)$ tra lo stato fondamentale e il primo stato eccitato.
• Per minimizzare il tempo di esecuzione, la velocità di evoluzione $ds/dt$ dovrebbe essere proporzionale a una potenza del gap: $ds/dt \propto g^q(s)$.

B. Fase di Apprendimento (Learning Phase)

1. Estrazione del Gap: Su istanze piccole e trattabili (es. $n=10$ qubit), gli autori calcolano il profilo del gap spettrale $g(s)$ per diverse istanze di problemi QUBO (Quadratic Unconstrained Binary Optimization).
2. Modellazione Continua: Viene costruita una funzione continua dello schedule basata sul gap medio o mediano osservato. La dinamica è governata dall'equazione:
   $$\frac{ds}{dt} = \kappa g^q(s)$$
   dove $\kappa$ è una costante di proporzionalità e $q$ è un esponente (tipicamente tra 1 e 2).

C. Mappatura su Circuito Discreto (QAOA)

Il schedule continuo viene discretizzato in $p$ passi per mapparlo su un circuito QAOA.

• Scomponendo l'operatore di evoluzione unitaria tramite la decomposizione di Trotter-Suzuki, si ottengono espressioni in forma chiusa per tutti gli angoli variazionali $\gamma_k$ e $\beta_k$ al layer $k$:
  $$\gamma_k = \frac{s_k \delta s}{\kappa g^q(s_k)}, \quad \beta_k = \frac{(1-s_k) \delta s}{\kappa g^q(s_k)}$$
• Riduzione dei Parametri: Invece di ottimizzare $2p$ parametri indipendenti, il problema classico si riduce alla ricerca di soli 2 iperparametri globali ($\kappa$ e $q$), indipendentemente dalla profondità $p$ del circuito.

3. Contributi Chiave

• Compressione Parametrica Drastica: Trasformazione di un problema di ottimizzazione con $2p$ gradi di libertà in uno con solo 2 iperparametri, indipendentemente dalla dimensione del circuito.
• Trasferibilità Scalabile: Dimostrazione che il profilo del gap spettrale appreso su piccoli sistemi ($n=10$) può essere efficacemente trasferito a sistemi più grandi ($n=20$) mantenendo prestazioni elevate.
• Mitigazione dei Barren Plateaus: Riducendo lo spazio di ricerca a due dimensioni, il metodo riduce la sensibilità ai barren plateaus, facilitando il training di circuiti profondi.
• Formulazione Analitica: Fornitura di formule chiuse per gli angoli QAOA basate sul gap spettrale, eliminando la necessità di un'ottimizzazione variazionale layer-per-layer.

4. Risultati Sperimentali

Gli autori hanno testato il metodo su simulazioni numeriche con istanze di:

• MaxCut 3-regolare (pesato e non pesato).
• QUBO casuali.
• Dimensione dei problemi target: $n=20$ qubit, con $p$ da 1 a 10 strati.

Risultati principali:

• Rapporto di Approssimazione: Le strategie basate sul gap (sia media che mediana) raggiungono rapporti di approssimazione competitivi o superiori rispetto al QAOA standard ("vanilla QAOA"), specialmente per istanze complesse come QUBO casuali e MaxCut pesato.
• Convergenza: Mentre il QAOA standard mostra alta varianza e miglioramento limitato all'aumentare di $p$, le strategie basate sul gap migliorano monotonicamente con la profondità, avvicinandosi a soluzioni di alta qualità.
• Stabilità degli Iperparametri: Gli iperparametri ottimali ($\kappa, q$) tendono a concentrarsi e stabilizzarsi a valori piccoli per $p \ge 7$, indicando una landscape di ottimizzazione più stabile.
• Vantaggio Specifico: Il miglioramento è più marcato per i problemi QUBO casuali e MaxCut pesato, mentre per il MaxCut non pesato il vantaggio è più modesto ma comunque presente.

5. Significato e Implicazioni

Questo lavoro offre una strategia scalabile ed efficiente in termini di parametri per l'implementazione di QAOA su dispositivi reali.

• Efficienza Computazionale: Riduce drasticamente il costo computazionale classico associato all'ottimizzazione dei parametri, rendendo fattibile l'uso di QAOA su circuiti profondi che altrimenti sarebbero intrattabili.
• Induzione Strutturale: Suggerisce che l'informazione strutturale estratta da piccole istanze (come i profili del gap spettrale) può servire come uno schema induttivo principiato per algoritmi quantistici variazionali, superando la necessità di ottimizzare ogni singolo parametro per ogni nuova istanza.
• Futuro: Apre la strada all'applicazione di QAOA su problemi di ottimizzazione combinatoria di grandi dimensioni, mitigando le limitazioni attuali dei dispositivi NISQ legate all'ottimizzazione dei parametri e alla profondità dei circuiti.