Quantum-Inspired Algorithm for Classical Spin Hamiltonians Based on Matrix Product Operators

Sintesi Tecnica: Algoritmo di Ispirazione Quantistica per Hamiltoniane di Spin Classiche Basato su Operatori di Prodotto di Matrici

Enunciato del Problema
Il documento affronta la sfida di risolvere problemi di ottimizzazione combinatoria (COP) formulati come Hamiltoniane di spin-glass classiche. Questi problemi, che includono la ricerca degli stati fondamentali di modelli di Ising con interazioni competitive, sono generalmente NP-difficili a causa della dimensione esponenziale dello spazio delle configurazioni e della presenza di frustrazione. I metodi euristici classici, come il Simulated Annealing (SA) e gli Algoritmi Genetici, spesso forniscono soluzioni quasi ottimali ma possono incontrare difficoltà con paesaggi energetici complessi. Al contrario, gli algoritmi di ispirazione quantistica che utilizzano le reti tensoriali, come il Density-Matrix Renormalization Group (DMRG), sono efficienti ma sono soggetti a rimanere intrappolati in minimi locali, in particolare quando il paesaggio energetico presenta grandi degenerazioni.

Metodologia
Gli autori propongono un approccio "powered-MPO" che combina il filtraggio spettrale con le rappresentazioni di reti tensoriali per risolvere questi problemi di ottimizzazione su hardware classico. La metodologia procede attraverso i seguenti passaggi:

1. Trasformazione dell'Hamiltoniana: L'Hamiltoniana del costo $\hat{H}$ viene traslata e scalata per formare un nuovo operatore $\hat{G} = a\hat{H} + b\hat{I}$. I parametri $a$ e $b$ sono scelti in modo che $\hat{G}$ sia semidefinito positivo e che gli stati fondamentali del problema originale corrispondano ai maggiori autovalori di $\hat{G}$.
2. Amplificazione Spettrale: L'operatore $\hat{G}$ viene elevato a una potenza elevata $K$ (ovvero, $\hat{G}^K$). Questa operazione amplifica esponenzialmente i pesi relativi delle configurazioni con i maggiori autovalori (gli stati fondamentali di $\hat{H}$), sopprimendo al contempo le altre.
3. Rappresentazione tramite Rete Tensoriale:
   • $\hat{G}$ è rappresentato come un Operatore di Prodotto di Matrici (MPO).
   • La potenza $\hat{G}^K$ viene costruita tramite ripetute contrazioni MPO-MPO. Gli autori utilizzano due programmi di contrazione: un programma "lineare" (moltiplicando ripetutamente per $\hat{G}$) e un programma di "raddoppio" (elevando al quadrato il risultato iterativamente, $K=2^m$).
   • Durante la contrazione, la dimensione del legame (bond dimension) viene troncata utilizzando la Decomposizione ai Valori Singolari (SVD) con una soglia fissa per gestire il costo computazionale, mantenendo una dimensione massima del legame $\chi$.
4. Campionamento: Il risultante MPO potenziato viene incorporato in uno Stato di Prodotto di Matrici (MPS) agendo su uno stato di sovrapposizione uniforme $|+\rangle^{\otimes N}$. Poiché $\hat{G}^K$ è diagonale nella base computazionale, questa incorporazione permette un "campionamento perfetto" di stringhe di bit. La probabilità di campionare una configurazione è proporzionale al quadrato del corrispondente elemento diagonale in $\hat{G}^K$, orientando l'output verso stati a bassa energia.

Contributi Chiave

