Quantum optimization beyond QUBO for industrial logistics and scheduling

Sintesi Tecnica: Ottimizzazione Quantistica Oltre QUBO per Logistica Industriale e Programmazione

Enunciato del Problema
I problemi di programmazione industriale e di instradamento dei trasporti sono sempre più complessi, possedendo spesso strutture matematiche naturali che conducono a formulazioni di Ottimizzazione Binaria Non Vincolata di Ordine Superiore (HUBO) piuttosto che a formulazioni puramente quadratiche. Sebbene il campo dell'ottimizzazione quantistica si sia concentrato prevalentemente sull'Ottimizzazione Binaria Non Vincolata Quadratica (QUBO) a causa della sua mappatura nativa agli Hamiltoniani di Ising e della compatibilità con gli attuali annealer quantistici, tale focalizzazione impone limitazioni significative. La riduzione dei problemi HUBO a QUBO tramite variabili ausiliarie spesso gonfia le dimensioni del problema (numero di qubit), offuscando le dipendenze chiave e fallendo nel rappresentare fedelmente vincoli operativi intricati. Al contrario, mentre algoritmi quantistici digitali come l'Algoritmo Quantistico di Ottimizzazione Approssimata (QAOA) possono teoricamente gestire interazioni di ordine superiore, le implementazioni a breve termine su hardware rumoroso sono spesso limitate in profondità all'aumentare degli ordini di interazione. Questo articolo indaga il compromesso tra la compattezza rappresentativa delle formulazioni HUBO e i costi di implementazione su hardware quantistico attuale ed emergente.

Metodologia
Gli autori propongono e analizzano formulazioni HUBO per tre casi d'uso industriali rappresentativi:

1. QUEST (Trasporto Condiviso Potenziato Quantisticamente): Un problema di matching veicolare in cui i "breaker" sono accoppiati con i "surfer" per minimizzare la resistenza aerodinamica e le discrepanze di tempo/velocità.
2. CVRP (Problema di Instradamento Veicolare con Capacità): Un problema di instradamento di flotte con vincoli di capacità, che estende il Problema del Commesso Viaggiatore.
3. Programmazione dell'Assemblaggio Automobilistico: Un problema di sequenziamento delle auto che coinvolge vincoli di spaziatura, gruppi e corsie di stoccaggio su una linea di assemblaggio.

Per ciascun caso d'uso, gli autori riformulano il problema come HUBO utilizzando codifiche binarie compatte (scalamento logaritmico nelle variabili) invece delle codifiche one-hot standard (scalamento lineare). Queste formulazioni sono validate utilizzando solver classici, tra cui Simulated Annealing (SA) e Memetic Tabu Search (MTS), e confrontate con Programmazione Lineare Intera (ILP) e soluzioni brute-force.

Per valutare la fattibilità quantistica, gli autori impiegano l'algoritmo Bias-Field Digitized Counterdiabatic Quantum Optimization (BF-DCQO). Questo protocollo estende il DCQO standard introducendo un meccanismo di feedback iterativo che utilizza campi di bias longitudinali derivati dai risultati di misurazioni precedenti per guidare il sistema verso configurazioni a energia inferiore. Gli autori stimano i requisiti di risorse (numero di qubit, numero di porte a due qubit, profondità del circuito) e la fedeltà del circuito sotto diverse ipotesi di connettività hardware (all-to-all, heavy-hex, square-lattice) e modelli di rumore.

Contributi Chiave

• Formulazione di Modelli HUBO: Il documento fornisce formulazioni HUBO esplicite per QUEST, CVRP e la programmazione automobilistica, dimostrando come le codifiche binarie compatte riducano il numero di variabili binarie da $O(N)$ o $O(N^2)$ a $O(N \log N)$.
• Analisi del Compromesso: Il lavoro evidenzia sistematicamente il compromesso centrale: le formulazioni HUBO riducono significativamente i requisiti di qubit (scalamento dei qubit) ma introducono termini di interazione di ordine superiore che necessitano circuiti più profondi con un maggior numero di porte a due qubit.
• Analisi delle Risorse e della Scalabilità: Gli autori forniscono stime dettagliate della fedeltà del circuito e del tempo di esecuzione per BF-DCQO. Dimostrano che, sebbene HUBO riduca l'ingombro dei qubit, il decadimento esponenziale della fedeltà del circuito con l'aumento del numero di porte a due qubit costituisce un collo di bottiglia critico per i dispositivi quantistici intermedi su scala rumorosa (NISQ) attuali.
• Proposta di Flusso di Lavoro Ibrido: Per istanze su larga scala (ad esempio, programmazione automobilistica) dove l'esecuzione quantistica completa non è fattibile, il documento propone e valuta un flusso di lavoro ibrido a orizzonte rotante. Questo approccio scompone il problema globale in sottoproblemi localizzati risolvibili da solver classici o quantistici a breve termine, preservando al contempo la struttura di ordine superiore dell'obiettivo completo.

