Optimized QUBO formulation methods for quantum computing

1. Il Problema

I computer quantistici, in particolare i dispositivi NISQ (Noisy Intermediate-Scale Quantum) come gli annealer quantistici di D-Wave, hanno limitazioni severe in termini di numero di qubit disponibili e connettività. Molti problemi di ottimizzazione combinatoria NP-difficili possono essere risolti su questi dispositivi se riformulati come problemi di Ottimizzazione Binaria Quadratica Senza Vincoli (QUBO).

Tuttavia, la trasformazione di un problema vincolato in un QUBO richiede l'introduzione di variabili di slack (variabili binarie aggiuntive) per codificare i vincoli (uguaglianze e disuguaglianze) sotto forma di termini di penalità quadratici.

• Il collo di bottiglia: I metodi standard per questa riformulazione richiedono un numero elevato di variabili di slack, spesso comparabile o superiore al numero di variabili logiche originali. Questo aumenta drasticamente il numero totale di variabili, rendendo il problema irrisolvibile per i dispositivi NISQ attuali a causa della scarsità di qubit e della necessità di catene lunghe per la mappatura (embedding).
• Obiettivo: Ridurre drasticamente il numero di variabili di slack necessarie per formulare QUBO, permettendo di risolvere istanze più grandi e complesse di problemi di ottimizzazione su hardware quantistico attuale.

2. Metodologia Proposta

Gli autori introducono due nuove tecniche indipendenti ma complementari, denominate Iterative Quadratic Polynomial (IQP) e Master-Satellite (MS).

A. Metodo Iterative Quadratic Polynomial (IQP)

Questo metodo offre un nuovo paradigma per tradurre i vincoli in forme quadratiche di penalità.

• Concetto: Invece di utilizzare la formula standard che richiede variabili di slack per coprire l'intero intervallo di valori possibili di un vincolo, l'IQP cerca di costruire un polinomio quadratico $P(x, s)$ che sia zero quando il vincolo è soddisfatto e $\le -1$ quando è violato.
• Iteratività: Il metodo inizia cercando una soluzione senza variabili di slack. Se non esiste, aggiunge iterativamente una variabile di slack alla volta, aumentando il numero di parametri liberi del polinomio, fino a trovare una soluzione fattibile.
• Vantaggi:
  • Funziona efficacemente per vincoli definiti su un piccolo numero di variabili binarie.
  • Gestisce vincoli non lineari e parametri non interi senza bisogno di approssimazioni.
  • Produce formulazioni sparse (non tutte le variabili sono accoppiate), riducendo la connettività richiesta.

B. Metodo Master-Satellite (MS)

Questa tecnica sfrutta la sinergia tra vincoli che condividono lo stesso insieme di variabili binarie.

• Concetto: I vincoli vengono divisi in Master e Satellite.
  • I vincoli Master sono imposti per tutte le combinazioni possibili delle variabili.
  • I vincoli Satellite sono imposti solo per le combinazioni che soddisfano già i vincoli Master.
• Meccanismo: Poiché i vincoli Satellite non devono essere penalizzati quando i vincoli Master sono violati, il numero di condizioni da soddisfare nel sistema lineare per trovare il polinomio quadratico diminuisce. Questo permette di utilizzare meno variabili di slack.
• Calibrazione: Per evitare che le combinazioni che violano i vincoli Master ricevano "incentivi accidentali" (valori positivi) dai vincoli Satellite, i termini di penalità dei vincoli Master vengono amplificati tramite moltiplicatori relativi ($\lambda_{MC}$) calibrati attentamente.
• Concatenazione: Per tre o più vincoli, è possibile concatenare il metodo (Master $\to$ Satellite $\to$ Satellite...) per ridurre ulteriormente i vincoli secondari.

C. Applicazione al Problema MPBS (Max-Profit Balance Settlement)

Gli autori applicano queste tecniche a un problema NP-difficile ispirato alla finanza: il Max-Profit Balance Settlement.

• Contesto: Un network di utenti con crediti e debiti pendenti. L'obiettivo è massimizzare il valore scambiato selezionando un sottoinsieme di transazioni.
• Vincoli:
  1. CAP/FLOOR: Il saldo netto di ogni utente deve rimanere entro un intervallo predefinito.
  2. IN/OUT: Se un utente partecipa, deve avere almeno un'entrata e un'uscita (o nessuna transazione).
