Efficient Fourier-Based Linear Combination of Unitaries and Applications in Quantum Optimization

Sintesi Tecnica: Combinazione Lineare Efficiente di Unitari Basata su Fourier e Applicazioni nell'Ottimizzazione Quantistica

Enunciazione del Problema
Gli algoritmi di ottimizzazione quantistica, in particolare l'Algoritmo Quantistico Approssimato per l'Ottimizzazione (QAOA), incontrano barriere significative di implementazione sull'hardware a breve termine. La struttura matematica dei problemi di ottimizzazione, specialmente quelli che coinvolgono vincoli (ad esempio, vincoli di cardinalità), spesso richiede circuiti quantistici con elevata connettività (interazioni da tutti a tutti), profondità di circuito elevate e numerosi gate a due qubit. Questi requisiti superano frequentemente le capacità degli attuali processori quantistici superconduttori. Sebbene esistano strategie come il taglio del circuito o l'approssimazione dei circuiti, queste spesso sacrificano la qualità della soluzione a favore della complessità o richiedono un sovraccarico di campionamento sostanziale senza garanzie rigorose di prestazioni.

Metodologia
Gli autori propongono un framework di Combinazione Lineare di Unitari (LCU) basato su Fourier progettato per approssimare circuiti quantistici complessi utilizzando ensemble di circuiti più semplici e compatibili con l'hardware. La metodologia centrale comprende:

1. LCU senza Ancilla per il Campionamento: A differenza delle implementazioni LCU standard che utilizzano un qubit ancilla per implementare coerentemente una combinazione lineare di unitari (richiedendo operazioni controllate), questo lavoro si concentra su applicazioni basate sul campionamento. Eliminando i fattori di segno associati alla decomposizione quasi-probabilistica (QPD) e sostituendo l'ancilla con casualità classica, il metodo elimina la necessità di qubit ancilla e gate controllati. Ciò trasforma l'implementazione in una miscela probabilistica di circuiti più semplici, dove il sovraccarico di campionamento è quantificato da un fattore $\Gamma$.
2. Decomposizione in Fourier per Unitari Diagonali: Per gli unitari diagonali (comuni nelle funzioni di costo e nei termini di penalità), gli autori utilizzano la trasformata discreta di Fourier. Un unitario target $U_f(\gamma) = \sum_x e^{-i\gamma f(g(x))} |x\rangle\langle x|$ viene decomposto in una combinazione lineare di unitari più semplici $V(\theta_j)$, che sono spesso strati di gate $R_Z$ a singolo qubit. I coefficienti sono derivati dalla trasformata di Fourier della funzione che definisce l'unitario. Questo approccio sostituisce interazioni complesse a più qubit (ad esempio, penalità quadratiche che richiedono $O(n^2)$ gate) con strati a singolo qubit, a costo di un sovraccarico di campionamento $\Gamma \le m+1$.
3. Estensione a Unitari Non-Diagonali Invarianti per Permutazione: Il framework è generalizzato a unitari non diagonali, come il mixer XY completamente connesso utilizzato per preservare i vincoli di peso di Hamming. Sfruttando la dualità di Schur-Weyl e la teoria delle rappresentazioni di $SU(2)$, gli autori esprimono gli unitari invarianti per permutazione come combinazioni lineari continue di rotazioni collettive a singolo qubit $R(g)^{\otimes n}$. Ciò consente l'implementazione di mixer altamente non locali utilizzando esclusivamente gate a singolo qubit, con un sovraccarico di campionamento teorico limitato da $O(n^3)$.
4. Connessione al Rilassamento Lagrangiano: Il documento stabilisce un legame formale tra le penalità quantistiche basate su Fourier e il rilassamento lagrangiano classico. L'ottimizzazione di un singolo ramo della decomposizione LCU si dimostra equivalente all'ottimizzazione di un parametro lagrangiano, fornendo una prospettiva unificata sulla gestione dei vincoli.

