Locally Acting Grover Mixers for Constraint-Preserving QAOA

Sintesi Tecnica: Mixer di Grover a Azione Locale per la QAOA con Preservazione dei Vincoli

Enunciato del Problema
L'Algoritmo di Ottimizzazione Quantistica Approssimata (QAOA) e la sua generalizzazione, il Quantum Alternating Operator Ansatz (QAOA), sono algoritmi variazionali prominenti per l'ottimizzazione combinatoria. Una sfida critica nell'applicare questi algoritmi a problemi vincolati è garantire che l'evoluzione quantistica rimanga confinata nel sottospazio ammissibile definito dai vincoli del problema. Il Grover Mixer QAOA (GM-QAOA) affronta questo problema impiegando un operatore di mixing generato dal proiettore sullo stato iniziale, il che garantisce matematicamente la preservazione del sottospazio ammissibile.

Tuttavia, il mixer standard del GM-QAOA richiede un gate di sfasamento multi-controllato globale che agisce su tutti i $n$ qubit. Sui dispositivi quantistici a scala intermedia rumorosi (NISQ) di prossima generazione, che supportano nativamente solo operazioni a uno e due qubit, la decomposizione di tale gate globale in gate elementari risulta in un sostanziale overhead circuitale. La profondità e il numero di gate di tali decomposizioni crescono rapidamente con il numero di qubit, ponendo una barriera significativa all'implementazione pratica e aumentando la suscettibilità al rumore dell'hardware.

Metodologia
Gli autori propongono una variante "a azione locale" del mixer di Grover, adattata per stati iniziali che ammettono una struttura di prodotto su sottosistemi di qubit disgiunti. Questo approccio sfrutta l'osservazione che in molti problemi combinatori, i vincoli possono essere parzialmente codificati nella preparazione dello stato iniziale, lasciando i vincoli rimanenti da gestire tramite termini di penalità nell'Hamiltoniana del costo.

1. Stati Iniziali a Struttura di Prodotto: Il metodo assume che lo stato iniziale $|\psi_0\rangle$ possa essere fattorizzato come $|\psi_0\rangle = |\psi^{(1)}_0\rangle \otimes |\psi^{(2)}_0\rangle \otimes \dots \otimes |\psi^{(\ell)}_0\rangle$, dove ogni $|\psi^{(j)}_0\rangle$ risiede su un sottoinsieme disgiunto di qubit. Questa struttura è ottenuta codificando solo un sottoinsieme dei vincoli del problema durante la preparazione dello stato.
2. Unitaria di Mixing Locale: Invece di un singolo mixer globale $e^{-i\beta |\psi_0\rangle\langle\psi_0|}$, il metodo proposto costruisce l'unitaria di mixing come un prodotto tensoriale di unitarie locali:
   $$U_M(\beta^{(1)}, \dots, \beta^{(\ell)}) = \bigotimes_{j=1}^{\ell} e^{-i\beta^{(j)} |\psi^{(j)}_0\rangle\langle\psi^{(j)}_0|}$$
   Ogni unitaria locale agisce indipendentemente sul proprio rispettivo sottosistema utilizzando un gate di sfasamento multi-controllato confinato a quel sottosistema.
3. Parametrizzazione: L'ansatz introduce parametri variazionali indipendenti $\beta^{(j)}$ per ogni sottosistema. Per un circuito con $p$ layer e $\ell$ sottosistemi, il numero totale di parametri di mixing è $p\ell$, rispetto a $p$ nel GM-QAOA originale. Sebbene ciò aumenti la dimensione del panorama di ottimizzazione classica, sostituisce un massiccio gate globale con $\ell$ gate locali più piccoli.

Contributi Chiave