• Implementazione: IN/OUT è trattato come vincolo Master e CAP/FLOOR come Satellite. Questo approccio è ideale perché i problemi finanziari reali tendono ad essere "localmente vincolati" (i vincoli dipendono solo dagli archi incidenti a un nodo).

3. Risultati Chiave

Gli autori hanno testato le loro tecniche su istanze reali di MPBS utilizzando due annealer quantistici D-Wave: Advantage_system4.1 (Adv1) e il prototipo di nuova generazione Advantage2_prototype1.1 (Adv2).

• Riduzione delle Variabili di Slack:

  • Il metodo standard richiede un numero di variabili di slack che cresce con la logaritmo del range dei vincoli (es. per CAP/FLOOR con range $10^5$, servono >15 slack per nodo).
  • Il metodo IQPMS riduce le variabili di slack di circa il 90% rispetto al metodo standard.
  • Per nodi con $\le 4$ archi, il metodo IQPMS richiede zero variabili di slack per i vincoli CAP/FLOOR e IN/OUT.
  • Per nodi con 5 archi, ne richiede solo 1 o 2, indipendentemente dal valore numerico dei vincoli (a differenza del metodo standard).

• Performance su D-Wave:

  • Qualità della Soluzione: L'adozione delle nuove tecniche ha portato a tassi di successo (trovare la soluzione ottima) significativamente più alti.
  • Fattore di Guadagno: Il numero di successi ottenuti con IQPMS rispetto al metodo standard varia da un fattore di 7 (per le istanze più piccole su Adv1) fino a 184 (per le istanze più grandi su Adv2).
  • Scalabilità: Mentre con il metodo standard la qualità della soluzione crolla rapidamente all'aumentare della dimensione dell'input, con IQPMS la qualità rimane stabile e permette di risolvere istanze molto più grandi.
  • Efficienza di Embedding: Il numero medio di qubit necessari per arc (transazione) scende da ~10.5 (metodo standard) a ~2 (metodo IQPMS), rendendo l'embedding molto più efficiente.

4. Contributi Principali

1. Nuovi Algoritmi di Riformulazione: Introduzione dei metodi IQP e MS che cambiano il paradigma di come i vincoli vengono codificati in QUBO, eliminando la necessità di approssimazioni o di risolvere QUBO preliminari.
2. Indipendenza dai Parametri: La riduzione delle variabili di slack ottenuta con IQPMS dipende solo dalla topologia del grafo (numero di archi per nodo) e non dai valori numerici dei vincoli (es. limiti di bilancio), rendendo il metodo robusto per scenari reali con grandi intervalli numerici.
3. Validazione Sperimentale: Dimostrazione pratica su hardware quantistico reale (D-Wave) che una migliore formulazione del problema (meno variabili, più sparsità) si traduce direttamente in una qualità superiore della soluzione e in una maggiore scalabilità.
4. Confronto Hardware: Analisi comparativa tra l'annealer Advantage e il prototipo Advantage2, mostrando come la maggiore connettività e il minor rumore del secondo migliorino ulteriormente i risultati, specialmente quando combinati con formulazioni efficienti.

5. Significato e Implicazioni

Questo lavoro dimostra che il collo di bottiglia principale per l'applicazione dell'ottimizzazione quantistica su problemi reali non è solo la potenza di calcolo grezza, ma l'efficienza della formulazione del problema.

• Impatto Pratico: Permette di risolvere problemi di ottimizzazione finanziaria (e altri problemi localmente vincolati) su hardware NISQ che altrimenti sarebbero irraggiungibili a causa della mancanza di qubit.
• Futuro della Ricerca: Suggerisce che l'ottimizzazione della formulazione QUBO (pre-processing) è un ingrediente chiave per ottenere risultati significativi nell'era quantistica attuale. Le tecniche proposte possono essere estese ad altri problemi combinatori come il Multiple Knapsack o problemi di routing su reti sparse.

In sintesi, gli autori hanno fornito un toolkit matematico che "alleggerisce" i problemi di ottimizzazione, rendendoli compatibili con i limiti fisici degli attuali computer quantistici e massimizzandone le prestazioni.