⚛️ quantum physics

A Hybrid Classical-Quantum Annealing Algorithm for the TSP

Questo articolo propone un algoritmo ibrido di annealing classico-quantistico per il Problema del Commesso Viaggiatore che utilizza la contrazione dei grafi per ridurre la dimensionalità del problema, consentendo una soluzione efficiente sui dispositivi quantistici attuali come l'annealer D-Wave, con le prestazioni validate sia tramite simulazione classica che su hardware quantistico.

Autori originali: Siwei Hu, Victor Lopata, Salvatore Sinno, Shruthi Thuravakkath, Paolo Zuliani

Pubblicato 2026-05-12

📖 5 min di lettura🧠 Approfondimento

CC BY 4.0

Autori originali: Siwei Hu, Victor Lopata, Salvatore Sinno, Shruthi Thuravakkath, Paolo Zuliani

Articolo originale sotto licenza CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Questa è una spiegazione generata dall'IA dell'articolo qui sotto. Non è stata scritta né approvata dagli autori. Per precisione tecnica, consulta l'articolo originale. Leggi il disclaimer completo

Immagina di essere un agente di viaggio che cerca di pianificare il viaggio su strada perfetto per un cliente. Hai una lista di 1.000 città che desidera visitare e devi determinare l'unico percorso più breve che passi per ogni città esattamente una volta e le riporti a casa. Questo è il famoso Problema del Commesso Viaggiatore (TSP).

Il problema è che, man mano che il numero di città aumenta, il numero di percorsi possibili esplode così rapidamente che persino i supercomputer più potenti al mondo possono rimanere bloccati nel tentativo di trovare il percorso assolutamente migliore. È come cercare un singolo granello di sabbia specifico su una spiaggia che continua a diventare più grande ogni secondo.

Questo articolo propone una strategia astuta di "lavoro di squadra" per risolvere questo enigma combinando il meglio di due mondi: i computer classici (quelli che usiamo oggi) e i computer quantistici (quelli futuristici e sperimentali).

Ecco come funziona il loro metodo, spiegato attraverso semplici analogie:

1. Il Problema: Troppe Opzioni

Pensa al TSP come a una gigantesca e aggrovigliata palla di lana. Se provi a districare tutto insieme, è impossibile. I computer quantistici attuali sono come mani minuscole e delicate; sono incredibilmente potenti ma possono tenere solo un piccolo pezzo di lana alla volta. Non riescono a gestire l'intera palla da 1.000 città perché non hanno abbastanza "dita" (qubit) o le connessioni giuste per afferrare tutto.

2. La Soluzione: La "Spina Dorsale Fidata"

Il segreto degli autori è una tecnica chiamata Contrazione del Grafo. Immagina di avere un gruppo di 500 diversi agenti di viaggio, ognuno che schizza la propria idea di un buon percorso per le 1.000 città.

Il Pool: Raccogli tutti questi 500 schizzi.
Il Modello: Osservi attentamente le mappe. Noti che in quasi ogni singolo schizzo, gli agenti concordano sul fatto che la Città A dovrebbe essere collegata alla Città B, e la Città C alla Città D. Queste sono le connessioni "fidate".
La Scorciatoia: Invece di trattare ogni città come una fermata separata, prendi quelle connessioni concordate e le "incollai" insieme. Trasformi una lunga catena di città (A-B-C-D) in un'unica "mega-città" sovradimensionata.

Facendo questo, non stai cambiando la destinazione; stai solo semplificando la mappa. Potresti trasformare un problema da 1.000 città in un problema da 50 città. Questa è la contrazione.

3. Il Passo Quantistico: La "Bussola Magica"

Ora che hai ridotto la mappa a una dimensione gestibile (diciamo 50 città), consegni questo piccolo enigma all'Annealer Quantistico (come la macchina D-Wave che hanno utilizzato).

I Computer Classici risolvono solitamente questi enigmi provando un percorso, rimanendo bloccati e provandone un altro (come un topo in un labirinto).
I Computer Quantistici utilizzano un fenomeno chiamato "tunneling quantistico". Immagina che il labirinto abbia valli profonde dove il topo rimane intrappolato. Un computer quantistico è come un fantasma che può semplicemente tunnelare attraverso le pareti della valle per trovare l'uscita dall'altra parte.

Gli autori hanno utilizzato una simulazione di questa capacità quantistica da "fantasma" (chiamata Monte Carlo con Integrale di Percorso) per trovare il percorso migliore per la mappa piccola e contratta. Poiché la mappa è ora abbastanza piccola, il computer quantistico può effettivamente risolverla in modo efficiente.

4. Il Risultato: Rimettere Tutto Insieme

Una volta che il computer quantistico ha trovato il percorso migliore per le "mega-città", l'algoritmo le "scollega", espandendo il percorso di nuovo fino alle 1.000 città originali. Poiché le parti "incollate" erano le connessioni più affidabili trovate in primo luogo, il percorso finale è molto vicino alla soluzione perfetta.

