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

Dit artikel toont aan dat het gebruik van qudit- (gehele getal) coderingen in plaats van conventionele qubit- (binaire) coderingen voor variatiele quantumalgoritmes de benodigde middelen en de simulatietijd aanzienlijk verlaagt, terwijl het op realistische problemen voor het beheer van elektrische voertuigflotten een vergelijkbare of superieure optimalisatieprestatie bereikt.

De kern

Stel je voor dat je de manager bent van een klein wagenpark van elektrische taxi's. Je hebt elke dag twee grote taken:

1. De auto's opladen: Je moet beslissen wanneer je ze inplugt (om op te laden) of laat ze energie terugleveren aan het net (ontladen) om geld te besparen.
2. Ritten toewijzen: Je moet beslissen welke auto welke rit van een klant uitvoert.

Dit is een raadsel. Als je de verkeerde auto aan een rit toewijst, of deze op het verkeerde moment oplaadt, kun je je batterij leegrijden of de regels van het elektriciteitsnet overtreden. Dit raadsel perfect oplossen is zeer moeilijk voor computers, zeker wanneer je de regels van de kwantumfysica erbij haalt.

Dit artikel is een verslag van onderzoekers van het Honda Research Institute en de Universiteit Leiden die een simpele vraag stelden: "Maakt het uit hoe we dit raadsel vertalen naar de taal van een kwantumcomputer?"

Ze testten twee verschillende "talen" (coderingen) om te zien welke de kwantumcomputer helpt het probleem sneller en beter op te lossen.

De Twee Talen: "Qubits" versus "Qudits"

Om hun experiment te begrijpen, stel je voor dat je een lijst met ritten probeert te beschrijven aan een robot.

1. De Oude Manier: De "Qubit"-Taal (De Schakelaar)
Denk aan een lichtschakelaar. Die staat ofwel AAN of UIT.

• In deze methode gebruikten de onderzoekers een aparte lichtschakelaar voor elke mogelijke combinatie van een auto en een rit.
• Als je 3 auto's en 2 ritten hebt, heb je 6 schakelaars nodig. Staat een schakelaar AAN, dan betekent dit "Auto 1 doet Rit A". Staat hij UIT, dan doet hij het niet.
• Het Probleem: Dit creëert een enorme, rommelige kamer vol schakelaars. De computer moet miljoenen combinaties controleren, waarvan de meeste nonsens zijn (zoals "Auto 1 doet Rit A" EN "Auto 2 doet Rit A" tegelijkertijd). De computer verspill tijd aan het controleren van deze onmogelijke scenario's.

2. De Nieuwe Manier: De "Qudit"-Taal (De Meerdere-Positieknop)
Denk aan een dimmer of een draaiknop die naar veel verschillende aantallen kan wijzen, niet alleen naar 0 of 1.

• In deze methode gebruikten ze, in plaats van veel schakelaars, één draaiknop voor elke rit.
• Als de knop naar "1" wijst, betekent dit "Auto 1 doet deze rit". Wijst hij naar "2", dan betekent dit "Auto 2". Wijst hij naar "0", dan betekent dit "Geen auto doet deze rit".
• Het Voordeel: Dit is veel directer. Je hoeft niet te controleren of twee auto's om dezelfde rit vechten; de knop kan fysiek niet tegelijk naar twee auto's wijzen. Het verkleint de "kamer" die de computer moet doorzoeken.

Het Experiment: Een Wedstrijd Tegen de Tijd

De onderzoekers draaiden een simulatie van hun kwantumcomputer (een "state-vector simulatie", wat neerkomt op een perfecte, ruisvrije oefenronde) om te zien hoe deze twee talen presteerden. Ze stelden veel willekeurige scenario's op met verschillende aantallen auto's, ritten en tijdsloten.

Hier is wat ze ontdekten:

