Geometry-Informed Polynomial Time Quantum Approximation Schemes for Constrained Optimisation

Sintesi Tecnica: Schemi di Approssimazione Quantistica in Tempo Polinomiale Informati dalla Geometria per l'Ottimizzazione Vincolata

Enunciato del Problema
L'ottimizzazione combinatoria vincolata consiste nel trovare configurazioni ottimali soggette a vincoli rigidi (ad esempio, assegnazione, matching, routing). Sebbene esistano algoritmi classici per sottoclassi specifiche e trattabili, molti di tali problemi sono NP-hard. Gli approcci quantistici, in particolare il Quantum Approximation Optimization Algorithm (QAOA), affrontano sfide nei dispositivi a breve termine (near-term):

1. Fattibilità: Il QAOA standard spesso campiona al di fuori dello spazio sottostante fattibile definito dai vincoli rigidi.
2. Rumore: Il rumore del dispositivo induce violazioni dei vincoli, degradando la qualità dei campioni.
3. Garanzie: I metodi esistenti spesso mancano di garanzie rigorose end-to-end sulle prestazioni (tempo di esecuzione polinomiale con alta probabilità di trovare un ottimo) sotto condizioni di rumore realistiche.

Il documento affronta la domanda: Quando un campionatore quantistico rumoroso consente un algoritmo end-to-end in tempo polinomiale con garanzie di prestazione?

Metodologia
Gli autori propongono l'algoritmo Noisy Polytime Hybrid Quantum-Classical (NP-HQ), una pipeline completa che integra il campionamento quantistico con il post-processing deterministico classico. La metodologia si basa su tre pilastri:

1. Il Kernel OFM e il CE-QAOA:
   L'approccio utilizza il kernel Onah–Firt–Michielsen (OFM), che definisce una codifica specifica per problemi come il Problema del Commesso Viaggiatore (TSP) e il Problema dell'Assegnazione Quadratica (QAP).

   • Codifica: Utilizza una codifica one-hot in cui ogni blocco logico ha esattamente un'eccitazione.
   • Dinamica: Impiega il Constraint-Enhanced QAOA (CE-QAOA) con un mixer XY blocco-locale che preserva lo spazio sottostante one-hot.
   • Garanzie: Basandosi sul lavoro precedente [1], viene dimostrato che l'ideale campionatore CE-QAOA assegna una massa di probabilità inversamente polinomiale ($p_0 = \Omega(n^{-k})$) all'insieme delle soluzioni ottime, a condizione che siano soddisfatte specifiche condizioni geometriche (separazione di fase).