Risultati

• Validazione di QUEST e CVRP: Per istanze piccole (fino a 6 breaker/surfer per QUEST e piccole istanze CVRP), le simulazioni BF-DCQO recuperano soluzioni ottimali, validando la codifica HUBO. Tuttavia, all'aumentare delle dimensioni del problema, il rapporto di approssimazione per BF-DCQO si degrada più rapidamente rispetto al Simulated Annealing classico su HUBO quadratizzato, in linea con il rapido aumento della complessità del circuito.
• Vincoli Hardware: L'analisi rivela che per l'hardware attuale (ad esempio, IBM heavy-hex o square-lattice), le codifiche QUBO rimangono spesso più fattibili a causa di un minor numero di porte a due qubit, nonostante richiedano più qubit. Le formulazioni HUBO diventano competitive in termini di conteggio delle porte solo su architetture con connettività all-to-all (ad esempio, ioni intrappolati) e, anche in tal caso, sono limitate a istanze molto piccole (ad esempio, 4 clienti in CVRP) a causa del tempo di coerenza e dell'accumulo di errori.
• Limiti di Scalabilità: Per un'istanza rappresentativa CVRP su larga scala (100 clienti), gli autori stimano che un'implementazione fedele dei circuiti DCQO richiederebbe tassi di errore medi delle porte a due qubit inferiori a $10^{-10}$, un livello raggiungibile solo nel regime di qubit logici abilitato dalla correzione degli errori quantistici.
• Prestazioni di Programmazione: Nel caso della programmazione automobilistica, solver classici (MTS e ILP) sono stati utilizzati per confrontare la formulazione HUBO. MTS ha ridotto efficacemente le violazioni FIFO (First-In-First-Out) ma ha faticato con vincoli di gruppo di ordine superiore all'aumentare delle dimensioni del problema. L'approccio ibrido a orizzonte rotante che utilizza SA ha fornito una riduzione equilibrata sia delle violazioni locali che globali.

Significato e Affermazioni
Il documento afferma con modestia che il suo contributo principale non è la dimostrazione di un vantaggio quantistico su istanze su scala industriale, bensì una chiarificazione di quando le formulazioni di ordine superiore offrano un vantaggio rappresentativo significativo e di come tale vantaggio sia vincolato dai requisiti di risorse quantistiche.

Gli autori concludono che:

1. HUBO vs. QUBO: Le formulazioni HUBO offrono una scalabilità dei qubit superiore, rendendole potenzialmente più attraenti del QUBO in ambienti di tolleranza ai guasti iniziali dove il numero di qubit è limitato ma le fedeltà delle porte sono elevate.
2. Limitazioni Attuali: L'implementazione pratica sull'hardware NISQ attuale è vincolata dalla fedeltà delle porte, dai tempi di coerenza e dalla profondità del circuito. L'aumentato requisito di porte a due qubit di HUBO spesso supera i benefici della riduzione del numero di qubit sui dispositivi attuali.
3. Percorsi Futuri: Il contesto più plausibile per l'uso pratico di queste formulazioni è un flusso di lavoro ibrido quantistico-classico sequenziale. In questo paradigma, le routine quantistiche agiscono come passaggi di affinamento per sottoproblemi localizzati all'interno di una pipeline di ottimizzazione prevalentemente classica. Questo approccio sfrutta la scalabilità favorevole dei qubit di HUBO mitigando al contempo i tempi di esecuzione proibitivi e l'accumulo di errori associati all'ottimizzazione quantistica end-to-end, anche nei regimi di tolleranza ai guasti iniziali.

Il lavoro sottolinea che la fattibilità dell'ottimizzazione quantistica nell'industria dipende dall'allineamento della struttura del problema con le capacità hardware, suggerendo che le strategie ibride sono essenziali per colmare il divario tra i vantaggi teorici di HUBO e l'implementazione pratica.