Cross-Platform Benchmarking of Near-Term Quantum Optimisation Algorithms

Questo studio presenta un framework di benchmarking applicativo per algoritmi di ottimizzazione quantistica near-term, confrontando l'efficacia di VQE e Quantum Annealing su dispositivi commerciali rispetto ad algoritmi classici per problemi QUBO densi fino a 72 variabili, identificando limiti imposti dalla connettività, dal rumore e dagli oneri computazionali classici.

L'essenziale

🧠 La Grande Gara dei Computer: Chi Risolve il Puzzle Meglio?

Immagina di avere un enorme puzzle con migliaia di pezzi. Il tuo obiettivo è trovare la disposizione perfetta di questi pezzi che crea l'immagine più bella (o, nel linguaggio dei computer, la soluzione con l'energia più bassa). Questo tipo di problema si chiama "ottimizzazione combinatoria" ed è ovunque: dalla logistica dei camion alla progettazione di nuovi farmaci.

Gli scienziati di questo studio hanno organizzato una gara per vedere chi risolve questo puzzle meglio:

1. I Computer Classici (quelli che usiamo ogni giorno).
2. I Computer Quantistici Gate-based (come quelli di IBM, che usano "interruttori" quantistici).
3. I Computer Quantistici ad Annealing (come quelli di D-Wave, che usano un processo simile al raffreddamento lento dei metalli).

Ecco come è andata la gara, spiegata con metafore semplici.

---

1. Il Problema: "Il Grafene con i Buchi" 🕳️

