Resource-Efficient Quantum Optimization via Higher-Order Encoding

Sintesi Tecnica: Ottimizzazione Quantistica Efficiente nelle Risorse tramite Codifica di Ordine Superiore

Definizione del Problema
I problemi di ottimizzazione combinatoria (COP) sono centrali in campi che spaziano dalla logistica alla biologia computazionale, ma sono spesso NP-hard, il che li rende computazionalmente intrattabili per i solver classici all'aumentare delle dimensioni del problema. Gli algoritmi quantistici, in particolare il Quantum Approximate Optimization Algorithm (QAOA), offrono un potenziale percorso per affrontare queste sfide. Tuttavia, gli attuali approcci quantistici sono frequentemente limitati dalle richieste di risorse delle formulazioni Quadratic Unconstrained Binary Optimization (QUBO). Le codifiche QUBO standard, come la codifica One-Hot, richiedono un numero di qubit lineare sia nel numero di variabili ($n$) che nel numero di valori possibili per variabile ($m$), risultando in $n \times m$ qubit. Inoltre, l'imposizione di vincoli in QUBO richiede tipicamente termini di penalità elevati, che aumentano la profondità del circuito e il conteggio dei gate CNOT a due qubit, rendendo molti problemi pratici inaccessibili sull'attuale hardware quantistico a breve termine.

Metodologia
Gli autori propongono un framework sistematico che utilizza la Higher-Order Unconstrained Binary Optimization (HUBO) per mitigare questi vincoli di risorse. La metodologia prevede tre componenti primarie:

1. Codifica Binaria vs. Codifica One-Hot: Invece di utilizzare la codifica One-Hot (dove ogni coppia variabile-valore è un qubit distinto), gli autori impiegano una codifica Binaria. In questo caso, ogni variabile $i$ è rappresentata da un registro binario compatto di $d = \lceil \log_2(m) \rceil$ bit. Ciò riduce il requisito di qubit da $n \times m$ a $n \times \lceil \log_2(m) \rceil$.
2. Costruzione dell'Hamiltoniana HUBO: Gli autori dimostrano che questa codifica binaria porta naturalmente a Hamiltoniane HUBO contenenti termini di interazione di ordine superiore (fino all'ordine $2 \times d$). A differenza di QUBO, che richiede termini di penalità per imporre il vincolo "one-hot" (ovvero che una variabile assuma un solo valore), la codifica binaria rispetta intrinsecamente l'assegnazione di valore singolo. I vincoli (ad esempio, $s_i \neq s_j$) sono incorporati direttamente nell'Hamiltoniana o tramite termini di penalità che non richiedono l'espansione dello spazio delle variabili.
3. Compilazione del Circuito: Sebbene i termini di ordine superiore implichino formalmente interazioni multi-qubit, gli autori mostrano che questi possono essere compilati interamente in gate standard a singolo e doppio qubit. Utilizzano una sintesi di circuito basata su Gray-code (seguendo Welch et al.) per implementare l'operatore di costo $e^{-i\gamma \hat{H}_C}$. Questo approccio minimizza le operazioni ridondanti sfruttando gli stati di parità generati per un termine per assistere la costruzione di altri, garantendo che il conteggio asintotico dei gate CNOT scali come $O(n^2 m^2)$, comparabile a QUBO ma con fattori costanti significativamente inferiori nella pratica.

Gli autori introducono inoltre PyHUBO, una libreria Python open-source che automatizza la costruzione di Hamiltoniane HUBO e il calcolo dei loro coefficienti utilizzando trasformate di Walsh-Hadamard, garantendo che la complessità numerica scali polinomialmente con la dimensione del problema.

Contributi Chiave

• Framework Sistematico: Un metodo generale per mappare i COP in Hamiltoniane HUBO utilizzando codifiche binarie, applicabile a problemi con vincoli one-hot o correlati.
• Riduzione delle Risorse: Una dimostrazione che le formulazioni HUBO riducono significativamente il numero di qubit e, crucialmente, il numero totale di gate CNOT richiesti per l'esecuzione di QAOA rispetto a QUBO.
• Strumento Software: Il rilascio di PyHUBO per facilitare l'adozione di modelli HUBO nella comunità quantistica.
• Benchmarking: Valutazione completa attraverso tre distinte classi di COP: Gate Assignment Problem (GAP), Maximum k-Colorable Subgraph (MkCS) e Programmazione Intera (IP).

Risultati
Gli autori hanno testato il QAOA utilizzando sia le codifiche QUBO che HUBO sulle tre classi di problemi selezionate. I risultati indicano un risparmio sostanziale di risorse per HUBO:

• Efficienza dei Qubit: HUBO riduce i requisiti di qubit da $O(nm)$a$O(n \log m)$.
• Riduzione del Conteggio dei Gate: Per tutte le istanze testate, HUBO ha ridotto il conteggio totale dei gate CNOT di almeno l'89,6%. In casi specifici, come nei benchmark di Programmazione Intera, le riduzioni hanno raggiunto il 97,1%.
• Qualità della Soluzione: Per un numero fisso di layer QAOA, l'approccio HUBO-QAOA ha costantemente ottenuto rapporti di approssimazione migliori (più vicini alla soluzione ottimale) rispetto a QUBO-QAOA. Ad esempio, nel benchmark GAP, HUBO ha ottenuto un valore obiettivo medio di 12,1 minuti rispetto ai 15,8 minuti di QUBO.
• Convergenza: HUBO-QAOA ha raggiunto i rapporti di approssimazione target con significativamente meno gate totali. Nel benchmark IP, HUBO ha raggiunto un rapporto target di 0,60 con 1 layer, mentre QUBO ne ha richiesti 10, risultando in un consumo di gate CNOT 31,6 volte superiore e di gate RZ 24,5 volte superiore per QUBO.
• Scalabilità: Il vantaggio di risorse di HUBO è persistito e spesso è aumentato all'aumentare delle dimensioni dei problemi, con HUBO che rimane trattabile per dimensioni di problemi in cui QUोDA-QAOA diventava computazionalmente impraticabile a causa degli eccessivi requisiti di risorse.

Significatività
L'articolo sostiene che le formulazioni HUBO offrono un'alternativa pratica per l'ottimizzazione quantistica su dispositivi a breve termine. Contrariamente all'intuizione che le interazioni di ordine superiore aumenterebbero la richiesta di hardware, gli autori dimostrano che l'eliminazione dei termini di penalità e la compressione della rappresentazione delle variabili portano a una riduzione netta della complessità del circuito. Riducendo significativamente i requisiti di qubit e CNOT, la codifica HUBO aiuta a mitigare i colli di bottiglia delle risorse che attualmente limitano l'applicazione degli algoritmi quantistici a problemi industriali reali. Gli autori concludono che questi metodi efficienti nelle risorse sono sempre più vitali man mano che la tecnologia quantistica avanza e le dimensioni dei problemi aumentano, abilitando applicazioni più fattibili nell'industria e nella ricerca.