Improving the efficiency of QAOA using efficient parameter transfer initialization and targeted-single-layer regularized optimization with minimal performance degradation

Sintesi Tecnica: Miglioramento dell'efficienza di QAOA tramite il trasferimento dei parametri e l'ottimizzazione mirata regolarizzata

Definizione del Problema
L'Algoritmo di Ottimizzazione Approssimata Quantistica (QAOA) è un principale candidato per la risoluzione di Problemi di Ottimizzazione Combinatoria (COP), specificamente il problema del Max-Cut (Massimo Taglio), su dispositivi quantistici a breve termine. Tuttavia, il QAOA affronta sfide significative all'aumentare della dimensione del problema ($n$) e della profondità del circuito ($p$). Il panorama di ottimizzazione diventa altamente non convesso, caratterizzato da uno spazio di soluzioni che cresce esponenzialmente ($2^n$) e da un numero di parametri che aumenta linearmente ($2p$). Questa complessità spesso intrappola gli ottimizzatori classici in minimi locali sub-ottimali, particolarmente per le famiglie di grafi pesati, portando a rapporti di approssimazione ($r$) scarsi. Inoltre, l'ottimizzazione completa di tutti i $2p$ parametri è computazionalmente costosa, richiedendo tempo e risorse considerevoli, il che ostacola la dimostrazione pratica del vantaggio quantistico.

Metodologia
Gli autori propongono una strategia ibrida che combina l'inizializzazione tramite trasferimento dei parametri con l'ottimizzazione mirata a singolo strato e la regolarizzazione L2 per migliorare l'efficienza del QAOA riducendo al minimo la degradazione delle prestazioni.

1. Inizializzazione tramite Trasferimento dei Parametri:

   • L'approccio sfrutta l'osservazione che i parametri ottimizzati per istanze di problemi simili tendono a raggrupparsi.
   • Un grafo "donatore" ($G_1$) con un piccolo numero di nodi ($n_d = 8$) viene completamente ottimizzato. Per questo donatore, l'inizializzazione utilizza il Quantum Annealing Trotterizzato (TQA) con $t=0.75$, seguito da una piena ottimizzazione utilizzando l'ottimizzatore Adagrad.
   • Questi parametri ottimizzati $\{\gamma^*_i, \beta^*_i\}$ vengono trasferiti a un grafo "accettore" ($G_2$) con $n_a \ge n_d$ nodi all'interno della stessa famiglia di grafi.

2. Ottimizzazione Mirata a Singolo Strato:

   • Invece di ri-ottimizzare tutti i $2p$ parametri per il grafo accettore, il metodo identifica uno strato specifico "mirato" ($p_k$) che produce il miglior rapporto di approssimazione quando ottimizzato individualmente.
   • Per una profondità fissa $p=15$, gli autori hanno testato sistematicamente ogni strato $p_k \in [1, 15]$ per determinare lo strato ottimale più probabile per diverse famiglie di grafi (3-Regolare, Erdős–Rényi, Barabási–Albert).
   • Solo i parametri di questo singolo strato vengono ottimizzati utilizzando l'ottimizzatore COBYLA (Constrained Optimization By Linear Approximation), mentre tutti gli altri strati rimangono fissi ai loro valori trasferiti.

3. Regolarizzazione (L2/Ridge):

   • Per affrontare l'incoerenza per cui l'ottimizzazione mirata a singolo strato ($r_s$) occasionalmente supera l'ottimizzazione completa ($r_f$) a causa dell'intrappolamento dell'ottimizzatore in minimi locali durante il processo di ottimizzazione completa, gli autori introducono la regolarizzazione L2 (Ridge).
   • Un termine di penalità $\lambda \sum (\gamma_k^2 + \beta_k^2)$ viene aggiunto alla funzione di costo. Questo leviga il panorama della soluzione, aiutando l'ottimizzatore a uscire dai minimi locali e migliorando l'affidabilità dell'ottimizzazione completa ($r_f$).

Contributi Chiave e Risultati
Lo studio è stato condotto su tre famiglie di grafi non pesati (3-Regolare, Erdős–Rényi, Barabási–Albert) e tre famiglie pesate, utilizzando grafi con conteggi di nodi compresi tra 8 e 24.

