Benchmark of Pauli Correlation Encoding for different optimisation problems

Questo articolo valuta un framework di ottimizzazione quantistico-classico utilizzando la codifica della correlazione di Pauli su quattro problemi combinatori, dimostrando le sue prestazioni competitive, la resilienza al rumore e il potenziale come strategia di codifica efficiente per dispositivi NISQ e vicino alla tolleranza ai guasti.

L'essenziale

Immagina di cercare di risolvere un puzzle enorme, ma di avere solo una scatolina minuscola in cui riporre i pezzi. Di solito, se hai 1.000 pezzi di un puzzle, ti serve una scatola abbastanza grande da contenere 1.000 scomparti. Ma cosa succederebbe se potessi magicamente comprimere quei 1.000 pezzi in una scatola che ne contiene solo 10, senza perdere la capacità di risolvere il puzzle?

Questo è essenzialmente ciò di cui tratta questo articolo. I ricercatori stanno testando un nuovo "trucco magico" per i computer quantistici chiamato Pauli Correlation Encoding (PCE).

Ecco una ripartizione del loro lavoro utilizzando analogie semplici:

1. Il Problema: Il limite della "Scatolina"

I computer quantistici sono come potenti nuovi motori, ma al momento sono molto piccoli e rumorosi (come un motore d'auto che sussulta un po'). Hanno un numero limitato di "qubit" (gli scomparti della nostra scatola).

• Il Vecchio Metodo: Per risolvere un problema con 100 variabili (come decidere dove sedersi a una cena), i vecchi metodi quantistici avevano bisogno di 100 qubit. Se avessi 1.000 variabili, avresti bisogno di 1.000 qubit. Poiché gli attuali computer quantistici hanno solo circa 50–100 qubit, non possono risolvere problemi grandi.
• Il Nuovo Trucco (PCE): Il metodo PCE è come un algoritmo di compressione per un file zip. Permette al computer di rappresentare 1.000 variabili usando solo una manciata di qubit (magari 10 o 20). Lo fa osservando come le variabili si "correlano" o danzano insieme, invece di dare a ciascuna un proprio posto dedicato.

2. Il Test: Tre Puzzle Classici

Per vedere se questo trucco di compressione funziona davvero, il team lo ha provato su tre famosi e difficili puzzle provenienti da una libreria standard di test (QOPTLib):

• Il Puzzle del "Posto a Tavola" (Problema del Maximum Cut): Immagina un grafo di persone che si piacciono o si odiano. L'obiettivo è dividere le persone in due gruppi in modo che il maggior numero possibile di "antipatie" avvenga tra i gruppi, non all'interno di essi.
  • Risultato: Il metodo PCE è andato molto bene. Ha trovato soluzioni buone quanto le migliori risposte note, dimostrando di poter gestire questo tipo di problema in modo efficiente.
• Il Puzzle del "Camion Trasloco" (Problema del Bin Packing): Hai un sacco di scatole di diverse dimensioni e un numero limitato di camion. Vuoi far entrare tutte le scatole nel minor numero possibile di camion senza sovraccaricarli.
  • Risultato: Questo è stato complicato. Il metodo ha trovato delle soluzioni, ma ha faticato a far entrare tutto perfettamente nei camion senza violare le regole (come il sovraccarico di un camion). Tuttavia, quando i ricercatori hanno aggiunto una "squadra di pulizia" (un passaggio di post-elaborazione classica) per riorganizzare le scatole dopo che il computer quantistico ha finito, i risultati sono migliorati significamente.
• Il Puzzle del "Commesso Viaggiatore" (TSP): Un commesso deve visitare un elenco di città esattamente una volta e tornare a casa, percorrendo la rotta più breve possibile.
  • Risultato: Simile al puzzle del camion trasloco, il computer quantistico ha trovato una buona rotta, ma non sempre la rotta perfetta. Anche in questo caso, la "squadra di pulizia" (post-elaborazione) ha aiutato a perfezionare il percorso per renderlo molto più breve.

3. Le "Manopole di Regolazione" (Iperparametri)

I ricercatori hanno scoperto che il trucco magico non funziona automaticamente; bisogna sintonizzarlo con cura. Hanno usato due manopole principali:

• La Manopola della "Nitidezza" (Alpha): Immagina di cercare di decidere se una luce è "accesa" o "spenta". Se la manopola è impostata troppo bassa, la luce è solo un bagliore debole e sfocato (una via di mezzo tra acceso e spento). I ricercatori hanno scoperto che alzando molto questa manopola, la luce scatta chiaramente su "acceso" o "spento", portando a soluzioni migliori.
• La Manopola della "Regolarizzazione" (Beta): Questa è un'assistente che cerca di evitare che i numeri diventino troppo selvaggi. Interessante è che hanno scoperto che a volte spegnere questa manopola non ha danneggiato i risultati, il che significa che il sistema è piuttosto robusto.

4. Il Controllo della Realtà "Rumorosa"