Cosa Hanno Trovato?

Il team ha testato questo su dati di viaggio reali (da una libreria chiamata TSPLIB):

Viaggi Piccoli: Per piccoli gruppi di città, il loro metodo ha trovato il percorso perfetto ogni volta.
Viaggi Grandi: Per viaggi massicci (come 1.000+ città), sono riusciti a ridurre il problema a una dimensione che un computer quantistico poteva gestire. I percorsi risultanti erano molto buoni (solitamente entro il 2-4% della distanza perfetta), il che rappresenta un enorme miglioramento rispetto al tentativo di risolvere tutto con un computer quantistico da solo.
Il Compromesso: Hanno scoperto che se incollavano troppe città insieme (essendo troppo aggressivi), rischiavano di commettere un errore. Se ne incollavano troppo poche, il computer quantistico era ancora sopraffatto. Dovevano trovare una soglia "Porcellino d'Oro" per ottenere i migliori risultati.

La Conclusione

L'articolo non afferma che questo risolve ogni problema di viaggio istantaneamente. Piuttosto, mostra un modo pratico per utilizzare i computer quantistici limitati di oggi. Usando un computer classico per fare il lavoro pesante di "semplificare" la mappa per prima cosa, possono consegnare un enigma gestibile alla macchina quantistica, che poi utilizza i suoi speciali poteri di "tunneling" per trovare una risposta quasi perfetta. È un team ibrido in cui il computer classico agisce come organizzatore e il computer quantistico agisce come risolutore esperto per la parte finale, più complessa.

Riepilogo Tecnico: Un Algoritmo di Annealing Ibrido Classico-Quantistico per il TSP

Enunciato del Problema

Il Problema del Commesso Viaggiatore (TSP) è un fondamentale problema di ottimizzazione NP-difficile che richiede l'identificazione del ciclo hamiltoniano più breve in un grafo completo pesato. Sebbene i solutori classici esatti (ad esempio Concorde) possano gestire istanze di grandi dimensioni, spesso faticano a garantire la scalabilità in tempo polinomiale. Al contrario, gli approcci quantistici, in particolare l'Annealing Quantistico (QA), offrono un meccanismo alternativo promettente al rumore termico per sfuggire ai minimi locali. Tuttavia, i dispositivi quantistici attuali a scala intermedia rumorosa (NISQ), come gli annealer D-Wave, affrontano severe limitazioni fisiche riguardanti il numero di qubit e la connettività topologica. Questi vincoli impediscono la mappatura diretta di istanze TSP su larga scala, che richiedono una connettività densa, sulle attuali Unità di Elaborazione Quantistica (QPU).

Metodologia

Gli autori propongono un algoritmo ibrido classico-quantistico che colma il divario tra istanze TSP su larga scala e le attuali capacità dell'hardware quantistico. L'approccio sintetizza due metodologie fondanti: una simulazione Monte Carlo a Integrale di Percorso (PIMC) dell'annealing quantistico e una strategia di estrazione di subQUBO.

1. Contrazione del Grafo tramite Frequenza degli Archi

L'innovazione centrale è una tecnica di contrazione del grafo che riduce la dimensionalità del problema originale.

Generazione del Pool: L'algoritmo inizializza un pool di soluzioni candidate ( $P$ ) utilizzando permutazioni casuali raffinate mediante Annealing Simulato (SA) con mosse 2-opt.
Identificazione dello Scheletro Confidato: Invece di analizzare l'intero pool, l'algoritmo campiona un sottoinsieme ( $S$ ) per calcolare la frequenza degli archi che appaiono nelle soluzioni. Gli archi che appaiono con una frequenza superiore a una soglia di confidenza ( $\tau$ ) sono identificati come uno "scheletro confidato".
Contrazione: Questi archi ad alta frequenza vengono fissati e i nodi connessi vengono fusi in "super-nodi". Ciò trasforma il grafo originale $G$ in un'istanza TSP sottomessa significativamente più piccola ( $G_{sub}$ ). La matrice delle distanze per il sottoproblema viene ricalcolata per tenere conto della fusione logica dei percorsi (testa e coda dei super-nodi).

2. Ciclo di Ottimizzazione Ibrida

L'algoritmo opera in un ciclo iterativo:

Raffinamento: Euristiche classiche affinano il pool di soluzioni per migliorare l'affidabilità della frequenza degli archi.
Campionamento e Contrazione: Viene campionato un sottoinsieme di soluzioni per determinare gli archi fissi e contrarre il grafo.
Risoluzione Quantistica: Il sottoproblema TSP ridotto viene risolto utilizzando un solutore quantistico. Negli esperimenti del documento, ciò è stato implementato tramite:
- Simulazione Classica: Monte Carlo a Integrale di Percorso (PIMC) basato sullo schema di Martoňák et al., che mappa il TSP su un sistema simile a Ising vincolato utilizzando mosse 2-opt come operatori di energia cinetica.
- Esecuzione Hardware: Esecuzione diretta su una QPU D-Wave Advantage_system 4.1.
Espansione e Aggiornamento: La soluzione del sottoproblema viene espansa nuovamente al grafo originale reinserendo gli archi fissi. Il nuovo tour viene aggiunto al pool e il miglior globale viene aggiornato se viene trovata un' miglioria.
Terminazione: Il processo si ripete fino a quando $K$ iterazioni consecutive non producono miglioramenti.