• Prestazioni nei Grafi Non Pesati:

  • Per i grafi 3-Regolari non pesati (u3R), l'approccio di trasferimento dei parametri ha raggiunto un rapporto di approssimazione medio di 0,9443 per l'ottimizzazione mirata a singolo strato ($r_s$), rispetto a 0,9551 per l'ottimizzazione completa ($r_f$). Ciò rappresenta il 98,88% delle prestazioni ottimali.
  • Fondamentalmente, questo approccio ha prodotto un incremento di velocità computazionale di 8,06× rispetto all'ottimizzazione completa.
  • Tendenze simili sono state osservate per i grafi Erdős–Rényi (uER) e Barabási–Albert (uBA) non pesati, dove $r_s$ è rimasto costantemente vicino a $r_f$ riducendo significativamente il tempo di ottimizzazione ($\tau$).

• Prestazioni nei Grafi Pesati:

  • 3-Regolare Pesato (w3R): Il metodo ha funzionato bene, con la sola inizializzazione ($r_n$) che spesso superava la soglia classica di Goemans-Williamson ($r_{GW} \ge 0,878$). L'ottimizzazione mirata ha ulteriormente migliorato questi risultati.
  • Erdős–Rényi Pesato (wER): L'approccio ha faticato con nodi più grandi ($n_a \ge 14$), dove $r_s$ è sceso al di sotto della soglia $r_{GW}$. Per queste famiglie pesate più complesse, l'ottimizzazione completa è rimasta necessaria per ottenere soluzioni di alta qualità.
  • Barabási–Albert Pesato (wBA): Questa famiglia ha mostrato un comportamento ibrido; sebbene l'ottimizzazione completa fosse leggermente più efficiente, l'ottimizzazione mirata rimaneva un'alternativa valida.

• Impatto della Regolarizzazione:

  • Senza regolarizzazione, l'ottimizzazione mirata a singolo strato ha superato l'ottimizzazione completa nell'8,92% dei casi di test (indicando che l'ottimizzazione completa era intrappolata in minimi locali).
  • L'applicazione della regolarizzazione L2 ha ridotto questa incoerenza al 3,81%, migliorando significativamente la robustezza dell'ottimizzazione completa.

• Confronto tra Ottimizzatore e Inizializzazione:

  • Tra vari ottimizzatori (COBYLA, POWELL, GSLS, NELDER-MEAD, SPSA), COBYLA è stato identificato come il più adatto, offrendo un'accuratezza comparabile con il minor tempo di ottimizzazione.
  • L'inizializzazione tramite trasferimento dei parametri ha costantemente superato la TQA e l'inizializzazione casuale sia in termini di rapporto di approssimazione che di numero di passi di ottimizzazione richiesti.

Significato e Rivendicazioni
Il documento dimostra che un'efficace inizializzazione dei parametri combinata con l'ottimizzazione mirata a singolo strato può migliorare significativamente l'efficienza del QAOA con una degradazione minima delle prestazioni.

Gli autori affermano che questa strategia bilancia efficacemente il compromesso tra accuratezza e costo computazionale. Trasferendo i parametri da istanze piccole, completamente ottimizzate, a istanze più grandi e complesse, il metodo fornisce un punto di partenza "quasi ottimale" che riduce lo spazio di ricerca. La successiva ottimizzazione di un singolo strato strategicamente scelto affina ulteriormente la soluzione senza il costo esponenziale della ri-ottimizzazione completa.

Il lavoro evidenzia che, sebbene questo approccio sia altamente efficace per grafi non pesati e specifiche famiglie pesate (come w3R), non è una soluzione universale per tutte le topologie pesate (specificamente wER), dove la complessità del panorama dei costi richiede ancora l'ottimizzazione completa. L'introduzione della regolarizzazione L2 è presentata come una strategia di mitigazione critica per stabilizzare il panorama di ottimizzazione, garantendo che l'ottimizzazione completa non performi peggio rispetto ai metodi selettivi. In definitiva, lo studio suggerisce una via per rendere il QAOA più pratico per problemi combinatori su larga scala riducendo l'overhead computazionale classico associato alla sintonizzazione dei parametri.