I veri computer quantistici non sono perfetti; sono come una radio con l'interferenza. I ricercatori hanno testato cosa succede eseguendo il programma su una macchina rumorosa simulata (mimando l'hardware reale).

• La Scoperta: Di solito, il rumore rovina i calcoli. Tuttavia, hanno scoperto qualcosa di sorprendente: un poquito di rumore ha effettivamente aiutato il computer a uscire dai "vicoli ciechi" (minimi locali). È come scuotere leggermente un labirinto per aiutare una pallina a trovare l'uscita quando rimane bloccata in una piccola buca.
• Il Limite: Tuttavia, se il rumore diventa troppo forte, il segnale si perde. Hanno scoperto che per ottenere una risposta chiara, è necessario eseguire il calcolo molte volte (shot) per mediare l'interferenza.

5. Il Verdetto

L'articolo conclude che questo "trucco di compressione" (PCE) è un modo molto promettente per risolvere grandi problemi di ottimizzazione sui computer quantistici piccoli e rumorosi di oggi.

• Pro: Riduce drasticamente il numero di qubit necessari, permettendoci di affrontare problemi che prima erano troppo grandi per i computer quantistici.
• Contro: Richiede una regolazione attenta delle "manopole" (iperparametri) e spesso necessita di un computer classico per fare una "pulizia finale" della risposta per renderla perfetta.

In breve, i ricercatori hanno dimostrato che, comprimendo il problema, possiamo far entrare enormi puzzle in piccole scatole quantistiche e, con un piccolo aiuto dai computer classici per sistemare i risultati, possiamo ottenere ottime risposte anche su hardware imperfetto.

Sommario tecnico

Sintesi Tecnica: Benchmark della Codifica di Correlazione di Pauli per Diversi Problemi di Ottimizzazione

Definizione del Problema
L'articolo affronta i limiti di scalabilità degli Algoritmi Quantistici Variazionali (VQA) nell'era NISQ (Noisy Intermediate-Scale Quantum). Nello specifico, mira alla scalabilità lineare dei requisiti di qubit negli approcci standard come il Quantum Approximate Optimisation Algorithm (QAOA), dove il numero di qubit cresce linearmente con il numero di variabili binarie classiche. Questo vincolo ostacola l'applicazione dell'ottimizzazione quantistica a problemi combinatori su larga scala. Lo studio investiga la Codifica di Correlazione di Pauli (PCE), uno schema capace di rappresentare $m$ variabili binarie utilizzando un numero polinomiale di qubit $n$ (dove $n \ll m$), per determinarne l'efficacia attraverso diversi problemi di ottimizzazione classica.

Metodologia
Gli autori valutano il framework PCE utilizzando un approccio ibrido quantistico-classico su tre problemi di ottimizzazione combinatoria classica: il Problema del Massimo Taglio (Maximum Cut Problem - MCP), il Problema del Bin Packing (BPP) e il Problema del Commesso Viaggiatore (Travelling Salesman Problem - TSP). La valutazione utilizza istanze del benchmark QOPTLib.

• Schema di Codifica: La PCE codifica le variabili binarie $z_i \in \{-1, 1\}$ come il segno dei valori attesi di specifiche stringhe di Pauli traceless $\Pi_i$. La codifica si basa su un ordine di compressione $k$, dove il numero di variabili scala come $m \approx 3 \binom{n}{k}$.
• Ansatz Variazionale: Lo stato quantistico $|\Psi\rangle$ è preparato utilizzando un circuito quantistico parametrizzato (PQC) a parete di mattoni (brick-wall) hardware-efficient e problem-agnostic. La profondità del circuito scala come $O(m^{1-1/k})$, bilanciando espressività e numero di parametri variazionali.
• Strategia di Ottimizzazione: L'ottimizzazione classica dei parametri del circuito è eseguita tramite Evoluzione Differenziale (DE), un algoritmo evolutivo privo di gradienti scelto per la sua robustezza contro i barren plateaus e i minimi locali.
• Rilassamento e Regolarizzazione: Per facilitare l'ottimizzazione, la funzione segno discreta viene rilassata utilizzando una funzione tangente iperbolica $z_i = \tanh(\alpha \langle \Pi_i \rangle)$, controllata dall'iperparametro $\alpha$. Viene incluso un termine di regolarizzazione pesato da $\beta$ per concentrare i valori attesi attorno allo zero.
• Formulazione delle Penalità: Per i problemi con vincoli (BPP e TSP), i vincoli sono incorporati nella funzione di costo tramite termini di penalità con pesi $\lambda_1, \lambda_2, \lambda_3$. Lo studio esplora il problema "Big-M" della selezione dei pesi delle penalità appropriati per garantire la fattibilità senza distorcere il panorama dell'ottimizzazione.
• Post-Processing: Un passaggio di post-processing classico viene applicato a tutti i risultati. Per MCP, vengono utilizzati scambi di bit-flip; per BPP, riassegnazioni di singoli oggetti nei bin; e per TSP, viene impiegata un'euristica 2-opt per raffinare i tour ricostruiti.
• Analisi del Rumore: Lo studio include esecuzioni basate su shot utilizzando l'emulatore CUNQA (che imita l'hardware IBM Sherbrooke) per analizzare l'impatto del rumore di shot e degli errori di gate sulla stima del valore atteso e sulla dinamica di ottimizzazione.