Contributi Chiave

• Sviluppo del Framework: Introduzione di un framework LCU basato su Fourier e senza ancilla che decompone ampie classi di unitari diagonali e non diagonali in ensemble di strati di gate a singolo qubit.
• Efficienza Hardware: Dimostrazione che operatori complessi e connessi da tutti a tutti (come penalità di cardinalità e mixer XY) possono essere sostituiti da circuiti significativamente più semplici, scambiando profondità e connettività del circuito con un sovraccarico di campionamento polinomiale.
• Garanzie Teoriche: Fornitura di limiti rigorosi sulle prestazioni, mostrando che la probabilità di campionare stringhe di bit di alta qualità nell'approccio LCU è limitata inferiormente dalla probabilità coerente scalata per $1/\Gamma$. Il documento collega inoltre l'ottimizzazione del Conditional Value at Risk (CVaR) a questi limiti.
• Validazione della Scalabilità: Applicazione riuscita del framework al problema del sottografo più denso di k nodi su istanze fino a 106 qubit su hardware quantistico IBM reale, una scala precedentemente intrattabile per implementazioni completamente coerenti di tali vincoli.

Risultati Sperimentali
Gli autori hanno validato il loro approccio attraverso simulazioni esatte di vettori di stato su un'istanza a 12 nodi e esperimenti su larga scala su un dispositivo a 106 qubit:

• Simulazione a 12 Nodi: I confronti tra QAOA completamente coerente e l'approccio LCU basato su Fourier hanno mostrato che, sebbene i valori attesi grezzi dei circuiti LCU fossero inferiori (a causa del sovraccarico di campionamento), l'ottimizzazione di un singolo circuito base LCU (un ansatz variazionale derivato dall'LCU) ha prodotto la probabilità più alta di campionare soluzioni ottimali, superando la baseline coerente in metriche specifiche.
• Esperimento Hardware a 106 Nodi: Su un grafo heavy-hex a 106 qubit (esteso tramite strati SWAP), sono stati eseguiti gli approcci LCU basati su penalità e su mixer XY. I risultati hanno dimostrato che il sovraccarico di campionamento pratico era significativamente inferiore ai limiti teorici nel caso peggiore ($\Gamma \approx 10^4$). L'ansatz LCU a ramo singolo ha trovato con successo soluzioni di alta qualità (fino a 81 archi nel sottografo più denso) con probabilità fattibili comprese tra il 2,7% e il 4,8%, indicando la fattibilità del metodo per problemi su larga scala.
• Mixer XY vs. Penalità: L'approccio LCU basato su mixer XY ha generalmente superato l'approccio basato su penalità, in particolare quando si utilizzava un singolo circuito base ottimizzato, suggerendo che i mixer che preservano i vincoli sono più efficaci se combinati con questa decomposizione.

Significato e Affermazioni
Il documento afferma che il framework LCU basato su Fourier offre una via sistematica per estendere la portata pratica dell'ottimizzazione quantistica a breve termine. Sostituendo operazioni coerenti complesse con combinazioni ponderate di circuiti più semplici, il metodo amplia la gamma di istanze di problemi (in particolare quelle con vincoli globali) che possono essere eseguite sull'hardware attuale. Gli autori sottolineano che questo approccio non richiede la riproduzione esatta della distribuzione target, ma si concentra sul campionamento di soluzioni di alta qualità, un obiettivo ben adatto ai compiti di ottimizzazione. Il lavoro suggerisce che il compromesso tra complessità del circuito e sovraccarico di campionamento è favorevole, poiché i limiti teorici sono spesso lassi nella pratica, e il metodo consente lo studio di algoritmi e istanze di problemi che altrimenti sarebbero oltre le capacità hardware. Il documento conclude che ciò fornisce un principio di progettazione flessibile per algoritmi quantistici più compatibili con l'hardware, in particolare per la gestione dei vincoli nel QAOA.