• De Zoekruimte Kromp: De "Qudit"- (knop) methode verkleinde de grootte van de zoekruimte exponentieel. Stel je voor dat je een naald in een hooiberg probeert te vinden. De Qubit-methode gaf je een hooiberg ter grootte van een berg. De Qudit-methode gaf je een hooiberg ter grootte van een schoenendoos.
• Snellere Resultaten: Omdat de "schoenendoos" zo veel kleiner was, draaide de simulatie veel sneller. De Qudit-methode had aanzienlijk minder tijd nodig om een oplossing te vinden.
• Betere Kwaliteit: Verrassend genoeg leverde de Qudit-methode niet alleen snellere resultaten op; ze vonden ook betere of gelijke oplossingen. De gevonden oplossingen lagen dichter bij het perfecte antwoord en de resultaten waren consistenter (minder "trillend" of willekeurig).
• Het "Diepe" Probleem: Ze probeerden de kwantumcomputer "harder te laten denken" door meer lagen (diepte) aan het algoritme toe te voegen. Meestal helpt harder denken. Maar hier raakte de Qubit-methode in de war en presteerde slechter naarmate deze dieper werd, waarschijnlijk omdat er te veel variabelen waren om te managen en de computer te vroeg stopte met optimaliseren. De Qudit-methode bleef stabiel en robuust, zelfs naarmate het probleem complexer werd.

De Conclusie

