Raggruppamento per l’instradamento dei veicoli tramite rilassamento quantistico sparso

Abstract degli autori

Questo articolo studia il livello di assegnazione ai cluster di una decomposizione «prima i cluster, poi gli itinerari» per il problema di pickup-and-delivery capacitated con finestre temporali (CPDPTW), anziché un’ottimizzazione binaria quadratica non vincolata (QUBO) che determina direttamente l’ordine degli itinerari. La diagonalizzazione di sottospazi basata su campioni (SQD) si riduce alla scelta del migliore tra i campioni per qualsiasi Hamiltoniana di ottimizzazione diagonale, quindi un’applicazione utile all’instradamento richiede un rilassamento non diagonale. L’ottimizzazione quantistica ad accesso casuale (QRAO) introduce questa non diagonalità codificando le variabili binarie tramite osservabili non commutanti dei codici quantistici ad accesso casuale (QRAC). I grafi dei conflitti derivati dal CPDPTW mettono in luce un ostacolo specifico dell’instradamento: gli obiettivi densi e i vincoli codificati mediante penalità vanificano la compressione QRAO. Manteniamo sparsa l’Hamiltoniana codificando solo l’obiettivo reso sparso e imponendo la fattibilità rispetto ai vincoli one-hot, di capacità e di budget temporale dei cluster mediante una procedura di correzione dopo l’arrotondamento. Non affermiamo che vi sia un vantaggio quantistico. Con una correzione rigorosa, la sola fase classica raggiunge costi prossimi all’ottimo alle dimensioni testate. Il risultato è una mappa dei regimi che mette in relazione la sparsificazione, la compressione ottenuta, la norma 1 della combinazione lineare di operatori unitari (LCU), la profondità a due qubit sull’architettura heavy-hex, la deriva del campionamento e la qualità finale dell’instradamento su Qiskit Aer, FakeTorino calibrato e IBM Heron ibm_quebec. In una griglia di valutazione di 108 righe, su hardware calibrato rispetto alla simulazione ideale, che comprende da 4 a 12 coppie di richieste di ritiro e consegna, la parte eseguita su hardware presenta un gap medio di 0,0016 e una distanza di variazione totale (TVD) media tra dispositivo e simulazione ideale pari a 0,279; un’ablazione del decoder alle dimensioni da 6 a 12 isola il segnale non diagonale.