A competitive NISQ and qubit-efficient solver for the LABS problem

Riepilogo Tecnico: Un Solutore Competitivo per il Problema LABS, Adatto al NISQ e Efficiente nei Qubit

Definizione del Problema
Il problema delle Sequenze Binarie a Bassa Autocorrelazione (LABS) è una nota sfida di ottimizzazione combinatoria NP-difficile con applicazioni nell'ingegneria, nelle comunicazioni e nella fisica statistica. Dato un intero $N$, l'obiettivo è trovare una sequenza binaria $x \in \{-1, +1\}^N$ che minimizzi l'energia dei lobi secondari $E(x)$, definita come la somma dei quadrati delle autocorrelazioni $C_\ell(x)$ per $\ell > 0$. Equivalentemente, l'obiettivo è massimizzare il fattore di merito $F(x) = N^2 / 2E(x)$. Il problema è caratterizzato da un panorama di ottimizzazione di tipo "campo di golf" (golf course) con numerosi minimi locali ed isolati minimi globali. Sebbene siano note soluzioni esatte per $N \le 66$, trovare soluzioni ottimali o di alta qualità per $N$ più grandi diventa intrattabile per i metodi classici di forza bruta, e anche gli euristici allo stato dell'arte come il Memetic Tabu Search affrontano significative sfide di scalabilità.

Metodologia: Pauli Correlation Encoding (PCE)
Gli autori propongono un solutore quantistico variazionale basato sul framework di Pauli Correlation Encoding (PCE) che è efficiente nei qubit. A differenza delle codifiche standard che richiedono un qubit per ogni variabile binaria, il PCE comprime $N$ variabili binarie in $n$ qubit dove $N = \text{poly}(n)$, specificamente $n \ll N$.

• Codifica: Le variabili binarie $x_i$ sono codificate come i segni dei valori di aspettazione di un insieme di stringhe di Pauli a $n$ qubit $\Pi = \{\Pi_i\}_{i \in [N]}$:
  $$x_i := \text{sgn}(\langle \Pi_i \rangle)$$
  dove $\langle \Pi_i \rangle = \langle \Psi | \Pi_i | \Psi \rangle$.
• Ottimizzazione: Lo stato quantistico $|\Psi\rangle$ è generato da un circuito a mattoni (brickwork circuit) parametrizzato. I parametri sono ottimizzati classicamente per minimizzare una funzione di perdita non lineare $L$. Per facilitare l'ottimizzazione basata sul gradiente, le variabili binarie vengono rilassate utilizzando una funzione tangente iperbolica: $\tilde{x}_i = \tanh(\alpha \langle \Pi_i \rangle)$. La funzione di perdita include un termine di regolarizzazione per evitare che i correlatori svaniscano.
• Selezione dell'Insieme di Pauli: Lo studio valuta due distinti insiemi per $\Pi$:
  1. $\Pi(C)$: Un insieme di operatori di Pauli scelti casualmente e mutuamente commutanti.
  2. $\Pi(NC)$: Un insieme progettato per massimizzare il numero di operatori di Pauli mutuamente non commutanti. Gli autori ipotizzano che la non-commutatività porti a misurazioni mutuamente unbiased, aumentando così l'espressività e l'indipendenza delle variabili codificate.

Contributi Chiave e Risultati

1. Simulazioni Numeriche ($N \le 45$):

   • Gli autori hanno simulato il solutore PCE utilizzando $n=4$ qubit e un circuito con profondità di 15 layer (30 porte a due qubit, 150 parametri).
   • La variante $\Pi(NC)$ ha superato costantemente la variante commutante.
   • Analisi della Scalabilità: Il Time-to-Solution (TTS), definito come il numero di valutazioni della funzione di costo necessarie per trovare la soluzione esatta, è stato confrontato con QAOA e Memetic Tabu Search.
     • Scalabilità PCE: $O(1.330^N)$ per istanze pari e $O(1.326^N)$ per istanze dispari.
     • Confronto: Questa scalabilità migliora quella di QAOA di $O(1.46^N)$ ed è marginalmente migliore della scalabilità dello stato dell'arte del Tabu Search, ovvero $O(1.34^N)$ (per istanze pari) e $O(1.409^N)$ (per istanze dispari).
   • I risultati indicano un vantaggio di legge di potenza per il PCE rispetto ai baseline classici all'interno dell'intervallo testato.

2. Dimostrazione Sperimentale (IonQ Forte):

   • Gli autori hanno eseguito una dimostrazione di prova di concetto su un processore quantistico IonQ Forte per una dimensione dell'istanza $N=120$, la più grande dimostrata finora su hardware quantistico.
   • Per l'esperimento, è stato utilizzato un insieme specifico di correlatori a $k$-corpi (con $k=2$) compatibili con l'hardware, richiedendo solo tre setup di misurazione.
   • Resilienza al Rumore: Lo studio ha rilevato che, sebbene il rumore di campionamento (shot noise) abbia avuto un impatto minore (richiedendo solo poche migliaia di shot), il rumore dell'hardware ha degradato significativamente la qualità della soluzione finale. Tuttavia, il processo di addestramento stesso è rimasto robusto, suggerendo che la mitigazione dell'errore o tassi di compressione più elevati siano critici per l'implementazione nel near-term.

Significatività e Rivendicazioni
Il documento sostiene che i solutori basati su PCE rappresentino una via promettente per due direzioni distinte:

1. Euristici Classici Ispirati al Quantum: Anche quando simulati classicamente, il framework PCE offre una scalabilità competitiva o superiore rispetto ai principali euristici classici per problemi difficili come LABS, agendo come un potente algoritmo quantum-inspired.
2. Riduzione delle Risorse NISQ: Codificando $N$ variabili in un numero di qubit polinomialmente minore ($n$), il PCE riduce drasticamente i requisiti di qubit per i dispositivi attuali. Gli autori notano che $n=8$ qubit potrebbero teoricamente affrontare istanze fino a $N=66$ (dove le soluzioni esatte sono note), e $n \le 20$ potrebbe sfidare le più grandi istanze risolvibili dagli euristici classici.

Gli autori mantengono una posizione modesta riguardo al "vantaggio quantistico". Riconoscono che l'overhead di simulare i full quantum state vector in benchmark classici ritarda il punto di incrocio in cui un vero vantaggio di runtime quantistico diventa evidente. Inoltre, osservano che, sebbene il metodo mostri prestazioni solide, attualmente manca di garanzie sulle prestazioni. Tuttavia, la capacità di risolvere istanze $N=120$ sull'hardware attuale con budget di shot modesti e l'osservazione della resilienza al rumore evidenziano il potenziale del PCE come strumento per ridurre i requisiti di risorse negli algoritmi quantistici reali.