Het artikel concludeert dat voor problemen die betrekking hebben op het plannen en toewijzen van dingen (zoals elektrische auto's aan ritten), het gebruik van de Qudit (knop)-aanpak een veel slimmere keuze is dan de traditionele Qubit (schakelaar)-aanpak.

Het is als inpakken voor een reis:

• Qubit: Je neemt een koffer vol individuele sokken mee, één voor één, en probeert ze in een doos te krijgen. Je verspilt ruimte en tijd.
• Qudit: Je neemt een enkele, netjes opgevouwen bundel sokken mee. Dit past perfect, neemt minder ruimte in beslag en je kunt het direct pakken.

De onderzoekers suggereren dat voor realistische planningsproblemen met veel opties, het gebruik van deze "meerwaardige" kwantumknoppen (qudits) een praktische en efficiënte weg voorwaarts is, die zowel tijd als rekenkracht bespaart.

Technische samenvatting

Technische Samenvatting: Vergelijking van Qubit- en Qudit-Encoderingen voor EV-lading en Toewijzing van Ritten

Probleemstelling
Het artikel behandelt het beperkte optimalisatieprobleem van het beheren van een vloot elektrische voertuigen (EV's). Dit omvat twee gekoppelde besluitvormingsprocessen: het plannen van de bi-directionele (of uni-directionele) lading van $N_{EV}$ voertuigen over een discrete tijdsperiode $T$, en het toewijzen van deze voertuigen aan $R$ klantritten. Het doel is om de laadkosten te minimaliseren terwijl strikte operationele beperkingen worden nageleefd, waaronder limieten voor de laadtoestand (SOC) van de batterij, overlappingen van ritten, grenswaarden voor het stroomnet en de vereiste dat een voertuig niet kan laden tijdens het uitvoeren van een rit.

De kernvraag die wordt onderzocht, is hoe de keuze van de codering voor de toewijzingsvariabelen van ritten de resource-eisen en het optimalisatiegedrag beïnvloedt van Variational Quantum Algorithms (VQA's), specifiek het Quantum Approximate Optimization Algorithm (QAOA). De auteurs vergelijken twee verschillende representaties:

1. Binair (Qubit) Codering: Gebruikt één binaire variabele ($r_{n,i} \in \{0,1\}$) voor elk EV-ritpaar. Dit vereist expliciete beperkingen om te waarborgen dat elke rit door ten hoogste één EV wordt uitgevoerd en dat overlappende ritten niet aan hetzelfde voertuig worden toegewezen.
2. Integer (Qudit) Codering: Gebruikt één integer-variabele ($q_i \in \{0, \dots, N_{EV}\}$) per rit, waarbij de waarde direct het toegewezen EV specificeert (of een niet-gevoerde staat). Deze codering voldoet inherent aan de beperking "één EV per rit", waardoor de noodzaak voor expliciete binaire beperkingen op toewijzing wordt verwijderd.

Methodologie
De auteurs formuleren het probleem met QAOA. Beide coderingen gebruiken qudit-variabelen voor de laadniveaus ($l_{n,t}$), maar verschillen in de computationele basis voor rittoewijzingen.

• Hamiltoniaanconstructie: De klassieke kostenfuncties en beperkingen worden gepromoveerd tot diagonale operatoren in de computationele basis. Beperkingen (bijv. SOC-limieten, geen laden tijdens ritten) worden afgedwongen via niet-lineaire straftermen die aan de kosten-Hamiltoniaan worden toegevoegd.
• Simulatie: De studie maakt gebruik van exacte state-vector-simulaties om de algoritmen te benchmarken. Om realistische hardware-beperkingen na te bootsen, worden de verwachtingswaarden van de kostenfunctie geschat met een eindig aantal meetshots ($M=256$) in plaats van een exacte berekening.
• Optimalisatie: Een klassieke optimizer (Powell-methode) minimaliseert de kostenfunctie door de QAOA-parameters ($\gamma, \beta$) te variëren. De studie voert 10 willekeurige instanties uit voor elke probleemklasse, met 10 optimalisatiedraaien per instantie, met een vast budget van 200 interne optimizer-iteraties.
• Testgevallen: Twee probleemklassen worden geanalyseerd:
  • Bi-directionele lading: 3 EV's, 2 tijdstappen, 2 ritten, 3 laadniveaus ($d=3$).
  • Uni-directionele lading: 2 EV's, 3 tijdstappen, variërende ritten ($R=2,3,4$), 2 laadniveaus ($d=2$).

Belangrijkste Bijdragen en Resultaten
Het artikel biedt een vergelijkende analyse van de twee coderingen over verschillende metrieken:

1. Reductie van de Hilbertruimte: De integer (qudit) codering reduceert exponentieel de dimensie van de Hilbertruimte in vergelijking met de binaire (qubit) codering. De verhouding van configuraties wordt gegeven door $N_{int}/N_{bin} \approx 2^{-R N_{EV} + R \log_2(N_{EV}+1)}$. Voor de geteste instanties resulteert dit in een reductie van de zoekruimte van tienduizenden naar enkele duizenden toestanden.
2. Optimalisatieprestaties:
   • Gemiddelde Energiekloof: De qudit-codering bereikt consequent een gemiddelde energie-kloof die vergelijkbaar is met of iets beter is dan de qubit-codering.
   • Variantie: De qudit-resultaten vertonen aanzienlijk lagere variantie in energie-kloven over verschillende runs.
   • Succeskans: Het percentage runs dat het globale optimum vindt en het percentage geprobeerde haalbare toestanden zijn over het algemeen hoger of stabieler voor de qudit-codering.
3. Uitvoeringstijd en Convergentie:
   • Simulatie-uitvoeringstijd: Vanwege de kleinere Hilbertruimte vereist de qudit-codering aanzienlijk kortere simulatietijden (lineair met de circuitdiepte, maar met een veel kleinere coëfficiënt).
   • Gedrag van de Laagdiepte: Naarmate de QAOA-diepte ($L$) toeneemt, verslechtert de prestatie van de qubit-codering aanzienlijk meer dan die van de qudit-codering. De auteurs schrijven dit toe aan het toegenomen aantal variational parameters, waardoor het optimalisatielandschap moeilijker te navigeren is binnen een vast iteratiebudget. De qudit-codering is robuuster tegen voortijdige beëindiging van de klassieke optimizer.
4. Kostenlandschap: De kostenlandschappen voor de qubit-codering tonen een grotere energieschaal en hogere oscillatiefrequenties vanwege het grotere aandeel onhaalbare toestanden (die hoge strafkosten opleveren) in vergelijking met de qudit-codering.

Betekenis en Claims
Het artikel beweert dat qudit-native coderingen een praktische route bieden voor het oplossen van integer- en meerwaardige planningsproblemen in variational quantum optimalisatie. De primaire betekenis ligt in het aantonen dat het direct representeren van discrete meerwaardige variabelen via qudits, in plaats van het uitbreiden ervan naar binaire qubits, oplevert:

• Exponentiële resourcebesparingen in de dimensie van de Hilbertruimte.
• Verminderde computatie-overhead in klassieke simulaties (dienend als proxy voor representatieve complexiteit).
• Verbeterde robuustheid in het optimalisatieproces, met name in sterk beperkte regimes waar haalbare oplossingen schaars zijn.

De auteurs merken op dat hoewel de studie state-vector-simulaties gebruikt, de compacte representatie potentiële voordelen suggereert voor hardware-implementaties door de overhead van beperkingenbeheer en logische variabele-mapping te verminderen. Zij concluderen dat voor beperkte planningsproblemen de qudit-codering een superieure keuze is die de optimalisatieprestaties behoudt of verbetert terwijl de resource-eisen drastisch worden gereduceerd. Het artikel suggereert bescheiden dat toekomstig werk deze trends moet testen op grotere instanties en op daadwerkelijke quantumhardware om te verifiëren of de voordelen behouden blijven buiten simulatie.