Quantum Optimization Methods for the Generalized Traveling Salesman Problem

Questo articolo valuta i metodi di ottimizzazione quantistica, in particolare una nuova formulazione QUBO per l'annealing quantistico e una variante vincolata di QAOA con un mixer XY, per il Problema del Commesso Viaggiatore Generalizzato, rilevando che, sebbene offrano una qualità della soluzione competitiva su istanze di piccole dimensioni, attualmente affrontano sfide significative in termini di fattibilità, scalabilità e tempo di esecuzione rispetto ai solver classici.

L'essenziale

Immagina di essere un robot di consegna con un compito molto specifico. Hai una lista di attività da svolgere, ma queste sono raggruppate in "quartieri" (cluster). La tua regola è semplice: devi visitare esattamente una fermata in ogni quartiere, e devi farlo in un ordine che risparmi la maggior quantità di carburante. Non puoi visitare due fermate nello stesso quartiere, e non puoi saltare un quartiere intero. Questo è il Problema del Commesso Viaggiatore Generalizzato (GTSP).

Ora, immagina di provare a risolvere questo puzzle non con un computer normale, ma con un Computer Quantistico. Queste sono macchine futuristiche che utilizzano le strane regole della fisica (come essere in due posti contemporaneamente) per trovare risposte.

Questo articolo è un rapporto sul quanto bene i computer quantistici attuali riescono a risolvere questo specifico puzzle della "consegna nei quartieri". Ecco la suddivisione di ciò che i ricercatori hanno fatto e di ciò che hanno scoperto, utilizzando semplici analogie.

I Due Strumenti Quantistici Che Hanno Provato

Il team ha testato due diversi "motori quantistici" per risolvere il puzzle:

1. L'Annealer Quantistico (Il "Labirinto Magnetico"):
   Pensa a questo come a una biglia che rotola giù per una collina irregolare e complessa. Il fondo della collina rappresenta la soluzione perfetta (il percorso più economico). La macchina cerca di far rotolare la biglia giù per trovare il punto più basso.

   • Il Problema: La collina è piena di "trappole" (percorsi invalidi). La biglia spesso rimane bloccata in una piccola depressione che sembra il fondo ma non è la risposta reale. I ricercatori hanno dovuto costruire una mappa molto specifica (una formulazione QUBO) per assicurarsi che la biglia rotolasse solo su percorsi validi.

2. Il QAOA Basato su Porte (Il "Funambolo"):
   Questo è come un funambolo che cerca il miglior percorso attraverso un burrone. Fa passi (strati di un circuito), aggiustando l'equilibrio (parametri) per avvicinarsi all'obiettivo.

   • L'Innovazione: I ricercatori hanno costruito una speciale "imbracatura di sicurezza" (un mixer XY) per questo camminatore. Questa imbracatura costringe il camminatore a rimanere sulla fune (visitando esattamente una fermata per quartiere) ad ogni passo. Tuttavia, hanno ancora dovuto fare affidamento su "cartelli di penalità" per impedire al camminatore di scendere completamente dalla mappa (visitando i quartieri sbagliati o strade inesistenti).

Il Problema del "Limite di Dimensione"

I computer quantistici attuali sono come piccole calcolatrici rispetto ai supercomputer che usiamo oggi. Non hanno abbastanza "pulsanti" (qubit) per gestire problemi grandi.

Per far entrare il puzzle in queste piccole macchine, i ricercatori hanno inventato un Trucco di Pre-elaborazione:

• Immagina di avere una città con 100 quartieri, ma il tuo robot può gestirne solo 5.
• Invece di provare a risolvere l'intera città, hanno guardato ogni quartiere e detto: "Ok, quale singola fermata in questo quartiere è più vicina al quartiere successivo?"
• Hanno scartato tutte le altre fermate e mantenuto solo la "migliore entrata" e la "migliore uscita" per ogni quartiere.
• Questo ha ridotto la vasta città a un piccolo villaggio che il computer quantistico poteva effettivamente gestire.

Cosa Hanno Trovato (I Risultati)

I ricercatori hanno confrontato i loro robot quantistici con un computer classico molto intelligente (un algoritmo standard chiamato GLNS).

1. Le Buone Notizie (Puzzle Piccoli):
Quando il puzzle era piccolo (da 3 a 5 quartieri), i computer quantistici sono stati imponenti. Spesso trovavano il percorso perfetto o uno molto vicino ad esso. In questi scenari minuscoli, si sono comportati esattamente quanto i migliori computer classici.

2. Le Cattive Notizie (Dolori di Crescita):
Non appena il puzzle è diventato leggermente più grande (più di 5 o 7 quartieri), i computer quantistici hanno iniziato a lottare pesantemente.

• Il Crollo della "Fattibilità": Il problema più grande non era che trovavano un percorso cattivo; è che spesso non trovavano nessun percorso valido. Immagina il funambolo che cade dalla fune, o la biglia che rotola contro un muro.
• Il Fattore "Rumore": Man mano che il problema cresceva, i computer quantistici si "confondevano" a causa del rumore e delle limitazioni. Per i test più grandi, non sono riusciti a trovare una singola soluzione valida più del 99% delle volte.
• Il Collo di Bottiglia: I ricercatori hanno scoperto che il problema principale è il campionamento. Il computer quantistico deve provare molte, molte volte per ottenere una buona risposta. Ma man mano che il puzzle diventa più grande, la probabilità di ottenere qualsiasi risposta valida nel tempo consentito scende a quasi zero.