• Efficienza Circuitale: Il contributo primario è la sostituzione del gate di sfasamento multi-controllato globale con $\ell$ operazioni locali. Ciò riduce drasticamente il numero di gate di entanglement (specificamente i CNOT) e la profondità del circuito richiesti per il passo di mixing.
• Strategia di Codifica dei Vincoli: Il documento investiga il compromesso tra la codifica di tutti i vincoli nello stato iniziale rispetto alla codifica di un solo sottoinsieme. Dimostra che la codifica parziale dei vincoli, che consente la struttura di prodotto richiesta per il mixer locale, può produrre circuiti complessivamente più compatti rispetto alla codifica completa dei vincoli, anche se quest'ultima riduce la dimensione dello spazio di ricerca.
• Preservazione dell'Ammissibilità: Il metodo mantiene il vantaggio principale del GM-QAOA: l'operatore di mixing preserva lo spazio di ricerca definito dallo stato iniziale, garantendo che l'algoritmo non scivoli in regioni non ammissibili.

Risultati
Gli autori hanno valutato il metodo proposto sul problema di Exact-Cover e sul problema del Commesso Viaggiatore (TSP) tramite simulazioni numeriche.

• Problema di Exact-Cover: Per un'istanza a sette qubit, il metodo proposto ha raggiunto un comportamento di convergenza comparabile all'originale GM-QAOA. Fondamentalmente, la decomposizione dell'unitaria di mixing nel set di gate $\{RX, RY, RZ, CNOT\}$ ha ridotto il conteggio dei CNOT da 218 (originale) a 28 (proposto), una riduzione di circa l'87%.
• Problema del Commesso Viaggiatore (TSP): Le simulazioni su istanze TSP a quattro città (nove qubit) hanno mostrato che il metodo proposto mantiene probabilità di soluzione comparabili al GM-QAOA attraverso diversi layer di profondità $p$.
  • Resilienza al Rumore: Sotto un modello di rumore depolarizzante, il metodo proposto ha mostrato un errore relativo significativamente inferiore nel valore di aspettazione dell'Hamiltoniana del costo rispetto all'originale GM-QAOA, grazie alla riduzione della profondità del circuito e del numero di gate.
  • Compromesso sulle Risorse: Sebbene il metodo proposto richieda un maggior numero di esecuzioni del circuito durante l'ottimizzazione classica a causa dell'aumento dei parametri variazionali, la riduzione della complessità del circuito quantistico (il conteggio CNOT è sceso da 572 a 54 per operatore di mixing) lo rende più praticabile per l'hardware rumoroso.
  • Codifica Parziale vs. Completa: Per il TSP, la codifica del solo vincolo temporale ($P_1$) nello stato iniziale (codifica parziale) combinata con il mixer locale ha prodotto una profondità di circuito di 450 alle prestazioni ottimali ($p=7$). Al contrario, la codifica sia del vincolo temporale che del vincolo di visita della città ($P_1$ e $P_2$) nello stato iniziale (codifica completa) ha richiesto un mixer globale e ha portato a una profondità di circuito di 4142 a $p=1$, nonostante raggiungesse più velocemente un'alta probabilità di soluzione. Gli autori concludono che la codifica parziale produce una complessità circuitale complessiva più favorevole.

Significatività e Rivendicazioni
Il documento afferma che i mixer di Grover a azione locale proposti offrono una via pratica per implementare la QAOA con preservazione dei vincoli su dispositivi quantistici a breve termine. Sfruttando la struttura di prodotto dei sottospazi ammissibili, il metodo riduce significativamente il costo di implementazione (numero di gate e profondità) pur preservando la capacità dell'algoritmo di convergere verso soluzioni di alta qualità.

Gli autori notano con modestia che, sebbene l'aumento dei parametri introduca un maggiore overhead di ottimizzazione classica e potenzialmente un panorama di ottimizzazione più complesso, la riduzione della complessità del circuito quantistico è il fattore dominante per i dispositivi NISQ, dove la fedeltà del gate è la limitazione primaria. Il lavoro suggerisce che il compromesso tra numero di parametri e profondità del circuito favorisce l'approccio proposto per l'hardware attuale. Il documento non pretende di risolvere la questione teorica del perché la struttura di mixing rilassata raggiunga una convergenza comparabile, identificando questa come una direzione aperta per la ricerca futura.