Near-Optimal Parameter Tuning of Level-1 QAOA for Ising Models

Sintesi Tecnica: Ottimizzazione dei Parametri Quasi-Ottimali per QAOA di Livello-1 per Modelli di Ising

Definizione del Problema
L'Algoritmo di Ottimizzazione Quantistica Approssimata (QAOA) è un algoritmo ibrido quantistico-classico progettato per risolvere problemi di ottimizzazione combinatoria, come la Ottimizzazione Binaria Non Vincolata Quadratica (QUBO), codificando le soluzioni nello stato fondamentale di un Hamiltoniano. Sebbene l'aumento della profondità del circuito ($p$) migliori teoricamente la qualità della soluzione, le implementazioni pratiche su dispositivi NISQ (Noisy Intermediate-Scale Quantum) sono vincolate a profondità ridotte ($p=1$, o QAOA1) a causa del rumore dei gate, dei limiti di connettività e degli errori di preparazione dello stato.

Un collo di bottiglia critico in QAOA1 è l'ottimizzazione dei suoi due parametri variazionali, $\gamma$ e $\beta$. Nonostante la bassa dimensionalità, il panorama dei costi è altamente oscillatorio, con tassi di oscillazione che aumentano con la dimensione del problema, la densità e la variabilità dei pesi. La concezione comune suggerisce che ricerche su griglia grossolane seguite da minimizzazione locale siano sufficienti; tuttavia, questo lavoro dimostra che tali approcci spesso non riescono a catturare il vero ottimo globale a causa della distorsione del panorama e dell'aliasing, portando a stime dei parametri subottimali. Inoltre, gli esistenti metodi euristici per l'inizializzazione dei parametri spesso mancano di garanzie di prestazione o si basano su specifiche strutture di grafi (ad esempio, grafi regolari non pesati) che non si generalizzano a istanze reali complesse e pesate.