Per fare la gara, gli scienziati hanno scelto un problema specifico: immagina un foglio di grafene (un materiale super forte fatto di atomi di carbonio disposti a nido d'ape).
La sfida: Devi togliere esattamente 3 atomi da questo foglio. Ma non puoi toglierli a caso! Devi toglierli in modo che il foglio rimanga il più "integro" possibile (cioè, che rimanga il maggior numero di legami tra gli atomi rimanenti).

È come se avessi una griglia di luci accese e dovessi spegnerne esattamente 3, ma devi farlo in modo che le luci rimaste siano il più vicine possibile tra loro per formare un gruppo compatto. Più il gruppo è compatto, più la soluzione è "buona".

2. I Partecipanti alla Gara 🏁

🏃‍♂️ Il Corridore Classico: "Simulated Annealing" (Ricottura Simulata)

Immagina un esploratore che cammina su una montagna piena di buchi (i picchi sono le soluzioni buone, le valli sono quelle cattive).

• Come funziona: All'inizio l'esploratore è molto "caldo" (energico) e salta ovunque, anche su buchi profondi. Man mano che si raffredda, inizia a fare passi più piccoli e cerca di stare in cima alle colline.
• Risultato: È stato il vincitore assoluto. È stato veloce, preciso e ha risolto problemi enormi (fino a 338 atomi) in pochi secondi. È come un esperto che conosce la mappa e trova la strada migliore rapidamente.

🤖 Il Robot Quantistico Gate-based (VQE - IBM)

Questo è un computer quantistico che funziona come un orchestra che prova a suonare una canzone.

• Come funziona: Il computer prova una melodia (una soluzione), ascolta quanto è stonata, e chiede al direttore d'orchestra (un computer classico) di correggere gli strumenti. Ripete questo processo migliaia di volte finché la musica non è perfetta.
• Il problema: È molto lento e si stanca facilmente. Se l'orchestra è troppo grande (problemi complessi), i musicisti si confondono a causa del "rumore" (disturbi quantistici).
• Risultato: Ha risolto problemi piccoli (18 atomi) bene, ma quando il puzzle è diventato grande (72 atomi), il computer ha impiegato ore e non ha trovato la soluzione perfetta. È come un genio che però si distrae facilmente se il compito è troppo lungo.

❄️ Il Robot Quantistico ad Annealing (D-Wave)

Questo computer funziona come un metallo che viene raffreddato lentamente.

• Come funziona: Immagina di avere un blocco di metallo pieno di imperfezioni. Se lo raffreddi molto lentamente, gli atomi si sistemano nella posizione più stabile possibile. Il computer fa lo stesso: cerca la configurazione più stabile "raffreddando" il problema.
• Il problema: Il computer ha una "mappa" interna rigida. Se il puzzle richiede di collegare pezzi che non sono vicini nella mappa, il computer deve usare "ponti" (catene di qubit) per collegarli. Costruire questi ponti richiede tempo e risorse.
• Risultato: È stato veloce nel trovare soluzioni decenti per problemi medi (fino a 72 atomi), ma ha faticato molto a preparare la mappa (embedding) prima di iniziare. È come un corridore velocissimo, ma che perde molto tempo a legarsi le scarpe prima della gara.

---

3. Le Scoperte Chiave (Cosa abbiamo imparato?) 📝

Ecco i "segreti" emersi dalla gara:

• La trappola delle regole: Nel puzzle, c'era una regola ferrea: "Togli esattamente 3 atomi". Se il computer ne toglieva 2 o 4, la soluzione era sbagliata.

  • La scoperta: I computer quantistici funzionavano meglio se usavamo una "penalità" (una multa) piccola per chi sbagliava il numero di atomi. Sembra controintuitivo, ma è come dire: "Se sbagli, ti do una multa leggera". Questo permetteva al computer di esplorare più soluzioni velocemente. Poi, alla fine, gli scienziati usavano un "filtro" (post-selezione) per scartare manualmente le soluzioni che violavano la regola. Risultato: Migliore qualità delle soluzioni!

• Il collo di bottiglia: Per i computer quantistici, il problema non è solo la potenza di calcolo, ma come sono collegati i pezzi.

  • L'analogia: Immagina di dover collegare 100 persone in una stanza, ma possono parlarsi solo con chi stanno accanto. Se vuoi che tutti parlino con tutti, devi costruire un labirinto di corridoi. Costruire questi corridoi (chiamati embedding) richiede tanto tempo e risorse, spesso più del tempo necessario per risolvere il problema stesso.

• Il rumore è il nemico: I computer quantistici attuali sono "rumorosi". È come cercare di ascoltare una conversazione in un concerto rock. Più il problema è grande, più il rumore copre la voce della soluzione corretta.

4. Il Verdetto Finale 🏆

• Per i problemi piccoli e medi: I computer quantistici sono promettenti e possono trovare soluzioni creative che i computer classici potrebbero non vedere subito.
• Per i problemi grandi: Al momento, i computer classici (Simulated Annealing) sono ancora i re indiscussi. Sono più veloci, più precisi e non si confondono.
• Il futuro: I computer quantistici stanno migliorando. Gli scienziati sperano che, con hardware migliore (meno rumore, più collegamenti), possano un giorno battere i computer classici su problemi specifici.

In Sintesi

Questo studio è come una gara di automobilismo su un circuito nuovo.
I computer classici sono le F1: veloci, affidabili e pronte a correre subito.
I computer quantistici sono le macchine da corsa sperimentali: hanno un potenziale pazzesco e possono andare velocissime su certi tratti, ma spesso si inceppano nei cambi, hanno bisogno di manutenzione continua e faticano a gestire le curve strette (i problemi complessi).

La ricerca non dice "i computer quantistici sono inutili", ma ci dice: "Ecco dove siamo oggi, ecco dove facciamo fatica e ecco cosa dobbiamo migliorare per vincere la prossima gara".

Sommario tecnico

Titolo: Benchmarking Cross-Platform di Algoritmi di Ottimizzazione Quantistica a Breve Termine

1. Il Problema e il Contesto

Il lavoro si concentra sulla valutazione delle prestazioni degli algoritmi di ottimizzazione quantistica disponibili attualmente (era "near-term" o NISQ) rispetto ai metodi classici. L'obiettivo è fornire un framework di benchmarking rigoroso e trasparente per confrontare diverse piattaforme hardware e approcci algoritmici su problemi reali.

• Problema di Test: Gli autori hanno scelto il problema della configurazione di difetti nel grafene. Nello specifico, si tratta di determinare quale configurazione di rimozione di un numero fisso di atomi di carbonio (vacanze) da un reticolo di grafene minimizzi l'energia del sistema (massimizzando i legami carbonio-carbonio rimanenti).
• Formulazione: Il problema è modellato come un QUBO (Quadratic Unconstrained Binary Optimization), un problema NP-hard. La formulazione specifica corrisponde al problema del "Densest k-Subgraph" (il sottografo più denso con $k$ nodi), dove $k = N - 3$ (rimozione di 3 atomi).
• Sfida: I problemi QUBO densi (con alta connettività tra le variabili) sono difficili da mappare su hardware quantistico a causa delle limitazioni di connettività dei qubit e del rumore.

2. Metodologia

Gli autori hanno implementato un framework di benchmarking "end-to-end" che confronta metodi quantistici e classici sullo stesso set di istanze QUBO.

• Algoritmi Quantistici:
  • VQE (Variational Quantum Eigensolver): Eseguito sia su un simulatore classico a vettore di stato (senza rumore) che su un processore quantistico reale basato su gate (IBM ibm_fez, 156 qubit). È stato utilizzato un ansatz RealAmplitudes e l'obiettivo è stato ottimizzato usando la Conditional Value at Risk (CVaR) per migliorare la convergenza.
  • Quantum Annealing (QA): Eseguito su un annealer quantistico commerciale (D-Wave Advantage 6.4, 5612 qubit fisici).
• Algoritmi Classici:
  • Forza Bruta: Per istanze piccole (es. 18 variabili) per ottenere la soluzione esatta.
  • Simulated Annealing (SA): Un metodo euristico classico.
  • Campionamento Casuale: Come baseline.
• Hardware e Accesso: Tutti gli esperimenti sono stati condotti tramite modelli QCaaS (Quantum Computing as a Service).
• Metriche di Valutazione:
  • Qualità della Soluzione: Probabilità di trovare la soluzione ottima ($P_s$) e Rapporto di Approssimazione (AR).
  • Risorse Tempore: User Runtime (tempo totale per l'utente, includendo codifica, latenza e tempo dispositivo) e QPU Time (tempo effettivo di calcolo sul processore quantistico).
• Post-Selezione: Poiché il problema è stato formulato con vincoli soft (tramite termini di penalità $\lambda$), è stata applicata una post-selezione classica per rimuovere le soluzioni che violano il vincolo del numero di vacanze. È stato scoperto che l'uso di coefficienti di penalità $\lambda$ piccoli, combinati con la post-selezione, migliora le prestazioni.

3. Contributi Chiave

1. Framework di Benchmarking Unificato: Introduzione di un metodo sistematico per confrontare algoritmi gate-based (VQE), annealing quantistico e metodi classici su istanze QUBO dense e completamente connesse.
2. Scalabilità su Hardware Reale: Applicazione del framework per risolvere QUBO completamente connessi fino a 72 variabili su hardware commerciale, spingendo i limiti attuali della tecnologia.
3. Analisi di Scalabilità Classica: Dimostrazione che il Simulated Annealing scala in tempo polinomiale per questo specifico problema, risolvendo istanze fino a 388 variabili, fornendo un benchmark di riferimento robusto.
4. Insight Tecnici Specifici:
   • Identificazione dell'embedding come collo di bottiglia principale per l'annealing quantistico (specialmente con la tecnica minor embedding).
   • Analisi dell'impatto del rumore e della variabilità dei parametri iniziali sul VQE, che porta a grandi deviazioni standard nelle prestazioni.
   • Dimostrazione che i tempi di calcolo classici (compilazione, ottimizzazione) dominano il User Runtime del VQE su QPU, superando di ordini di grandezza il tempo effettivo di esecuzione sul QPU.

4. Risultati Principali

• Prestazioni del Simulated Annealing (SA): È stato il metodo migliore in assoluto, offrendo la più alta qualità di soluzione ($P_s \approx 0.99$) e i tempi di esecuzione più brevi, con una scalabilità polinomiale fino a 338 variabili.
• Quantum Annealing (QA):
  • Ha dimostrato prestazioni superiori al campionamento casuale ma inferiori al SA.
  • È stato possibile risolvere problemi fino a 72 variabili con minor embedding, ma la probabilità di successo ($P_s$) è diminuita drasticamente all'aumentare della dimensione.
  • La tecnica di clique embedding (più efficiente per grafi completamente connessi) ha ridotto i tempi di embedding ma ha mostrato limiti di scalabilità su dimensioni maggiori rispetto al minor embedding in termini di $P_s$ per le istanze testate.
  • L'embedding ha rappresentato la maggior parte del tempo di esecuzione dell'utente, non il tempo di calcolo dell'annealer.
• VQE su QPU:
  • Le prestazioni sono state limitate dal rumore e dalla difficoltà di convergenza dell'ottimizzatore classico.
  • Per problemi oltre le 50 variabili, il VQE ha spesso fallito nel trovare soluzioni con overlap significativo con lo stato fondamentale entro il numero massimo di iterazioni.
  • Il tempo di esecuzione totale è stato estremamente alto (migliaia di secondi) a causa dei tempi di compilazione e delle iterazioni classiche, rendendo difficile eseguire ripetizioni statistiche significative.
  • L'uso della CVaR ha aiutato a migliorare leggermente la probabilità di trovare la soluzione ottima rispetto al VQE standard.
• Limiti di Scalabilità: Oltre le 72 variabili, le limitazioni di connettività del dispositivo, il rumore e gli overhead computazionali classici hanno impedito un'ulteriore scalabilità efficace con i metodi quantistici testati.

5. Significato e Conclusioni

Il lavoro sottolinea che, allo stato attuale della tecnologia (inizio 2025/2026), nessun algoritmo quantistico ha superato i metodi euristici classici (come il Simulated Annealing) in termini di combinazione di qualità della soluzione e tempo di esecuzione per questo specifico problema di ottimizzazione densa.

• Implicazioni: Il benchmarking rivela che i colli di bottiglia non sono solo algoritmici, ma derivano fortemente dall'hardware (rumore, connettività) e dai processi di pre/post-elaborazione classica (embedding, compilazione).
• Futuro: Il framework proposto è applicabile a qualsiasi problema di ottimizzazione. Gli autori suggeriscono che per ottenere un vantaggio quantistico reale, saranno necessari miglioramenti nell'hardware (qubit più stabili, connettività migliore), tecniche di mitigazione degli errori e strategie algoritmiche avanzate (es. warm-start, codifiche efficienti qubit-variabile).
• Valore del Lavoro: Fornisce una valutazione onesta e trasparente delle capacità attuali dei computer quantistici, spostando il focus dalle promesse teoriche ai dati sperimentali reali, e identifica le aree critiche che richiedono sviluppo per rendere l'ottimizzazione quantistica praticabile su larga scala.