Il Verdetto

L'articolo conclude che, sebbene i computer quantistici siano attualmente eccellenti per puzzle piccoli e specifici, non sono ancora pronti per risolvere da soli grandi problemi di instradamento del mondo reale.

• Per lavori piccoli: Funzionano bene e possono competere con i computer classici.
• Per lavori grandi: Attualmente falliscono perché non riescono a mantenere la soluzione "valida" (fattibile) man mano che il problema diventa complesso.

I ricercatori suggeriscono che affinché i computer quantistici siano utili per questo tipo di problema in futuro, abbiamo bisogno di modi migliori per costringere il computer a rimanere sul "percorso valido" senza crashare, e abbiamo bisogno di macchine più grandi e meno rumorose. Fino ad allora, il "trucco di pre-elaborazione" è l'unico modo per adattare questi problemi all'hardware quantistico di oggi, ma anche quello ha dei limiti.

Sommario tecnico

1. Definizione del Problema

Il documento affronta il Problema Generale del Commesso Viaggiatore (GTSP), un'estensione NP-difficile del classico TSP.

• Definizione: Il problema coinvolge un grafo in cui i nodi sono partizionati in cluster disgiunti. L'obiettivo è trovare un tour a costo minimo che visiti esattamente un nodo da ciascun cluster e ritorni all'origine.
• Applicazioni: Il GTSP modella scenari industriali reali come la pianificazione flessibile della produzione, lo stoccaggio/recupero automatizzato, il prelievo degli ordini nei magazzini e la pianificazione del movimento robotico (dove un robot deve selezionare una variante di esecuzione tra diverse opzioni per una sequenza di sottocompiti).
• Sfida: Sebbene esistano soluzioni quantistiche per il TSP standard, le formulazioni per il GTSP sono scarse. Il problema introduce vincoli complessi (selezione e sequenziamento dei cluster) che sono difficili da mappare sull'hardware quantistico intermedio rumoroso (NISQ) attuale a causa delle limitazioni dei qubit e della difficoltà nel mantenere la fattibilità della soluzione.

2. Metodologia

Gli autori propongono e valutano due paradigmi distinti di ottimizzazione quantistica, affiancati da una strategia di pre-elaborazione classica per mitigare le limitazioni hardware.

A. Pre-elaborazione: Nodi più vicini estesi ai cluster (NN2C)

Per affrontare il numero limitato di qubit dell'hardware attuale, gli autori estendono l'algoritmo NN2C per ridurre la dimensione dell'istanza prima della risoluzione:

• Meccanismo: Per ogni cluster, l'algoritmo seleziona il "nodo di ingresso migliore" (minimizzando la distanza in entrata dagli altri cluster) e il "nodo di uscita migliore" (minimizzando la distanza in uscita).
• Risultato: Ciò riduce il numero di nodi per cluster ad al massimo due, riducendo efficacemente la dimensione del problema preservando la struttura dei cluster. Ciò consente di mappare istanze originali GTSPLIB più grandi su istanze quantistiche risolvibili.

B. Approccio di Ricottura Quantistica (Q-GTSP)

• Formulazione: Gli autori propongono una nuova codifica QUBO (Ottimizzazione Binaria Quadratica Senza Vincoli) utilizzando una rappresentazione one-hot ($x_{c,i} = 1$ se il nodo $i$ è visitato al passo $c$).
• Vincoli: La funzione di costo è aumentata con termini di penalità quadratici per imporre:
  1. Esattamente un nodo visitato per passo ($p_0$).
  2. Esattamente un nodo visitato per cluster ($p_1$).
  3. Transizioni di bordo valide ($p_2$).
• Ponderazione della Penalità: Viene calcolato un fattore di penalità specifico $\lambda$ per garantire che qualsiasi soluzione non valida sia strettamente più costosa della soluzione valida più costosa, garantendo teoricamente che lo stato fondamentale corrisponda a un tour fattibile.
• Hardware: Eseguito sulla QPU Advantage2 di D-Wave (topologia Zephyr).

C. Approccio basato su Gate (C-QAOA)