Contributi Chiave

Framework Ibrido Scalabile: Il documento introduce un metodo per aggirare i limiti di qubit e connettività dei dispositivi NISQ riducendo le istanze TSP di grandi dimensioni a dimensioni gestibili dall'hardware attuale (ad esempio, riducendo un'istanza di 1.002 città a ~185 nodi).
Integrazione di PIMC e SubQUBO: Il lavoro combina la promessa teorica dell'effetto tunnel quantistico PIMC (efficace per navigare paesaggi energetici complessi) con la necessità pratica dell'estrazione di subQUBO (partizionamento iterativo del problema).
Validazione Empirica su Hardware: Gli autori hanno dimostrato con successo l'algoritmo su un annealer quantistico D-Wave, mostrando che la strategia di contrazione permette l'embedding diretto di sottoproblemi TSP che altrimenti sarebbero intrattabili.

Risultati Sperimentali

L'algoritmo è stato valutato su istanze TSPLIB che vanno da 14 a 11.849 città.

Sensibilità ai Parametri:
- Soglia ( $\tau$ ): Abbassare $\tau$ aumenta la compressione (riducendo la dimensione del problema) ma rischia di fissare archi sub-ottimali, aumentando il gap di ottimalità. Una soglia di $\tau=0.75$ ha offerto un equilibrio favorevole per istanze medie.
- Dimensione del Pool ( $N_I$ ) e Dimensione del Campione ( $N_S$ ): Una dimensione del pool di 500 con una dimensione del campione di 250 (50%) ha prodotto i migliori risultati per istanze medie-grandi, suggerendo che il campionamento stocastico impedisce alla selezione degli archi di diventare eccessivamente deterministica.
Prestazioni rispetto alle Baseline Classiche:
- Per istanze piccole (ad esempio burma14, ulysses22), l'algoritmo ha trovato l'ottimo globale (gap 0%).
- Per istanze grandi (ad esempio pr2392), l'algoritmo ha mantenuto un gap medio di ottimalità inferiore al 4%, superando Google OR-Tools in diversi casi (ad esempio, rl11849 ha raggiunto un gap del 7,36% contro il 14,58% di OR-Tools).
Risultati Hardware D-Wave:
- Quando eseguito sulla QPU D-Wave, l'approccio ibrido ha raggiunto gap di ottimalità significativamente migliori rispetto al solutore ibrido BQM nativo di D-Wave. Ad esempio, su ulysses22, il metodo proposto ha raggiunto un gap del 2,57% rispetto al 16,88% del solutore ibrido, risolvendo sottoproblemi di soli ~5 nodi.
Colli di Bottiglia:
- La fase di simulazione PIMC è stata identificata come il principale collo di bottiglia computazionale nella simulazione classica.
- Per istanze molto grandi (ad esempio rl11849), l'overhead classico (inizializzazione e raffinamento del pool) è diventato dominante, rappresentando circa il 70% del tempo di esecuzione, suggerendo che i benefici dell'accelerazione quantistica sono attualmente compensati dai costi di pre-elaborazione classica a scale estreme.

Significato e Affermazioni

Il documento afferma che la sua tecnica ibrida mitiga efficacemente le limitazioni fisiche dei dispositivi quantistici attuali. Sfruttando l'ottimizzazione classica per contrarre il grafo, gli autori dimostrano che:

Fattibilità: Le istanze TSP di grandi dimensioni possono essere ridotte a una scala adatta all'embedding negli annealer NISQ senza perdere l'integrità strutturale richiesta per soluzioni di alta qualità.
Potenziale Vantaggio Quantistico: Sebbene la simulazione PIMC attuale sia classica, il framework è progettato per essere direttamente adattabile all'hardware quantistico. I risultati suggeriscono che se il passaggio PIMC fosse eseguito su un annealer quantistico, il costo computazionale potrebbe essere drasticamente ridotto, offrendo potenzialmente accelerazioni esponenziali per la fase di ottimizzazione.
Robustezza: Il metodo è robusto attraverso dimensioni di istanza variabili, raggiungendo soluzioni esatte per problemi piccoli e mantenendo bassi gap di ottimalità per problemi su larga scala dove le euristiche classiche faticano.

Gli autori concludono che, sebbene l'overhead classico rimanga una sfida per istanze massive, la strategia di contrazione proposta porta con successo il TSP entro la portata della tecnologia attuale di annealing quantistico, validando la fattibilità degli approcci ibridi classico-quantistici per l'ottimizzazione combinatoria.