Hybrid quantum-classical end-to-end pipeline for solving MILPs: a vehicle routing case study

Sintesi Tecnica: Pipeline Ibrida Quantistico-Classica End-to-End per la Risoluzione di MILP

Definizione del Problema
I problemi di Programmazione Lineare Intera Mista (MILP) sono centrali per i processi decisionali ad alto impatto in settori come la logistica e la gestione della supply chain, ma sono computazionalmente impegnativi a causa della loro natura combinatoria. Sebbene le tecniche di decomposizione come la Decomposizione di Benders (BD) siano ampiamente utilizzate per risolvere MILP su larga scala separandoli in un problema master (MP) e sottoproblemi (SP), esse spesso soffrono di una convergenza lenta. Questa convergenza dipende criticamente dalla selezione di "tagli" (vincoli) informativi da aggiungere al problema master. Un lavoro precedente di Paterakis [1] ha proposto l'uso del quantum annealing per risolvere lo step di selezione dei tagli — formulato come un problema di Copertura Minima di Insiemi (Minimum Set Cover) — per accelerare questo processo. Tuttavia, il quantum annealing richiede costose procedure di minor-embedding che introducono un overhead significativo quando si scala il problema.

Metodologia
Questo articolo presenta un framework di ottimizzazione ibrido quantistico-classico end-to-end che estende l'approccio di decomposizione di Benders Multiple Cuts via Multiple Solutions (MCMS). L'innovazione principale consiste nel sostituire lo step di quantum annealing con implementazioni del Quantum Approximate Optimization Algorithm (QAOA) basate su gate.

Il framework opera come segue:

1. Decomposizione di Benders MCMS: L'algoritmo genera molteplici soluzioni candidate per ogni iterazione, risolvendo più sottoproblemi in parallelo per produrre un pool di tagli candidati.
2. Selezione dei Tagli come QUBO: Per evitare che il problema master diventi computazionalmente oneroso a causa di un numero eccessivo di tagli, viene selezionato un sottoinsieme di tagli informativi. Questo viene formulato come un problema di Copertura Minima di Insiemi, che viene poi mappato in un'istanza di Ottimizzazione Binaria Quadratica Non Vincolata (QUBO).
3. Integrazione QAOA: A differenza dell'approccio precedente basato sull'annealing, questo framework risolve il QUBO utilizzando QAOA. La pipeline si interfaccia con tre diversi solver:
   • Ava di Fermioniq: Un emulatore di circuiti basato su reti di tensori.
   • MPS-JuliQAOA: Un emulatore di Matrix Product State (MPS) open-source costruito in Julia.
   • IBM Quantum: Esecuzione diretta su hardware quantistico superconduttore (processore IBM Eagle).
4. Caso di Studio: Il framework è valutato sul Problema del Veicolo (VRP), un problema di ottimizzazione logistica canonico. Lo studio utilizza un benchmark standardizzato da QOptLib (20 clienti, 4 veicoli) e istanze toy casuali (5 clienti) per testare la fattibilità della pipeline.

Contributi Chiave

• Estensione Gate-Based: Il documento estende l'attuale framework HQC-MCMS dal quantum annealing al calcolo quantistico basato su gate, consentendo l'esecuzione sia su emulatori di reti di tensori che su processori quantistici superconduttori.
• Implementazione End-to-End: Gli autori dimostrano con successo una pipeline completamente funzionale che integra subroutine QAOA in un ciclo di decomposizione di Benders classico.
• Benchmarking Empirico: Lo studio fornisce un'analisi comparativa delle prestazioni della pipeline attraverso diversi backend di solver (Cbc classico, MPS-JuliQAOA, Fermioniq e IBM Quantum) su istanze VRP.

Risultati
I risultati sperimentali forniscono diverse intuizioni critiche riguardo l'attuale viabilità del vantaggio quantistico in questo specifico contesto:

• Prestazioni Classiche: Nel setting completamente classico (utilizzando Cbc per la selezione dei tagli), la pipeline trova con successo soluzioni ammissibili per l'istanza VRP a 20 clienti, con il gap di ottimalità che diminuisce nel corso delle iterazioni. L'approccio Multi-Cut (utilizzando più sottoproblemi) porta a soluzioni ammissibili in meno iterazioni.
• Colli di Bottiglia del Runtime: L'analisi della pipeline classica rivela che lo step di selezione dei tagli consuma solo una piccola frazione del tempo totale di iterazione. La maggior parte del tempo computazionale è impiegata per risolvere il Problema Master.
• Prestazioni Quantistiche: Quando lo step di selezione dei tagli viene sostituito da QAOA (utilizzando MPS-JuliQAOA) su un problema toy, il runtime totale aumenta significativamente rispetto all'approccio classico. Lo studio nota che MPS-JuliQAOA è molto meno efficiente del solver classico Cbc per il problema della copertura minima di insiemi a questa scala.
• Output QAOA: Gli esperimenti su hardware quantistico ed emulatori mostrano che, per le configurazioni testate, la maggior parte dei campioni QAOA risulta in soluzioni non ammissibili (ovvero, non formano una copertura di insiemi valida). Sebbene circuiti più profondi ($p=3$) abbiano prodotto campioni con costo più ottimale rispetto a quelli più superficiali ($p=1$), le prestazioni complessive non hanno superato i metodi classici.

Significatività e Dichiarazioni
L'articolo conclude con una valutazione modesta dello stato attuale del framework. Gli autori dichiarano esplicitamente che, per le dimensioni dei problemi e le configurazioni testate, il vantaggio quantistico è improbabile. La ragione principale è duplice:

1. Lo step di selezione dei tagli, che è l'obiettivo dell'accelerazione quantistica, non è un collo di bottiglia computazionale nell'attuale pipeline MCMS classica; la risoluzione del Problema Master domina il runtime.
2. Il solver classico (Cbc) supera ampiamente le implementazioni QAOA per le specifiche istanze di Copertura Minima di Insiemi generate a questa scala.

Gli autori sottolineano che, sebbene la pipeline sia tecnicamente funzionale e dimostri un passo riproducibile verso l'ottimizzazione potenziata dal quantum, la traduzione del problema di copertura minima in QUBO introduce un overhead sostanziale. Essi sostengono che la ricerca futura debba concentrarsi su benchmarking su scala maggiore, dove lo step di selezione dei tagli potrebbe diventare un collo di bottiglia più significativo, e dove unità di elaborazione quantistica (QPU) più potenti potrebbero potenzialmente offrire valore. Lo studio funge da analisi empirica cautelativa, evidenziando come gli attuali metodi quantistici non forniscano ancora un'accelerazione per questo specifico step di decomposizione in istanze pratiche di piccola-media scala.