Contributi Chiave e Risultati
L'articolo confronta il framework PCE con le soluzioni di riferimento QOPTLib e i solver ibridi D-WAVE.

1. Prestazioni tra i Problemi:

   • Massimo Taglio (MCP): Il framework PCE raggiunge prestazioni competitive, spesso toccando la soglia di durezza teorica ($16/17$) e trovando soluzioni equivalenti o migliori del benchmark. Ordini di compressione più elevati ($k$) producono generalmente una migliore qualità della soluzione grazie alla maggiore profondità del circuito e all'espressività, nonostante il maggior costo computazionale.
   • Bin Packing (BPP): Il metodo dimostra un forte potenziale, in particolare per istanze piccole. Tuttavia, la fattibilità è altamente sensibile all'ordine di compressione e agli iperparametri. Mentre $k=4$ poteva produrre soluzioni fattibili per tutte le istanze testate, ordini inferiori hanno fallito per $N$ più grandi. Il post-processing ha migliorato significativamente il numero di bin utilizzati, recuperando spesso imballaggi quasi ottimali.
   • Commesso Viaggiatore (TSP): Similmente al BPP, l'approccio produce soluzioni iniziali competitive. Per $k \in \{3, 4\}$, l'algoritmo spesso eguaglia o supera le soluzioni di benchmark. Il post-processing con 2-opt riduce costantemente la lunghezza del tour. I tassi di fattibilità scendono per istanze più grandi con $k$ inferiore, evidenziando il compromesso tra compressione e capacità di soddisfare vincoli stretti.

2. Sensibilità agli Iperparametri:

   • L'iperparametro $\alpha$ (che controlla la nitidezza della binarizzazione) è critico. Valori più elevati migliorano generalmente la qualità della soluzione evitando che le variabili rimangano nel regime lineare della funzione $\tanh$ (vicino a 0.5), il che causerebbe ambiguità nella ricostruzione.
   • Il parametro di regolarizzazione $\beta$ ha mostrato un impatto minore in questo studio rispetto alla proposta originale; impostare $\beta=0$ ha spesso prodotto risultati comparabili a valori non nulli, probabilmente a causa dei pesi delle penalità utilizzati.
   • I pesi delle penalità ($\lambda$) richiedono una calibrazione attenta. Pesi eccessivamente grandi non hanno garantito una migliore binarizzazione e hanno potuto portare a una soddisfazione dei vincoli "morbida", dove le variabili assumono valori frazionari.

3. Effetti di Rumore e Shot:

   • Nelle simulazioni ideali, aumentare il numero di shot riduce l'errore di convergenza a $\sim 10^{-3}$.
   • Nelle simulazioni rumorose (backend IBM Sherbrooke), il rumore dell'hardware domina, limitando l'Errore Assoluto Medio (MAE) a circa 0.025 indipendentemente dal numero di shot.
   • Paradossalmente, la presenza di rumore nel processo di ottimizzazione iterativa (con 1000 shot) ha talvolta aiutato l'algoritmo DE a sfuggire ai minimi locali, portando a rapporti di soluzione migliori rispetto alle esecuzioni ideali prive di rumore in casi specifici.

Significato e Rivendicazioni
L'articolo sostiene che la Codifica di Correlazione di Pauli rappresenti una strategia promettente per l'ottimizzazione quantistica nell'era NISQ e in quella vicino al fault-tolerant. Il suo significato primario risiede nella capacità di ridurre drasticamente i requisiti di qubit, consentendo il trattamento di problemi combinatori su larga scala con un numero relativamente piccolo di qubit.

Gli autori concludono che, sebbene il framework basato su PCE sia in grado di ottenere soluzioni competitive, e in alcuni casi superiori, rispetto ai benchmark classici e ai solver quantistico-classici ibridi, il suo successo dipende fortemente da:

1. Riformulazione specifica del problema: Adattare correttamente le funzioni di costo e i pesi delle penalità.
2. Calibrazione degli iperparametri: In particolare la calibrazione di $\alpha$ e dell'ordine di compressione $k$.
3. Post-processing: La necessità di passaggi di raffinamento classico per recuperare soluzioni discrete di alta qualità dalla l'output quantistico rilassato.

Il lavoro evidenzia che, sebbene la PCE offra una codifica scalabile, il problema "Big-M" della selezione delle penalità e il compromesso tra espressività del circuito (profondità) e addestrabilità rimangono sfide critiche. Lo studio stabilisce un riferimento pratico per i tempi di esecuzione e i limiti di errore, suggerendo che con gli ottimizzatori classici appropriati e la parallelizzazione, l'approccio è percorribile per il futuro hardware quantistico, fungendo al contempo da potente algoritmo classico di ispirazione quantistica.