Accuracy and Performance Evaluation of Quantum, Classical and Hybrid Solvers for the Max-Cut Problem

Sintesi Tecnica: Valutazione dell'accuratezza e delle prestazioni di solver quantistici, classici e ibridi per il problema Max-Cut

Definizione del Problema
Questo studio affronta il problema Max-Cut, che è NP-difficile, e la sua formulazione equivalente, il problema di Ottimizzazione Binaria Quadratica Non Vincolata (QUBO). L'obiettivo è partizionare i vertici di un grafo non orientato pesato in due insiemi disgiunti in modo tale da massimizzare la somma dei pesi degli archi che connettono gli insiemi. Il documento valuta la capacità di vari solver di trovare soluzioni vicine all'ottimo globale, riconoscendo che per istanze di grandi dimensioni le soluzioni esatte sono spesso computazionalmente intrattabili, rendendo necessari approcci euristici approssimati.

Metodologia e Configurazione Sperimentale
Gli autori hanno condotto uno studio di benchmarking completo utilizzando tre dataset distinti composti da 139 istanze di problemi con dimensioni comprese tra 100 e 10.000 nodi.

• Dataset:
  1. Billionnet ed Elloumi (be): 50 istanze con $n \in \{101, 121, 151\}$. Gli ottimi globali sono stati calcolati utilizzando i solver esatti BiqBin e MADAM.
  2. Collezione Beasley (bqp): 20 istanze con $n \in \{251, 501\}$. Gli ottimi per $n=251$ sono stati calcolati esattamente; per $n=501$, sono stati utilizzati i migliori valori noti in letteratura.
  3. Dataset G (G): 69 istanze con $n \in \{800, 1000, 2000, 3000, 5000, 7000, 8000, 9000, 10000\}$. Gli ottimi globali sono sconosciuti; sono stati utilizzati come benchmark i migliori risultati noti dalla letteratura.
• Solver Valutati:
  • Quantum Annealing (QPU): Sistema D-Wave Advantage che utilizza una funzione di "fast annealing" per isolare i qubit dagli effetti ambientali. Limitato a istanze con $n \le 151$.
  • Solver Ibrido: Il "LeapHybridSampler" basato su cloud di D-Wave, che combina iterativamente metodi classici (simulated annealing interrompibile, ricerca tabu, parallel tempering) con chiamate alla QPU. In grado di gestire tutte le dimensioni delle istanze.
  • Simulated Annealing Classico (SA): Sono state implementate due varianti dell'algoritmo da [3]:
    • SA1: Dimensione del passo aggressiva, temperatura iniziale 10.000 (ottimizzato per un tempo di esecuzione comparabile alla QPU).
    • SA2: Dimensione del passo conservativa, temperatura iniziale 40.000 (ottimizzato per la qualità della soluzione).
  • Simulated Bifurcation Machine (SBM): Il solver hardware di Toshiba. I risultati sono stati presi dalla letteratura esistente [4], poiché gli autori non avevano accesso diretto al solver.

Risultati Chiave

• Piccole Istanze ($n \le 151$): Il solver ibrido e entrambe le varianti SA (SA1, SA2) hanno costantemente raggiunto l'ottimo globale per tutte le istanze. La QPU, tuttavia, ha prodotto costantemente soluzioni significativamente lontane dall'ottimo globale.
• Medie Istanze ($n = 251, 501$): Il solver ibrido e le varianti SA hanno nuovamente eguagliato gli ottimi globali (per $n=251$) o i migliori valori noti (per $n=501$). La QPU non poteva essere testata a causa dei limiti di capacità.
• Grandi Istanze ($n \ge 800$):
  • Qualità della Soluzione: L'SBM e SA2 hanno prodotto le soluzioni di qualità più elevata, trovando spesso i migliori valori noti. Il solver ibrido ha performato sensibilmente peggio di SBM e SA2, mentre SA1 ha prodotto le soluzioni di qualità inferiore tra i metodi testati.
  • Tempo Computazionale: Il solver ibrido e l'SBM hanno dimostrato tempi di computazione efficienti (da secondi a decine di secondi). SA2 ha richiesto molto più tempo (centinaia di secondi, circa 1000 volte più lento di Hybrid/SBM in alcuni confronti) per raggiungere una qualità di soluzione superiore. SA1 aveva un tempo di esecuzione comparabile al solver ibrido, ma forniva soluzioni inferiori.

Significatività e Rivendicazioni
Il documento sostiene di far avanzare la comprensione dell'ottimizzazione assistita dal quantum attraverso il test rigoroso del nuovo QPU D-Wave fast annealing e del solver ibrido rispetto a metodi classici allo stato dell'arte su un set standardizzato e pubblicamente disponibile di istanze Max-Cut.

Gli autori concludono che:

1. Limitazioni della QPU: La QPU di D-Wave, anche con il fast annealing, non riesce a trovare soluzioni ottimali per le istanze testate ed è limitata dalla dimensione del problema ($n \le 151$).
2. Efficacia dell'Ibrido: Il solver ibrido di D-Wave è altamente efficiente in termini di velocità e scalabilità (gestendo fino a 10.000 nodi) e produce soluzioni quasi ottimali per istanze più piccole. Tuttavia, per le istanze più grandi, è superato in qualità della soluzione dalla SA classica (specificamente la variante SA2) e dall'SBM.
3. Competitività Classica: Gli algoritmi di simulated annealing trasparenti e classici (specificamente la variante SA2) rimangono altamente competitivi, spesso superando il solver ibrido "black-box" in qualità della soluzione, sebbene a un costo computazionale più elevato.
4. Gap di Trasparenza: Gli autori esprimono frustrazione riguardo alla natura "black-box" del solver ibrido, notando che la mancanza di insight sul suo flusso di lavoro interno e sull'utilizzo delle risorse quantistiche ostacola l'analisi scientifica.

Lo studio non rivendica un vantaggio quantistico per i solver e le istanze di problema testati; piuttosto, evidenzia che per il Max-Cut, gli attuali euristici classici (specialmente se ottimizzati per la qualità) e l'hardware specializzato come l'SBM possono superare o eguagliare le prestazioni degli approcci quantistici e ibridi testati.