Generative Quantum Search for Combinatorial Optimization: Learning Shallow Quantum Samplers for Classically Refined Solution Subspaces

Sintesi Tecnica: Ricerca Quantistica Generativa per l'Ottimizzazione Combinatoria

Enunciato del Problema
Questa ricerca indaga se campionatori quantistici superficiali possano superare i campionatori classici nell'ottimizzazione combinatoria, posizionando una massa di probabilità più elevata all'interno di un "bacino di recupero classico". Lo studio adatta l'architettura Generative Quantum Eigensolver + Quantum-Selected Configuration Interaction (GQE+QSCI), originariamente sviluppata per la chimica quantistica, al dominio dell'ottimizzazione su grafi (specificamente il Maximum Weighted Independent Set, MWIS). L'ipotesi centrale è che un campionatore quantistico possa generare una distribuzione di soluzioni candidate che, quando raffinata da un algoritmo di riparazione e espansione classica, fornisca un tasso di successo superiore rispetto ai campionatori classici.

Metodologia
L'autore propone il framework GQO+QSS (Generative Quantum Optimization + Quantum-Selected Search), che segue una pipeline a quattro fasi:

1. Politica Generativa: Un modello di machine learning (politica condizionata dal grafo) genera programmi di circuiti quantistici (ad esempio, parametri QAOA).
2. Campionamento Quantistico: I circuiti vengono eseguiti su un simulatore o su un QPU (Piast-Q) per produrre bitstring (soluzioni candidate).
3. Recupero Classico: Una funzione di riparazione specifica per il problema corregge le soluzioni non ammissibili, seguita da un'espansione locale (es. vicinato a $r$-flip) per creare un sottospazio di ricerca ristretto.
4. Solver Ristretto: Un solver classico esatto trova la soluzione ottimale all'interno di questo sottospazio ristretto.

Formulazione Teorica Chiave
Il documento formalizza la questione del "vantaggio quantistico" utilizzando la massa del bacino di recupero ($p_r$):
$$p_r(q_\theta, G) = \Pr_{x \sim q_\theta} [x \in A_r(G)]$$
dove $A_r(G)$ è l'insieme degli stati che, dopo la riparazione e l'espansione a $r$-flip, contengono l'ottimo globale. La probabilità di successo con $B$ campionamenti è $P_{success} = 1 - (1 - p_r)^B$. Lo studio postula che la metrica critica non sia la dimensione dello spazio campionato rispetto allo spazio totale ($|S_Q|/2^n$), ma la massa di probabilità $p_r$ che il campionatore colloca nel bacino di recupero.

Protocollo Sperimentale

• Dataset: 150 istanze MWIS con verità fondamentali certificate tramite CBC + verifica brute-force.
• Baseline: Sono stati confrontati nove campionatori, inclusi uniform random, greedy, simulated annealing (SA), tabu search, multi-start local search, Metropolis, warm-start QAOA, oracle QAOA (migliori tra 50 configurazioni) e un modello classico appreso corrispondente.
• Vincoli: Un protocollo preregistrato e congelato con un budget fisso di 200 campionamenti per campionatore.
• Hardware: Gli esperimenti hanno incluso simulazioni ed esecuzione sul processore a ioni intrappolati Piast-Q (20 qubit).

Risultati Chiave

1. Dominanza Classica: La Tabu Search e la Simulated Annealing (SA) hanno superato significativamente tutti i campionatori quantistici e quelli classici appresi in tutte le dimensioni di problema testate ($n=16$ a $n=28$). La Tabu Search ha raggiunto una massa del bacino di recupero ($p_r$) compresa tra 0,822 per $n=16$ e 0,944 per $n=18$, con valori di 0,878 per $n=20$, 0,943 per $n=24$ e 0,901 per $n=28$. La SA è variata tra 0,088 e 0,428 in queste dimensioni.
2. Sottoperformance Quantistica: Tutti i campionatori quantistici (warm-start QAOA, oracle QAOA e politiche generative) sono stati sconfitti sia dalla SA che dalla Tabu Search in ogni dimensione del problema sotto il protocollo equo e preregistrato.
3. L'Artefatto "Oracle": I precedenti risultati positivi che mostravano il QAOA superare la SA sono stati identificati come artefatti della selezione della configurazione per istanza (un limite superiore "oracle"), che non è un metodo implementabile. Quando valutato con configurazioni casuali (un metodo distribuibile), l'oracle QAOA ha raggiunto un $p_r = 0,014$ a $n=28$, ben al di sotto dello 0,088 della SA.
4. Parità del Modello Classico Appreso: Un modello classico appreso (140K parametri) ha ottenuto prestazioni comparabili all'oracle QAOA ($p_r = 0,005–0,101$ vs $0,014–0,113$), indicando che il circuito quantistico non offre alcun vantaggio strutturale rispetto a un modello classico corrispondente in questo contesto.
5. Robustezza dell'Hardware: Gli esperimenti su Piast-Q hanno mostrato una coerenza di recupero del 93,4% tra i campioni QPU e quelli del simulatore, confermando la robustezza dell'hardware ma rivelando nessun vantaggio quantistico nella qualità dell'ottimizzazione.
6. Transizione di Recupero: Lo studio ha mappato una "transizione di recupero" in cui il recupero classico è sufficiente per $n \le 16$, ma inizia a fallire per $n \ge 20$ con l'espansione a 2-flip. Tuttavia, anche in questo regime di transizione, i forti baseline classici (SA, Tabu) hanno mantenuto prestazioni superiori.

Significatività e Rivendicazioni
Il documento si presenta come uno studio di falsificazione. La sua rivendicazione principale è che, sotto una valutazione rigorosa e preregistrata con baseline classiche corrispondenti, le distribuzioni di proposta derivate da QAOA superficiali non superano i modelli di proposta classici corrispondenti per la cattura dei bacini di recupero classici in MWIS.

• Nessun Vantaggio Quantistico: L'autore dichiara esplicitamente l'assenza di vantaggio quantistico per l'architettura GQO+QSS nei regimi testati.
• Confutazione di Precedenti Rivendicazioni: Lo studio attribuisce i precedenti risultati positivi all'effetto "oracle" della selezione della migliore configurazione per istanza, che non è un metodo implementabile.
• Correzione della Metrica: Il documento sostiene che la "frazione di sottospazio" ($|S_Q|/2^n$) è una metrica tautologica sotto budget di campionamento fissi e che la massa del bacino di recupero ($p_r$) è la quantità scientificamente accurata da misurare.
• Direzione Futura: L'autore suggerisce che, affinché il campionamento quantistico fornisca valore, deve costantemente posizionare più massa nel bacino di recupero rispetto ai forti baseline classici (come la SA) nei regimi in cui il recupero classico fallisce ($n \ge 55$), una sfida che i correnti circuiti superficiali non hanno ancora affrontato.

Il lavoro conclude che, sebbene l'architettura GQO+QSS sia un framework valido per l'ottimizzazione ibrida, gli attuali campionatori quantistici superficiali derivati da QAOA non forniscono un vantaggio strutturale rispetto ai forti metodi di ricerca stocastica classica per il compito specifico della cattura del bacino di recupero in MWIS.