• Algoritmo: Una variante vincolata dell'algoritmo Quantum Approximate Optimization Algorithm (QAOA).
• Progettazione del Mixer: Invece di un mixer standard a campo trasverso, gli autori impiegano un mixer XY. Questo mixer preserva il vincolo "one-hot" (peso di Hamming passo-passo) limitando l'evoluzione quantistica al sottospazio fattibile del vincolo di passo.
• Gestione dei Vincoli: Mentre il mixer XY gestisce intrinsecamente il vincolo di passo, i vincoli di cluster e bordo sono ancora imposti tramite termini di penalità nell'Hamiltoniano di costo.
• Inizializzazione: Il circuito inizia in un singolo stato casuale fattibile one-hot invece che in una sovrapposizione uniforme per ridurre la profondità del circuito e le richieste hardware.
• Simulazione: Simulato utilizzando Qiskit Aer (a causa del limitato accesso alle QPU IBM per l'ottimizzazione completa dei parametri), mirando alle architetture del processore Heron.

3. Contributi Chiave

1. Nuova Codifica GTSP QUBO: Una formulazione specifica focalizzata sulla generazione di soluzioni fattibili attraverso termini di penalità attentamente sintonizzati.
2. Pipeline C-QAOA Vincolata: Implementazione di un C-QAOA orientato all'hardware che utilizza un mixer XY per preservare intrinsecamente la fattibilità passo-passo, un passo significativo verso algoritmi quantistici che preservano i vincoli.
3. Pre-elaborazione Estesa: Un algoritmo NN2C modificato, adattato per istanze GTSP asimmetriche, per ridurre le dimensioni del problema per dispositivi NISQ.
4. Benchmarking Completo: Un confronto diretto tra approcci di ricottura quantistica e basati su gate rispetto a risolutori classici all'avanguardia (GLNS/Gurobi) sul dataset GTSPLIB.

4. Risultati Sperimentali

Lo studio ha valutato le prestazioni su istanze Subsample (cluster selezionati casualmente) e Pre-elaborate (ridotte tramite NN2C) da GTSPLIB.

• Istanze Piccole (3–5 nodi):

  • Entrambi gli approcci quantistici hanno trovato frequentemente soluzioni ottimali o quasi ottimali.
  • Fattibilità: La Ricottura Quantistica (Q-GTSP) ha mostrato tassi di fattibilità elevati (fino al 98% sulle istanze pre-elaborate). C-QAOA ha mostrato una fattibilità inferiore (spesso <50%) ma è comunque riuscito a trovare soluzioni ottimali nell'analisi "best-shot".
  • Confronto: Su grafi molto piccoli, i risolutori quantistici sono stati competitivi rispetto ai risolutori classici.

• Scalabilità e Istanze più Grandi (6–20+ nodi):

  • Collasso della Fattibilità: All'aumentare della dimensione dell'istanza, la percentuale di soluzioni fattibili è crollata drasticamente. Per C-QAOA, la fattibilità è scesa sotto l'1% per istanze con 13–15 nodi. Per Q-GTSP, la fattibilità è diminuita significativamente oltre i 15 nodi.
  • Qualità della Soluzione: Il rapporto di approssimazione medio è spesso sceso al di sotto della linea di base del guess casuale, indicando che la maggior parte dei tentativi campionati era non valida o di scarsa qualità.
  • Limiti Hardware:
    • Q-GTSP: Ha incontrato "fallimenti di embedding" su istanze medie pre-elaborate dove i requisiti di qubit logici (fino a 400) superavano la capacità dei qubit fisici.
    • C-QAOA: Ha sofferto di bassi tassi di campionamento; 1500 tentativi erano insufficienti a coprire lo spazio di ricerca che cresceva esponenzialmente.

• Impatto della Pre-elaborazione:

  • La pre-elaborazione ha migliorato significativamente la fattibilità dell'approccio di Ricottura Quantistica, permettendogli di gestire strutture di problemi sottostanti più grandi.
  • La pre-elaborazione ha avuto un impatto negativo o neutro su C-QAOA, probabilmente a causa dell'aumentata complessità strutturale (più cluster) che la bassa profondità del circuito ($p=1$) non è riuscita a gestire.

5. Significato e Conclusione

• Stato Attuale: Gli ottimizzatori quantistici mostrano promesse per istanze GTSP su piccola scala, capaci di trovare soluzioni ottimali. Tuttavia, attualmente soffrono di scarsa scalabilità e bassi tassi di fattibilità all'aumentare della dimensione del problema.
• Collo di Bottiglia Primario: Il principale modo di fallimento non è solo la qualità della soluzione, ma l'incapacità di generare soluzioni fattibili entro un budget fisso di tentativi. La gestione dei vincoli basata su penalità (in QUBO) e i mixer superficiali (in QAOA) faticano a navigare efficacemente nello spazio di ricerca vincolato.
• Direzioni Future: Gli autori concludono che affinché l'ottimizzazione quantistica sia praticabile per il GTSP, il lavoro futuro deve concentrarsi su:
  1. Gestione dei Vincoli: Andare oltre i termini di penalità verso l'imposizione intrinseca dei vincoli (ad esempio, mixer più sofisticati in QAOA).
  2. Scalabilità: Migliorare l'efficienza della codifica e la gestione della profondità del circuito.
  3. Hardware: Utilizzare topologie di qubit più grandi e meglio connesse per ridurre l'overhead di embedding.

In sintesi, sebbene il documento stabilisca un quadro fondamentale per il GTSP quantistico, evidenzia che l'hardware e gli algoritmi NISQ attuali non sono ancora pronti a sostituire i risolutori classici per problemi di instradamento pratici su scala medio-grande senza significativi progressi algoritmici nella gestione dei vincoli.