Evaluating Parameter Transfer in FALQON Across Graph Families

Riepilogo Tecnico: Valutazione del Trasferimento dei Parametri in FALQON tra Famiglie di Grafi

Enunciato del Problema
Gli algoritmi basati sul feedback per l'ottimizzazione quantistica, come FALQON (Feedback-based Algorithm for Quantum Optimization), offrono un'alternativa promettente agli algoritmi quantistici variazionali (VQA) eliminando il ciclo di ottimizzazione classica esplicito. Invece, FALQON costruisce iterativamente circuiti quantistici utilizzando guadagni di feedback derivati dai valori di aspettazione dei commutatori misurati. Tuttavia, rimane una sfida fondamentale di scalabilità: all'aumentare delle dimensioni del problema, cresce il numero di misurazioni necessarie per calcolare i parametri di controllo, portando a un elevato sovraccarico e a una potenziale instabilità. Sebbene il trasferimento dei parametri sia stato esplorato negli algoritmi variazionali (ad esempio QAOA) per riutilizzare i parametri tra istanze strutturalmente simili, la sua applicabilità a strategie basate sul feedback come FALQON—dove i parametri sono generati dinamicamente anziché ottimizzati tramite discesa del gradiente—rimane poco investigata. Questo lavoro affronta la questione se i parametri di feedback appresi su piccoli grafi "donatori" possano essere trasferiti efficacemente a grafi "riceventi" più grandi per ridurre il sovraccarico delle misurazioni e accelerare la convergenza.

Metodologia
Gli autori hanno condotto uno studio empirico sistematico utilizzando simulazioni esatte di vettori di stato per isolare la trasferibilità dei parametri dal rumore hardware e dagli errori di campionamento. Il protocollo sperimentale ha coinvolto:

• Protocollo Donatore-Ricevente: Le sequenze di parametri $\beta^{(D)} = (\beta^{(D)}_1, \dots, \beta^{(D)}_L)$ sono state ottimizzate su grafi donatori più piccoli con dimensioni $n \in \{8, 10, 12\}$. Queste sequenze sono state poi applicate direttamente a grafi riceventi più grandi con una dimensione fissa di $n' = 14$ utilizzando una mappatura strato-a-strato rigorosa ($\beta^{(R)}_t = \beta^{(D)}_t$), senza interpolazione o re-indicizzazione.
• Famiglie di Grafi: Gli esperimenti hanno utilizzato due insiemi canonici di grafi casuali ampiamente utilizzati nei benchmark di ottimizzazione quantistica:
  • Grafi 3-Regolari ($G_{n,3}$): Grafi altamente simmetrici in cui ogni vertice ha grado tre.
  • Grafi di Erdős–Rényi ($G(n, p)$): Grafi casuali con probabilità di connessione $p$, che permettono di sondare densità variabili.
• Metriche di Valutazione: Le prestazioni sono state misurate utilizzando il rapporto di approssimazione (il valore del taglio rispetto all'ottimo esatto di Max-Cut, calcolato tramite forza bruta classica per $n=14$). I trasferimenti sono stati valutati all'interno e tra le famiglie di grafi, testando specificamente i trasferimenti da donatori 3-regolari a riceventi di Erdős–Rényi e viceversa.

Contributi Chiave

1. Analisi della Trasferibilità in Base alla Dimensione del Problema: Lo studio quantifica il riutilizzo dei parametri di controllo di FALQON da istanze piccole ($n=8, 10, 12$) a istanze più grandi ($n=14$), analizzando il degrado delle prestazioni e il comportamento di convergenza.
2. Dipendenza dalla Famiglia di Hamiltoniani: Il lavoro indaga l'efficacia del trasferimento attraverso diverse connettività strutturali (regolare vs casuale) e densità, identificando come la similarità strutturale influenzi il successo del trasferimento.
3. Resilienza alla Dimensione del Donatore: Gli autori dimostrano che la dimensione specifica del grafo donatore è un fattore secondario, mostrando che donatori piccoli e computazionalmente economici (ad esempio $n=8$) forniscono sequenze di parametri statisticamente indistinguibili da quelle di donatori più grandi.

Risultati
L'analisi empirica ha rivelato tre modelli principali riguardanti il trasferimento dei parametri in FALQON:

• Riceventi Densi Ottenono Elevato Successo: Il trasferimento è altamente efficace per riceventi di Erdős–Rényi densi (alta $p$). Per riceventi con $p \in \{0.8, 0.9, 1.0\}$, i parametri trasferiti hanno raggiunto alti rapporti di approssimazione (fino a 0,98 per grafi completi), spesso eguagliando o superando la traiettoria di addestramento del donatore. Gli autori attribuiscono questo alla omogeneità strutturale dei grafi densi, dove il segnale di feedback (valore di aspettazione del commutatore) riflette proprietà medie macroscopiche piuttosto che irregolarità locali, permettendo ai segnali di donatori piccoli di scalare efficacemente.
• Trasferimento Cross-Famiglia in Grafi Sparsi è Difficile: Il trasferimento di parametri da donatori 3-regolari a riceventi di Erdős–Rényi sparsi (ad esempio $p=0.2$) ha portato a un degrado significativo delle prestazioni, con le curve trasferite che rimanevano al di sotto dei riferimenti del donatore. Ciò suggerisce che l'alta variabilità strutturale e la discrepanza nella dinamica degli Hamiltoniani ostacolano il trasferimento in regimi sparsi e cross-famiglia.
• Indipendenza dalla Dimensione del Donatore: Le prestazioni dei parametri trasferiti sono state notevolmente resilienti alla dimensione del grafo donatore. I donatori di dimensione $n=8$ hanno performato in modo competitivo rispetto a quelli di $n=10$ e $n=12$, con deviazioni standard sovrapposte che indicano nessun vantaggio statisticamente significativo nell'uso di donatori più grandi.

Significato e Affermazioni
Il paper afferma che il trasferimento dei parametri è una strategia praticabile per migliorare la scalabilità di FALQON per problemi combinatori di grandi dimensioni. Il significato principale risiede nella scoperta che il successo del trasferimento è dettato dalle proprietà strutturali del grafo ricevente (in particolare la densità) piuttosto che dalla dimensione del donatore. Di conseguenza, grafi piccoli e computazionalmente economici possono generare parametri di controllo robusti per target più grandi, riducendo significativamente il sovraccarico delle misurazioni associato al ciclo di feedback. Gli autori concludono che, sebbene il trasferimento sia altamente efficace per istanze di problemi dense o "più facili", incontra sfide in regimi sparsi e strutturalmente dissimili. Suggeriscono che i lavori futuri dovrebbero investigare i limiti assoluti di questa invarianza di scala ed esplorare la normalizzazione dei parametri per estendere la trasferibilità attraverso divari dimensionali più estremi.