Sintesi Tecnica: Approcci Variazionali Quantistici al Problema del Massimo Insieme Indipendente su Scala Utility

Definizione del Problema

Il problema del Massimo Insieme Indipendente (MIS - Maximum Independent Set) cerca il più grande sottoinsieme di vertici in un grafo non orientato tale per cui nessun paio di vertici sia adiacente. È un problema canonico NP-hard con applicazioni nell'assegnazione delle frequenze, l'analisi delle interazioni proteiche e la progettazione VLSI. Mentre i solver classici esatti (branch-and-bound, programmazione intera) faticano con istanze difficili oltre i pochi centinaia di vertici, il calcolo quantistico offre potenziali euristiche. Tuttavia, gli algoritmi variazionali basati su gate affrontano sfide significative nell'era NISQ (Noisy Intermediate-Scale Quantum), tra cui il numero limitato di qubit, i tempi di coerenza brevi e il fenomeno dei "barren plateau" (plateau sterili) dove i gradienti svaniscono esponenzialmente.

Una specifica sfida strutturale sorge per grafi grandi e densi in cui il MIS costituisce una frazione minuscola del totale dei vertici (ad esempio, 15 su 180). In tali casi, la soluzione ottimale occupa una regione esponenzialmente piccola dello spazio di Hilbert. Gli approcci standard che inizializzano con una sovrapposizione uniforme assegnano un'ampiezza trascurabile al MIS, causando spesso la convergenza dei circuiti variazionali verso bacini di energia subottimali da cui è difficile uscire senza cambiamenti coordinati multi-qubit.

Metodologia

Gli autori propongono un framework stratificato che combina pre-elaborazione del circuito, ottimizzazione variazionale e post-elaborazione classica per affrontare queste sfide attraverso tre istanze benchmark: 64, 99 e 180 nodi.

1. Pre-elaborazione e Costruzione del Circuito

• Riorganizzazione dei Vertici: Per minimizzare l'overhead dei SWAP e migliorare l'efficienza dell'entanglement, gli autori confrontano tre strategie di riordinamento: BFS pesata per accoppiamento, Reverse Cuthill-McKee (RCM) e Riorganizzazione Spettrale (usando il vettore di Fiedler). La riorganizzazione spettrale viene adottata in quanto supera costantemente le altre su istanze dense raggruppando i vertici strutturalmente prossimi, minimizzando così la distanza di indice tra qubit fortemente accoppiati.
• Sparsificazione Basata sulla Distanza: Applicata specificamente ai circuiti QAOA, questa tecnica rimuove le interazioni a lungo raggio dalla costruzione del circuito (mantenendo solo gli archi dove $|i-j| \le k$) pur valutando l'energia con l'Hamiltoniana completa. Ciò riduce significativamente la profondità del circuito, rendendo le simulazioni trattabili su simulatori Matrix Product State (MPS).
• Algoritmi: Lo studio confronta il Variational Quantum Eigensolver (VQE) utilizzando un ansatz EfficientSU2 e il Quantum Approximate Optimization Algorithm (QAOA). Gli ottimizzatori includono COBYLA e Simultaneous Perturbation Stochastic Approximation (SPSA). Viene utilizzato l'obiettivo della Conditional Value at Risk (CVaR) per concentrare l'ottimizzazione sulla coda a bassa energia della distribuzione di misura.

2. Pipeline di Post-elaborazione Classica

Una pipeline euristica a due stadi converte le misurazioni quantistiche grezze in candidati MIS validi:

• Soppressione Guidata dalla Storia: Una Media Mobile Esponenziale (EMA) traccia la frequenza con cui i qubit si trovano nello stato $|0\rangle$ attraverso le bitstring con le migliori prestazioni. Questo genera maschere di soppressione per rimuovere i vertici sovra-selezionati (che violano l'indipendenza) e aggiungere i vertici sotto-selezionati.
• Correzione Greedy e Estensione alla Massimalità: Un algoritmo greedy a due passaggi prima ripara i set non fattibili rimuovendo le violazioni ad alto peso, poi estende il set alla massimalità aggiungendo vertici compatibili in ordine crescente di grado.

3. Inizializzazione di Sovrapposizione Assistita da Ancilla (Istanza a 180 Nodi)

Per l'istanza a 180 nodi, il VQE standard si blocca a dimensione 14 (il MIS noto è 15). Per superare questo, gli autori introducono una nuova tecnica di inizializzazione:

• Selezione dei Semi (Seed Selection): La post-elaborazione classica identifica molteplici e diverse soluzioni indipendenti quasi-ottimali di dimensione 14.
• Sovrapposizione di Ancilla: Invece di inizializzare da un singolo seme o da una sovrapposizione uniforme, il circuito prepara una sovrapposizione quantistica uniforme di questi $m$ distinti set di dimensione 14 usando i qubit ancilla come registro di indice.
• Ansatz che Preserva l'Eccitazione: Lo stato evolve sotto un ansatz composto da gate di simulazione fermionica (fSim) che conservano il peso di Hamming totale (numero di eccitazioni). Ciò restringe la ricerca allo spazio delle configurazioni di dimensione 14, eliminando la necessità di termini di penalità e rendendo più nitido il panorama energetico per l'ottimizzazione fine.
• Ricerca in Parallelo Quantistico: I parametri variazionali sono ottimizzati collettivamente attraverso tutti i rami dei semi simultaneamente. La distribuzione risultante viene poi elaborata dal l'euristica classica, che può estendere i set di dimensione 14 al MIS di dimensione 15.

Risultati Chiave

Istanze Benchmark (64, 99 e 180 Nodi)

• Istanza a 64 Nodi: VQE con SPSA e CVaR recupera con successo tutti i 9 distinti MIS certificati (dimensione 10) attraverso esecuzioni ripetute. QAOA recupera meno set distinti (0–5 per esecuzione) e non riesce a raggiungere la dimensione 10 con la Strategia 2 (spingendo tutti i set recuperati alla massimalità), evidenziando l'importanza della diversità delle soluzioni.
• Istanza a 99 Nodi: VQE recupera fino a 10 MIS distinti (dimensione 7) per esecuzione, campionando una frazione significativa dei 56 soluzioni certificate. Il QAOA non viene perseguito a causa dei limiti di sparsificazione sul simulatore MPS.
• Istanza a 180 Nodi: Il VQE standard (Fase 1) converge a dimensione 14 ma non riesce a raggiungere la dimensione 15. La Fase 3 assistita da ancilla (VQE preservante l'eccitazione) scopre con successo il MIS di dimensione 15. Gli studi di ablazione confermano che le euristiche classiche applicate a singoli semi, o i circuiti preservanti l'eccitazione inizializzati da singoli semi, falliscono nel trovare il MIS di dimensione 15. Solo la sovrapposizione quantistica multi-seme rompe la barriera dell'ottimo locale.

Validazione sull'Hardware (IBM Quantum ibm_marrakesh)

• VQE: Utilizzando parametri trasferiti direttamente dalla simulazione senza rumore (senza ri-ottimizzazione hardware), il VQE recupera circa il 50% della diversità del MIS senza rumore con il 40% del budget di shot. Per l'istanza a 64 nodi, sono stati trovati 3 MIS distinti (dimensione 10); per l'istanza a 99 nodi, 5 MIS distinti (dimensione 7) sono stati trovati.
• QAOA: Sotto lo stesso protocollo di trasferimento dei parametri, il QAOA ha recuperato zero insiemi indipendenti validi sull'hardware. Gli autori attribuiscono ciò all'effetto cumulativo della limitata larghezza di banda del circuito (che richiede lunghe catene di SWAP), l'ottimizzazione classica superficiale e il rumore dell'hardware.

Significato e Rivendicazioni

Il documento rivendica i seguenti contributi e significati:

1. Simulazione su Scala Utility: Per quanto ne sappiano gli autori, la simulazione MPS a 180 qubit rappresenta la scala più grande alla quale algoritmi variazionali basati su gate hanno risolto il problema del MIS all'ottimo.
2. Svolta Metodologica: Il contributo principale è la tecnica di sovrapposizione di ancilla. Essa fornisce un framework principato per rompere gli ottimi locali che intrappolano sia le euristiche classiche che gli approcci variazionali standard. Inizializzando una sovrapposizione quantistica uniforme su più semi quasi-ottimali classici ed evolvendoli sotto un ansatz che preserva l'eccitazione, il metodo esegue una "ricerca parallela ibrida quantistico-classica". Ciò permette la scoperta di soluzioni (dimensione 15) che sono inaccessibili ai metodi a singolo seme.
3. Robustezza al Rumore: La validazione sull'hardware dimostra che la pipeline euristica delle bitstring è robusta alle condizioni di rumore reali, recuperando una diversità di soluzioni significativa senza ri-ottimizzazione consapevole dell'hardware.
4. Rivendicazioni Modeste sul Vantaggio Quantistico: Gli autori dichiarano esplicitamente di non rivendicare un vantaggio computazionale quantistico per queste specifiche istanze. I circuiti studiati sono efficientemente simulabili classicamente tramite MPS (bond dimension $\chi_{max} = 2$) a causa della loro struttura di entanglement a bassa densità. La significatività risiede nel dimostrare che la metodologia funziona e fornisce una base per future implementazioni hardware dove ansätze più profondi e popolazioni di semi più ampie potrebbero generare un vero vantaggio quantistico.

Il lavoro stabilisce che la scoperta del MIS nel caso a 180 nodi è una conseguenza della ricerca in parallelo quantistico su molteplici inizializzazioni quasi-ottimali, piuttosto che della sola post-elaborazione classica. Questo framework è presentato come un approccio scalabile per problemi di ottimizzazione combinatoria che ammettono una formulazione Ising.