Metodologia
Gli autori propongono una strategia rigorosa e agnostica rispetto al problema per ottimizzare i parametri di QAOA1 per i modelli di Ising (l'equivalente quantistico di QUBO) in tempo polinomiale. La metodologia procede attraverso quattro fasi teoriche e algoritmiche principali:

1. Analisi di Fourier e Requisiti di Campionamento:
   Il documento modella il valore di aspettazione di QAOA1 come una serie di Fourier parziale. Derivando espressioni in forma chiusa per il valore di aspettazione (Teorema 1 e Corollario 1), gli autori determinano analiticamente la frequenza massima ($\omega_{\max}$) del panorama dei costi lungo la dimensione $\gamma$. Questa frequenza dipende dalle intensità di accoppiamento ($J_{uv}$) e dai campi esterni ($h_i$) dell'istanza specifica del problema. Applicando il Teorema del Campionamento di Nyquist-Shannon, essi stabiliscono la risoluzione di campionamento minima ($\Delta\gamma$) necessaria per ricostruire accuratamente il panorama dei costi senza distorsioni. Ciò risolve il problema del sottocampionamento nelle ricerche su griglia grossolane.

2. Riduzione della Dimensionalità:
   Un contributo teorico chiave è la riduzione del problema di ottimizzazione bidimensionale su $(\gamma, \beta)$ a una ricerca unidimensionale su $\gamma$.

• Per i modelli di Ising senza campi esterni, l'ottimo $\beta^*$ è derivato analiticamente come funzione di $\gamma$ (Teorema 5).
• Per i modelli con campi esterni, l'ottimo $\beta^*$ viene trovato risolvendo un polinomio quartico derivato dalle condizioni di ottimalità del primo ordine (Teorema 6).
  Questa trasformazione permette all'algoritmo di eseguire una ricerca su linea su $\gamma$ calcolando contemporaneamente l'ottimo $\beta^*$ in ogni punto, riducendo significativamente la complessità computazionale.

3. Algoritmo di Ottimizzazione:
   Per trovare l'ottimo globale della risultante funzione univariata, gli autori impiegano un algoritmo di suddivisione (Algoritmo 1) basato sull'analisi degli intervalli (algoritmo di Greene). Questo metodo stima efficientemente il modulo massimo del polinomio trigonometrico, garantendo l'identificazione del $\gamma^*$ quasi-ottimale senza ricorrere a ricerche esaustive su griglia.

4. Concentrazione degli Ottimi:
   Il documento dimostra rigorosamente che, per grafi regolari grandi e densi, l'ottimo globale $\gamma^* \in \mathbb{R}^+$ si concentra molto vicino a zero e coincide con il primo ottimo locale (Teorema 7). L'analisi empirica su grafi di dimensione finita conferma che le istanze "avversarie" (dove il primo ottimo locale differisce dall'ottimo globale) sono rare, occorrendo principalmente in grafi piccoli e sparsi. Questa intuizione permette un'ulteriore semplificazione: invece di una ricerca completa su linea, può essere utilizzato un gradiente discendente inizializzato vicino a $\gamma \approx 0$, a condizione che la dimensione del passo rispetti il limite di campionamento derivato dalla frequenza massima.

Risultati Chiave
La strategia proposta è stata validata utilizzando il Recursive QAOA (RQAOA), un metodo che utilizza QAOA1 come sottoprocedimento per ridurre ricorsivamente la dimensione del problema. Gli autori hanno testato il loro approccio su grandi grafi di Erdős-Rényi pesati e densi (128 e 256 vertici) con diverse probabilità di arco e distribuzioni di peso.

• Senza Campi Esterni: Il metodo proposto (RQAOA1 con parametri quasi-ottimali) ha superato costantemente sia il RQAOA1 ottimizzato grossolanamente che la programmazione semidefinita classica (SDP) in tutte le istanze testate. Al contrario, il RQAOA1 ottimizzato grossolanamente generalmente non è riuscito a superare l'SDP.
• Con Campi Esterni: Gli autori hanno osservato che lo standard RQAOA1 mostrava prestazioni inconsistenti sui modelli con campi. Per affrontare ciò, hanno introdotto "Iter-QAOA", una variante che utilizza una procedura di arrotondamento iterativa semplificata. Iter-QAOA, combinato con la strategia di ottimizzazione dei parametri proposta, ha superato costantemente l'SDP e le varianti standard di RQAOA1, dimostrando robustezza attraverso diverse densità di grafi.
• Istanze Avversarie: I test empirici hanno mostrato che la probabilità di incontrare un grafo avversario (dove il primo ottimo locale non è l'ottimo globale) si stabilizza a circa l'1% per grafi con più di $n > 14$ nodi, validando la strategia di utilizzare il gradiente discendente vicino allo zero per la maggior parte dei casi pratici.

Significatività e Rivendicazioni
Il documento sostiene di aver risolto la sfida di trovare efficientemente i parametri quasi-ottimali per QAOA1 su problemi QUBO arbitrari. La significatività del lavoro risiede in:

• Garanzie Rigorose: A differenza dei precedenti approcci euristici, questo metodo fornisce algoritmi in tempo polinomiale con quasi-ottimalità provabile per pesi commensurabili che non scalano esponenzialmente con la dimensione del sistema.
• Agnosticismo rispetto al Problema: La strategia non dipende da assunzioni sulla simmetria, struttura o distribuzione dei pesi del grafo, rendendola applicabile a modelli di Ising pesati generali.
• Efficienza Pratica: Riducendo lo spazio di ricerca e sfruttando le soluzioni analitiche per $\beta^*$, il metodo evita l'infattibilità computazionale delle ricerche su griglia 2D ad alta risoluzione, evitando al contempo le insidie del campionamento grossolano.
• Miglioramento delle Prestazioni: I risultati dimostrano che, con un'adeguata ottimizzazione dei parametri, gli algoritmi quantistici a profondità ridotta (QAOA1) possono superare le euristiche classiche allo stato dell'arte (SDP) su istanze dense e pesate, evidenziando il ruolo critico dell'ottimizzazione dei parametri nei algoritmi quantistici variazionali.

Gli autori concludono che il loro approccio affronta efficacemente il collo di bottiglia dell'ottimizzazione dei parametri per QAOA1, consentendo approssimazioni più affidabili e di alta qualità per problemi di ottimizzazione combinatoria sull'attuale e prossimo hardware quantistico.