• Filtraggio Spettrale Senza Trotter: A differenza dei metodi di evoluzione temporale immaginaria quantistica che si affidano a decomposizioni di porte e Trotterizzazione, questo approccio incorpora direttamente la funzione di costo non unitaria in un singolo MPO classico, evitando gli errori di Trotter.
• Miglioramento Sistematico: Il documento dimostra che, a differenza del DMRG che può ristagnare in minimi locali, il metodo powered-MPO offre una via più sistematica di miglioramento aumentando la dimensione del legame $\chi$.
• Costruzione Efficiente: Gli autori dettagliano la costruzione dell'MPO per funzioni di costo generali e forniscono limiti teorici sulla potenza $K$ necessaria per raggiungere un obiettivo di probabilità di successo, mostrando che $K$ scala inversamente con il gap spettrale e logarithmicamente con la dimensione dello spazio di Hilbert.
• Programmazione Ibrida: Lo studio identifica i punti di forza complementari tra i programmi di contrazione lineare e di raddoppio: il raddoppio fornisce un filtraggio iniziale rapido, mentre l'evoluzione lineare offre un raffinamento stabile e continuo nelle fasi successive.

Risultati
Gli autori hanno testato il metodo su due classi di problemi:

1. Modelli di Spin-Glass di Edwards-Anderson: Testati su reticoli ipercubici $D$-dimensionali ($D=2, 3$).
   • Il metodo powered-MPO ha costantemente superato il DMRG, in particolare quando il DMRG era inizializzato con uno stato di sovrapposizione uniforme, dove spesso rimaneva intrappolato in minimi locali.
   • Mentre i risultati del DMRG mostravano scarso miglioramento con l'aumento della dimensione del legame in questi casi, il metodo powered-MPO mostrava un miglioramento sistematico nel rapporto di approssimazione all'aumentare di $\chi$.
   • Il metodo ha identificato con successo gli stati fondamentali esatti per dimensioni di sistema più piccole e configurazioni a bassa energia per istanze più grandi (fino a $N=400$ variabili).
2. Modelli di Ising ad Ordine Superiore su Reticoli Heavy-Hexagonal: Testati su reticoli rilevanti per gli attuali dispositivi quantistici IBM (problemi HUBO con interazioni fino al cubo).
   • Il metodo powered-MPO (con $\chi=64$) ha superato il Simulated Annealing (sia nella formulazione standard che in quella a ordine ridotto QUBO) nel trovare configurazioni a energia inferiore.
   • Il metodo si è dimostrato robusto contro i paesaggi energetici accidentati caratteristici di questi problemi, con lo schema lineare che alla fine ha superato le prestazioni dello schema di raddoppio per potenze superiori ($m \geq 12$).

Significatività e Rivendicazioni
Il documento sostiene che questo approccio di ispirazione quantistica fornisce una solida linea di base classica per risolvere problemi di ottimizzazione combinatoria, navigando efficacemente paesaggi energetici dove gli euristici tradizionali e i metodi variazionali come il DMRG faticano.

• Baseline per Algoritmi Quantistici: Gli autori pongono in posa che le soluzioni di alta qualità generate da questo metodo basato su reti tensoriali possano servire come benchmark critico per valutare l'utilità e il vantaggio di futuri algoritmi e hardware quantistici.
• Scalabilità e Direzioni Future: Gli autori osservano che, sebbene il metodo richieda più passaggi rispetto al DMRG per convergere, esso evita l'intrappolamento locale. Suggeriscono che il lavoro futuro potrebbe sfruttare il parallelismo a livello MPI e l'accelerazione GPU per gestire dimensioni del legame più elevate ($\chi \sim O(10^3)$). Inoltre, propongono che estendere il metodo a reti tensoriali ad albero o sviluppare tecniche di contrazione più stabili per gli Operatori di Coppia di Entanglement Proiettati (PEPO) potrebbe ulteriormente potenziarne l'applicabilità a topologie di reticolo complesse.
• Modeste Limitazioni: Il documento riconosce che raggiungere soluzioni esatte per tutti i tipi di problemi richiede ancora il superamento di barriere di entanglement elevate, e che la scalabilità della dimensione del legimento richiesta attraverso diverse classi di problemi necessita di una chiarificazione più sistematica. Si nota inoltre che le attuali limitazioni dell'hardware (conteggio dei qubit e operazioni non locali) impediscono l'implementazione diretta della funzione di costo non unitaria su computer quantistici attuali, sebbene l'identificazione di circuiti poco profondi per mimare questa azione rimanga una possibilità futura.