Riepilogo Tecnico: QUACOD – Ottimizzazione Quantistica tramite Discesa per Coordinate per la Pianificazione Scalabile degli Droni

1. Enunciato del Problema

Il documento affronta il Problema di Pianificazione degli Droni, un componente critico della logistica dell'ultimo miglio, in cui l'obiettivo è assegnare percorsi pre-calcolati a una flotta di droni identici per minimizzare il tempo di completamento massimo ($C_{max}$) dell'intera flotta.

I vincoli e le caratteristiche chiave del problema includono:

• Vincoli di Batteria: I droni devono ricaricarsi tra percorsi consecutivi, introducendo un tempo di ricarica ($c$) non trascurabile che impatta significativamente sul tempo totale di completamento.
• Complessità Combinatoria: Il problema è NP-difficile, correlato al Problema del Commesso Viaggiatore, con uno spazio delle soluzioni che cresce esponenzialmente all'aumentare del numero di percorsi ($n$) e droni ($q$).
• Limitazioni Hardware: L'applicazione pratica è ostacolata dai dispositivi quantistici intermedi su scala rumorosa (NISQ) attuali, che mancano del numero di qubit necessario per codificare direttamente problemi di pianificazione su larga scala nell'Annealing Quantistico o negli Algoritmi Quantistici Variazionali (VQA). Gli approcci quantistici esistenti, come QUADRO, sono limitati a istanze molto piccole (ad esempio, meno di 11 droni).

2. Metodologia: QUACOD

Gli autori propongono QUACOD (Ottimizzazione Quantistica tramite Discesa per Coordinate), un framework ibrido quantistico-classico progettato per risolvere problemi di pianificazione su larga scala in condizioni di vincoli stringenti sui qubit.

A. Formulazione del Problema e Trasformazione QUBO

Il problema di pianificazione è inizialmente modellato come una minimizzazione di $C_{max}$ soggetta a vincoli di assegnazione (ogni percorso assegnato a esattamente un drone) e vincoli di capacità. Per renderlo compatibile con l'ottimizzazione quantistica, gli autori trasformano il problema in un formato di Ottimizzazione Binaria Quadratica senza Vincoli (QUBO):

1. Gestione dei Vincoli: I vincoli di uguaglianza (assegnazione del percorso) sono convertiti in termini di penalità aggiunti alla funzione obiettivo.
2. Trasformazione dell'Obiettivo: Invece di minimizzare direttamente $C_{max}$, gli autori utilizzano un'euristica derivata dall'osservazione che minimizzare la somma delle deviazioni quadrate dei tempi di completamento individuali dei droni ($T_j$) rispetto al tempo di completamento medio ($T/q$) minimizza efficacemente $C_{max}$. Questo elimina vincoli di disuguaglianza complessi.
3. Obiettivo Finale: La funzione QUBO risultante minimizza la somma delle deviazioni quadrate di $T_j$ più la penalità per i percorsi non assegnati.

B. L'Algoritmo QUACOD

Per superare il limite della scarsità di qubit, QUACOD adatta la strategia di ottimizzazione della Discesa per Coordinate:

• Decomposizione: Invece di ottimizzare simultaneamente tutte le $n \times q$ variabili binarie, l'algoritmo seleziona iterativamente un piccolo sottoinsieme di percorsi ($N$) e droni ($Q$).
• Selezione delle Variabili: I sottoinsiemi sono scelti in modo che:
  • Il numero di variabili ($|N| \times |Q|$) non superi i qubit disponibili ($m$).
  • Il sottoinsieme includa il drone con il tempo di completamento più alto (collo di bottiglia) e il drone con il tempo di completamento più basso (sottocarico) per facilitare la ridistribuzione.
  • La selezione garantisca soluzioni non banali (almeno un percorso è attualmente assegnato a ciascun drone selezionato).
• Sottoprogramma Quantistico: Il sottoproblema selezionato viene risolto utilizzando un Variational Quantum Eigensolver (VQE) con un ansatz efficiente per l'hardware (strato singolo con rotazioni $R_y$ e entanglement $CZ$ lineare).
• Iterazione: Le variabili non selezionate vengono fissate e il processo si ripete fino alla convergenza.

C. Ansatz Efficiente per l'Hardware

