Comparing Qubit and Qudit Encodings for EV Charging and Trip Assignment Problems

Riepilogo Tecnico: Confronto tra Codifiche a Qubit e Qudit per Problemi di Ricarica VE e Assegnazione di Viaggi

Enunciato del Problema
Il documento affronta il problema di ottimizzazione vincolata della gestione di una flotta di veicoli elettrici (VE). Ciò coinvolge due processi decisionali accoppiati: la programmazione della ricarica (bi-direzionale o uni-direzionale) di $N_{EV}$ veicoli su un orizzonte temporale discreto $T$, e l'assegnazione di tali veicoli a $R$ richieste di viaggio dei clienti. L'obiettivo è minimizzare i costi di ricarica soddisfacendo vincoli operativi rigorosi, inclusi i limiti dello stato di carica (SOC) della batteria, le sovrapposizioni di viaggio, i limiti di potenza della rete e il requisito secondo cui un veicolo non può ricaricarsi mentre svolge un viaggio.

La sfida centrale investigata è come la scelta della codifica per le variabili di assegnazione del viaggio influisca sui requisiti di risorse e sul comportamento di ottimizzazione degli Algoritmi Quantistici Variazionali (VQA), in particolare l'Algoritmo Quantistico di Ottimizzazione Approssimata (QAOA). Gli autori confrontano due rappresentazioni distinte:

1. Codifica Binaria (Qubit): Utilizza una variabile binaria ($r_{n,i} \in \{0,1\}$) per ogni coppia veicolo-viaggio. Ciò richiede vincoli espliciti per garantire che ogni viaggio sia servito da al massimo un veicolo e che i viaggi sovrapposti non siano assegnati allo stesso veicolo.
2. Codifica Interi (Qudit): Utilizza una variabile intera ($q_i \in \{0, \dots, N_{EV}\}$) per viaggio, dove il valore specifica direttamente il veicolo assegnato (o uno stato di non servito). Questa codifica soddisfa intrinsecamente il vincolo "un veicolo per viaggio", eliminando la necessità di vincoli binari espliciti sull'assegnazione.

Metodologia
Gli autori formulano il problema utilizzando QAOA. Entrambe le codifiche utilizzano variabili qudit per i livelli di potenza di ricarica ($l_{n,t}$), ma differiscono nella base computazionale per le assegnazioni di viaggio.

• Costruzione dell'Hamiltoniano: Le funzioni di costo classiche e i vincoli sono promossi a operatori diagonali nella base computazionale. I vincoli (ad esempio, limiti SOC, nessuna ricarica durante i viaggi) sono imposti tramite termini di penalità non lineari aggiunti all'Hamiltoniano di costo.
• Simulazione: Lo studio impiega simulazioni esatte del vettore di stato per mettere a confronto gli algoritmi. Per imitare i limiti hardware realistici, i valori di aspettazione della funzione di costo sono stimati utilizzando un numero finito di scatti di misurazione ($M=256$) piuttosto che un calcolo esatto.
• Ottimizzazione: Un ottimizzatore classico (metodo di Powell) minimizza la funzione di costo variando i parametri QAOA ($\gamma, \beta$). Lo studio esegue 10 istanze casuali per ogni classe di problema, con 10 esecuzioni di ottimizzazione per istanza, utilizzando un budget fisso di 200 iterazioni interne dell'ottimizzatore.
• Casi di Test: Vengono analizzate due classi di problemi:
  • Ricarica bi-direzionale: 3 VE, 2 passi temporali, 2 viaggi, 3 livelli di ricarica ($d=3$).
  • Ricarica uni-direzionale: 2 VE, 3 passi temporali, viaggi variabili ($R=2,3,4$), 2 livelli di ricarica ($d=2$).

Contributi e Risultati Chiave
Il documento fornisce un'analisi comparativa delle due codifiche attraverso diverse metriche:

1. Riduzione dello Spazio di Hilbert: La codifica intera (qudit) riduce esponenzialmente la dimensione dello spazio di Hilbert rispetto alla codifica binaria (qubit). Il rapporto delle configurazioni è dato da $N_{int}/N_{bin} \approx 2^{-R N_{EV} + R \log_2(N_{EV}+1)}$. Per le istanze testate, ciò si traduce in una riduzione dello spazio di ricerca da decine di migliaia a poche migliaia di stati.
2. Prestazioni di Ottimizzazione:
   • Gap di Energia Medio: La codifica qudit raggiunge costantemente un gap di energia medio paragonabile o leggermente migliore rispetto alla codifica qubit.
   • Varianza: I risultati qudit mostrano una varianza significativamente inferiore nei gap di energia tra le diverse esecuzioni.
   • Probabilità di Successo: La frazione di esecuzioni che trovano l'ottimo globale e la frazione di stati ammissibili campionati sono generalmente più elevate o più stabili per la codifica qudit.
3. Tempo di Esecuzione e Convergenza:
   • Tempo di Esecuzione della Simulazione: A causa dello spazio di Hilbert più piccolo, la codifica qudit richiede tempi di esecuzione della simulazione sostanzialmente più brevi (lineari nella profondità del circuito ma con un coefficiente molto più piccolo).
   • Comportamento della Profondità degli Strati: All'aumentare della profondità QAOA ($L$), le prestazioni della codifica qubit degradano in modo più significativo rispetto alla codifica qudit. Gli autori attribuiscono ciò all'aumento del numero di parametri variazionali che rende il paesaggio di ottimizzazione più difficile da navigare entro un budget fisso di iterazioni. La codifica qudit è più robusta alla terminazione anticipata dell'ottimizzatore classico.
4. Paesaggio di Costo: I paesaggi di costo per la codifica qubit mostrano una scala di energia più ampia e frequenze di oscillazione più elevate a causa della frazione maggiore di stati non ammissibili (che incorrono in alti costi di penalità) rispetto alla codifica qudit.

Significato e Affermazioni
Il documento afferma che le codifiche native qudit offrono una via pratica per risolvere problemi di scheduling interi e multi-valore nell'ottimizzazione quantistica variazionale. Il significato principale risiede nel dimostrare che rappresentare variabili discrete multi-valore direttamente tramite qudit, anziché espanderle in qubit binari, produce:

• Risparmi esponenziali di risorse nella dimensione dello spazio di Hilbert.
• Riduzione dell'overhead computazionale nelle simulazioni classiche (che fungono da proxy per la complessità rappresentazionale).
• Migliorata robustezza nel processo di ottimizzazione, in particolare in regimi altamente vincolati dove le soluzioni ammissibili sono scarse.

Gli autori notano che, sebbene lo studio utilizzi simulazioni del vettore di stato, la rappresentazione compatta suggerisce potenziali benefici per le implementazioni hardware riducendo l'overhead della gestione dei vincoli e della mappatura delle variabili logiche. Concludono che per i problemi di scheduling vincolati, la codifica qudit è una scelta superiore che mantiene o migliora le prestazioni di ottimizzazione riducendo drasticamente i requisiti di risorse. Il documento suggerisce modestamente che il lavoro futuro dovrebbe testare queste tendenze su istanze più grandi e su hardware quantistico reale per verificare se i vantaggi persistono oltre la simulazione.