2. Riparazione Deterministica e Scoring:
   Per gestire rumore e campioni infattibili, la pipeline include un post-elaboratore classico:

   • Controllo di Fattibilità: Verifica i vincoli one-hot.
   • Riparazione: Utilizza algoritmi deterministici in tempo polinomiale (specificamente l'algoritmo ungherese per i problemi di assegnazione o euristiche basate su scambi) per proiettare le stringhe di bit rumorose e infattibili verso la soluzione fattibile più vicina (ad esempio, una permutazione valida).
   • Scoring: Valuta la funzione obiettivo esatta sui candidati riparati.
   • Base Teorica: La mappa di riparazione è dimostrata essere una contrazione nella distanza di variazione totale e non diminuisce la massa di probabilità dell'insieme ottimale.

3. Analisi della Robustezza al Rumore:
   Gli autori derivano un limite di tipo Lipschitz che mette in relazione il rumore del dispositivo con la degradazione della massa di campionamento ottimale. Stabiliscono una "finestra di rumore" in cui, se l'errore effettivo per layer è sufficientemente basso, la massa ottimale rumorosa rimane inversamente polinomiale. Ciò consente il calcolo di un budget di shot polinomiale richiesto per recuperare un ottimo con alta probabilità.

Contributi Chiave

1. FPRAS$_q$ (Exact-Hit):
   Nel regime a basso rumore in cui l'ideale campionatore assegna una massa inversamente polinomiale all'ottimo, la pipeline NP-HQ costituisce uno Schema di Approssimazione Casuale Completamente Polinomiale (FPRAS$_q$). Garantisce di trovare il ottimo globale con probabilità $1-\delta$ in tempo polinomiale (chiamate di circuiti quantistici + post-processing classico).

2. $\varepsilon$-PTQAS (Approssimazione):
   Oltre il regime di "exact-hit", la pipeline fornisce uno Schema di Approssimazione Quantistica in Tempo Polinomiale $\varepsilon$ ($\varepsilon$-PTQAS). Se l'inflazione dell'obiettivo indotta dalla riparazione è controllata, l'algoritmo produce un'approssimazione $(1+\varepsilon)$ con runtime polinomiale.

3. Separazione Quantistica-Classica:
   Il documento stabilisce una separazione condizionale tra la pipeline NP-HQ e le strategie puramente classiche. Anche se a un campionatore classico venissero concessi:

   • L'accesso alle stesse mappe di riparazione efficienti (proiezione ungherese).
   • L'accesso perfetto alle strutture dei vincoli (ad esempio, campionare uniformemente da stringhe row-one-hot).
   • Tempo polinomiale.
     Non può riprodurre la sovrapposizione ottimale inversamente polinomiale su famiglie ammissibili al kernel NP, a meno che NP $\not\subseteq$ BPP. Il vantaggio quantistico risiede strettamente nella generazione della distribuzione di campionamento, non nell'elaborazione classica.

4. Heavy-Hitter QAOA (HH-QAOA):
   Un raffinamento che riduce i costi di post-elaborazione classica. Sfruttando la geometria della distribuzione quantistica, l'algoritmo identifica i "heavy hitters" (campioni ad alta frequenza) e filtra l'insieme dei candidati. Ciò riduce la complessità del post-processing classico da $O(n^{k+4})$ a $O(n^{k+3})$ (o inferiore con ulteriore compressione) senza sacrificare le garanzie di approssimazione.

5. Dimostrazione Hardware:
   L'intera pipeline è stata eseguita su due distinti processori IBM Eagle-r3 da 127 qubit (ibm_brisbane e ibm_sherbrooke) utilizzando istanze QOptlib TSP con fino a 100 variabili logiche.

   • Risultati: Nonostante il forte rumore (tassi di errore a due qubit $\sim 10^{-3}$ a $10^{-2}$), la riparazione deterministica ha ripristinato la fattibilità per tutti i campioni.
   • Performance: Le soluzioni riparate hanno pareggiato o migliorato i tour di riferimento pubblicati in ogni caso testato, dimostrando la fattibilità dell'approccio sull'hardware attuale.

Significato e Rivendicazioni
Il documento sostiene di fornire la prima garanzia di ottimizzazione end-to-end per una pipeline ibrida quantistico-classica sotto rumore di dispositivo che combina:

• Recupero dell'ottimo a shot finiti.
• Ripristino deterministico della fattibilità.
• Espliciti limiti inferiori di rumore finito sulla massa ottimale recuperata.
• Complessità di shot polinomiale e runtime di post-processing polinomiale.

Gli autori sostengono che l'ottimizzazione quantistica vincolata debba essere vista come una pipeline unificata in cui la struttura del problema viene sfruttata sia nella dinamica quantistica (tramite il kernel OFM) che nell'elaborazione classica (tramite mappe di riparazione). Il lavoro dimostra che anche nell'era NISQ, circuiti vincolati poco profondi combinati con un rigoroso post-processing classico possono produrre schemi di approssimazione provabili e risultati competitivi su hardware reale.

Limitazioni e Ambito

• Le garanzie sono dipendenti dall'istanza, basandosi sull'esistenza di una separazione di fase positiva ($\delta > 0$) e di un peso dell'inviluppo del mixer sufficiente.
• La garanzia di "exact-hit" è valida solo entro una specifica finestra di rumore; al di fuori di essa, lo schema degrada in uno schema di approssimazione.
• La separazione quantistica-classica è condizionata all'assunzione che NP $\not\subseteq$ BPP.
• Gli esperimenti hardware hanno utilizzato parametri di warm-start fissi da una ottimizzazione QAOA generica piuttosto che una ri-ottimizzazione nativa dell'hardware, testando la trasferibilità dei parametri a dispositivi rumorosi.