Il documento impiega un ansatz VQE specifico costituito da due blocchi di rotazione $R_y$ separati da una catena lineare di porte di entanglement $CZ$. Questa scelta è dettata dalla sua compatibilità con i dispositivi NISQ e dalla sua capacità di produrre soluzioni di alta qualità con un singolo strato, evitando circuiti profondi e alti costi computazionali associati a QAOA.

3. Contributi Chiave

1. Nuovo Algoritmo: Introduzione di QUACOD, un approccio ibrido che scompone la pianificazione ad alta complessità dei droni in sottoproblemi gestibili risolvibili dall'hardware quantistico attuale.
2. Scalabilità: Dimostrazione che la discesa per coordinate può colmare il divario tra il vantaggio quantistico teorico e i limiti pratici dei dispositivi NISQ, consentendo la risoluzione di problemi significativamente più grandi rispetto a quelli gestiti dai metodi precedenti.
3. Validazione delle Prestazioni: Evidenza empirica che mostra QUACOD supera lo stato dell'arte (QUADRO) sia nella qualità della soluzione (tempi di completamento inferiori) sia nella scalabilità.
4. Efficienza Hardware: Validazione che i circuiti efficienti per l'hardware sono efficaci per l'ottimizzazione combinatoria, supportando la fattibilità di un dispiegamento quantistico a breve termine.

4. Risultati Sperimentali

Gli autori hanno valutato QUACOD utilizzando simulazioni classiche dell'hardware quantistico (Qiskit) su due dataset:

• Confronto con QUADRO (Dataset Augerat):

  • QUACOD è stato testato su sei istanze con numeri variabili di droni e percorsi.
  • Risultati: QUACOD ha costantemente trovato soluzioni con tempi di completamento massimi inferiori rispetto sia all'approccio ibrido sia a quello puramente quantistico di QUADRO.
  • Scalabilità: Mentre QUADRO non è riuscito a pianificare istanze con più di 11 droni, QUACOD ha gestito con successo istanze fino a 50 droni e 1.000 percorsi (5 volte più droni e 35 volte più percorsi rispetto ai limiti di QUADRO).

• Benchmark su Larga Scala (Dataset di Pianificazione di Macchine Parallele):

  • Gli esperimenti sono stati condotti su istanze che variavano da 200 a 3.000 percorsi e da 5 a 100 droni.
  • QUACOD ha risolto con successo la maggior parte delle istanze su larga scala utilizzando solo 20 qubit per la simulazione quantistica.
  • Limitazioni: Le due istanze più grandi (3.000 percorsi, 100 droni) hanno fallito a causa di vincoli di memoria classica (RAM) necessari per memorizzare i termini $O(n^2q^2)$ della funzione obiettivo QUBO, non a limitazioni dell'hardware quantistico.

5. Significato e Affermazioni

Il documento afferma che QUACOD rappresenta un passo significativo verso applicazioni quantistiche pratiche nell'era NISQ, in quanto:

• Superamento delle Barriere delle Risorse: Dimostra che problemi logistici complessi possono essere risolti con qubit limitati sfruttando strategie di decomposizione classica (discesa per coordinate).
• Applicabilità Pratica: Il metodo raggiunge una scalabilità superiore rispetto ai framework quantistici esistenti, rendendolo un candidato vitale per la gestione reale di flotte di droni dove le dimensioni della flotta sono elevate.
• Allineamento Hardware: Utilizzando ansatz efficienti per l'hardware, l'approccio si allinea con le capacità dei dispositivi quantistici attuali e futuri a breve termine.

Limitazioni Riconosciute

Gli autori notano modestamente diverse limitazioni:

• Lacune Teoriche: Non esistono prove teoriche formali riguardanti il tasso di convergenza o le garanzie di convergenza della specifica implementazione della discesa per coordinate utilizzata.
• Teoria VQE: Non esistono prove teoriche a supporto del vantaggio specifico del VQE rispetto ai metodi classici per questa classe di problemi di ottimizzazione; i risultati sono empirici.
• Semplificazione del Modello: Il modello di pianificazione dei droni assume droni identici e percorsi pre-calcolati, semplificando la complessità dei sistemi logistici reali che possono coinvolgere flotte eterogenee e instradamento dinamico.