Quantum-Assisted Vehicle Routing: Realizing QAOA-based Approach on Gate-Based Quantum Computer

Sintesi Tecnica: Routing di Veicoli Assistito da Quantum tramite QAOA su Hardware a Gate

Definizione del Problema
Il Problema del Routing di Veicoli (VRP) è una sfida fondamentale di ottimizzazione combinatoria NP-hard centrale per la logistica e il trasporto, che mira a minimizzare i costi (distanza, tempo, carburante) soddisfacendo al contempo vincoli quali la visita dei clienti, la capacità dei veicoli e la continuità del percorso. Gli algoritmi classici faticano a trovare soluzioni ottimali anche per istanze di dimensioni modeste a causa della scalabilità esponenziale. Questo lavoro affronta la sfida di mappare il VRP su computer quantistici a gate all'interno del regime NISQ (Noisy Intermediate-Scale Quantum), concentrandosi specificamente sui limiti imposti dalla profondità del circuito, dalla connettività dei qubit e dal rumore dell'hardware.

Metodologia
Gli autori propongono un framework basato sull'hardware che integra l'Algoritmo di Ottimizzazione Approssimata Quantistica (QAOA) con una formulazione basata sui collegamenti (link-based) del VRP. La metodologia procede attraverso le seguenti fasi:

1. Formulazione del Problema: Il VRP è modellato utilizzando variabili di arco direzionale ($x_{i,j}$) che rappresentano se un veicolo attraversa un collegamento tra i nodi $i$ e $j$. A differenza delle formulazioni basate sull'espansione temporale o sull'ordine dei percorsi, questo approccio evita l'uso esplicito di variabili di sequenziamento.
2. Codifica dei Vincoli: I vincoli critici — conservazione del flusso (ogni cliente visitato esattamente una volta), conteggi di ingresso/uscita dal deposito e eliminazione dei sottotour — sono codificati direttamente nell'Hamiltoniana del costo ($H_C$) tramite termini di penalità. Ciò trasforma il problema vincolato in un problema di Ottimizzazione Binaria Quadratica Non Vincolata (QUBO).
3. Mappatura dell'Hamiltoniana: Il QUBO è mappato su un'Hamiltoniana di Ising adatta al QAOA. L'Hamiltoniana del costo consiste in termini Pauli-Z ($Z_i$) per i costi lineari e interazioni Pauli-Z ($Z_i Z_j$) per le penalità quadratiche. Viene utilizzata un'Hamiltoniana di mixing standard ($H_M = \sum X_i$) per esplorare lo spazio delle soluzioni.
4. Implementazione del Circuito: L'algoritmo è implementato su IBM Quantum System One (Eagle r3, 127 qubit). Il workflow include:
   • Traspilazione: Mappatura dei qubit logici sulla topologia a reticolo heavy-hex, introducendo i necessari gate di swap.
   • Mitigazione dell'Errore: Applicazione del disaccoppiamento dinamico (per preservare la coerenza sui qubit inattivi) e del Pauli twirling (per convertire i canali di rumore in firme specifiche).
   • Ottimizzazione Ibrida: Un ottimizzatore classico (COBYQA) regola iterativamente i parametri variazionali ($\gamma, \beta$) per minimizzare il costo atteso $\langle \psi | H_C | \psi \rangle$.
5. Parametri Sperimentali: Lo studio investiga l'impatto della scalabilità della penalità (specificamente impostando i coefficienti di penalità a due volte la somma dei pesi degli archi) e della normalizzazione dei coefficienti (limitando l'ampiezza dei termini Pauli a uno) sulla fattibilità della soluzione.

Contributi Chiave

• Formulazione Basata sugli Archi Direzionali: Gli autori sviluppano una formulazione che incorpora la conservazione del flusso e l'eliminazione dei sottotour direttamente nell'Hamiltoniana del costo. Questo approccio evita l'elevato overhead di qubit delle formulazioni a espansione temporale e la complessità fattoriale delle formulazioni basate sull'ordine dei percorsi, rendendolo più adatto ai dispositivi a breve termine.
• Pipeline Hardware Completa: Il lavoro esegue l'intera pipeline — dalla codifica del problema e mappatura di Ising alla sintesi del circuito, traspilazione ed esecuzione — su hardware quantistico reale, piuttosto che fare affidamento esclusivamente su simulazioni idealizzate.
• Analisi Empirica dei Colli di Bottiglia: Lo studio valuta quantitativamente come le formulazioni VRP influenzino il numero di qubit e la profondità dei gate a due qubit dopo la traspilazione, identificando la profondità del circuito come il principale collo di bottiglia per il routing vincolato sulle attuali architetture superconduttrici.
• Insight sulla Sensibilità dei Parametri: La ricerca dimostina che la fattibilità della soluzione dipende criticamente dalla selezione dei parametri di penalità e dalla normalizzazione dei coefficienti dell'Hamiltoniana. Nello specifico, la normalizzazione migliora significativamente il campionamento di soluzioni fattibili per istanze più grandi (4 e 5 nodi) dove gli approcci non normalizzati falliscono.

Risultati

• Successo su Piccola Scala: Per un'istanza a 3 nodi e 2 veicoli, il QAOA ha identificato con successo la soluzione ottimale (bit-string 111010) con alta probabilità, soddisfacendo tutti i vincoli inclusa l'eliminazione dei sottotour.
• Sfide di Scalabilità: All'aumentare della dimensione del problema (ad esempio, istanze a 4 e 5 nodi), il numero di gate richiesti è cresciuto esponenzialmente. Un problema a 4 nodi ha richiesto un circuito a 14 qubit con oltre 3.000 gate, impiegando oltre due ore per l'esecuzione, ma producendo soluzioni non fattibili. Un problema a 5 nodi ha richiesto un circuito a 30 qubit con circa 30.000 gate.
• Impatto della Normalizzazione: Senza la normalizzazione dei coefficienti, l'algoritmo non è riuscito a identificare costantemente rotte ottimali nella regione ad alta probabilità per le istanze a 4 e 5 nodi. Con la normalizzazione e un moltiplicatore di penalità di 1,5–2,0, il rapporto di fattibilità dei primi 1.000 bitstring campionati è migliorato significativamente.
• Limiti dell'Hardware: Lo studio conferma che l'attuale rumore dell'hardware e i tempi di coerenza limitati impediscono l'esecuzione di circuiti QAOA profondi richiesti per istanze VRP più grandi. I primi 10 stati campionati per il problema a 4 nodi erano tutti non fattibili senza una attenta regolazione dei parametri.

Significatività e Rivendicazioni
L'articolo rivendica la propria significatività non come una dimostrazione di vantaggio quantistico rispetto ai solver classici per VRP su larga scala, ma come una valutazione pratica eseguita su hardware che chiarisce gli attuali limiti nell'era NISQ. Gli autori sostengono che, sebbene il QAOA possa teoricamente risolvere il VRP, la rapida crescita della complessità del circuito (specificamente la profondità dei gate a due qubit) e l'accumulo di rumore ne limitano attualmente l'applicazione a istanze molto piccole.

Il valore primario dello studio risiede nel fornire indicazioni progettuali concrete per la futura ottimizzazione quantistica:

1. Scelta della Formulazione: Le formulazioni basate sugli archi sono attualmente più fattibili rispetto alle codifiche a espansione temporale o basate sull'ordine dei percorsi grazie ai minori requisiti di qubit e gate.
2. Euristiche dei Parametri: La normalizzazione dei coefficienti e la specifica scalabilità della penalità (circa 2x la somma dei pesi degli archi) sono essenziali per recuperare soluzioni fattibili su istanze più grandi.
3. Direzione Metodologica: Il lavoro delinea che l'avanzamento dell'ottimizzazione quantistica per il VRP richiede non solo miglioramenti algoritmici, ma anche progressi hardware (maggiori numeri di qubit, tassi di errore inferiori) e strategie ibride (ad esempio, transfer learning dei parametri, circuiti dinamici) per mitigare i vincoli di rumore e profondità.

Gli autori concludono che, sebbene la scalabilità rimanga limitata, questo lavoro stabilisce un percorso pratico per l'implementazione del VRP su hardware quantistico e identifica le direzioni metodologiche specifiche necessarie per il progresso futuro nell'ottimizzazione quantistica a breve termine.