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

Dieser Artikel zeigt, dass die Verwendung von Qudit-(Ganzzahl-)Codierungen anstelle herkömmlicher Qubit-(Binär-)Codierungen für variationelle Quantenalgorithmen den Ressourcenbedarf und die Simulationslaufzeit erheblich reduziert und gleichzeitig eine vergleichbare oder überlegene Optimierungsgüte bei realistischen Problemen des Managements von Elektrofahrzeugflotten erzielt.

Das Wesentliche

Stellen Sie sich vor, Sie sind der Manager einer kleinen Flotte von Elektro-Taxis. Sie haben jeden Tag zwei große Aufgaben zu erledigen:

1. Die Autos aufladen: Sie müssen entscheiden, wann Sie sie einstecken (zum Laden) oder ihnen erlauben, Energie zurück ins Netz zu speisen (Entladung), um Geld zu sparen.
2. Fahrten zuweisen: Sie müssen entscheiden, welches Auto die Fahrt eines Kunden übernimmt.

Dies ist ein Rätsel. Wenn Sie das falsche Auto einer Fahrt zuweisen oder es zur falschen Zeit aufladen, könnten Sie den Akku erschöpfen oder gegen die Regeln des Stromnetzes verstoßen. Dieses Rätsel perfekt zu lösen, ist für Computer sehr schwierig, insbesondere wenn man die Regeln der Quantenphysik ins Spiel bringt.

Dieser Bericht stammt von Forschern des Honda Research Institute und der Universität Leiden, die eine einfache Frage stellten: „Kommt es darauf an, wie wir dieses Rätsel in die Sprache eines Quantencomputers übersetzen?"

Sie testeten zwei verschiedene „Sprachen" (Kodierungen), um herauszufinden, welche dem Quantencomputer hilft, das Problem schneller und besser zu lösen.

Die zwei Sprachen: „Qubits" vs. „Qudits"

Um ihr Experiment zu verstehen, stellen Sie sich vor, Sie versuchen, einer Roboter eine Liste von Fahrten zu beschreiben.

1. Der alte Weg: Die „Qubit"-Sprache (Der binäre Schalter)
Stellen Sie sich einen Lichtschalter vor. Er ist entweder EIN oder AUS.

• Bei dieser Methode verwendeten die Forscher einen separaten Lichtschalter für jedes einzelne mögliche Paar aus Auto und Fahrt.
• Wenn Sie 3 Autos und 2 Fahrten haben, benötigen Sie 6 Schalter. Ist ein Schalter EIN, bedeutet das „Auto 1 übernimmt Fahrt A". Ist er AUS, tut er es nicht.
• Das Problem: Dies erzeugt einen riesigen, chaotischen Raum voller Schalter. Der Computer muss Millionen von Kombinationen prüfen, von denen die meisten Unsinn sind (wie „Auto 1 übernimmt Fahrt A" UND „Auto 2 übernimmt Fahrt A" gleichzeitig). Der Computer verschwendet Zeit damit, diese unmöglichen Szenarien zu prüfen.

2. Der neue Weg: Die „Qudit"-Sprache (Der Mehrstufen-Drehregler)
Stellen Sie sich einen Dimmer oder einen Drehregler vor, der auf viele Zahlen zeigen kann, nicht nur auf 0 oder 1.

• Bei dieser Methode verwendeten sie statt vieler Schalter einen Drehregler für jede Fahrt.
• Zeigt der Regler auf „1", bedeutet das „Auto 1 übernimmt diese Fahrt". Zeigt er auf „2", bedeutet das „Auto 2". Zeigt er auf „0", bedeutet das „Kein Auto übernimmt diese Fahrt".
• Der Vorteil: Dies ist viel direkter. Sie müssen nicht prüfen, ob zwei Autos um dieselbe Fahrt kämpfen; der Regler kann physisch nicht gleichzeitig auf zwei Autos zeigen. Er verkleinert den „Raum", den der Computer durchsuchen muss.

Das Experiment: Ein Wettlauf gegen die Zeit

Die Forscher führten eine Simulation ihres Quantencomputers durch (eine „Zustandsvektor-Simulation", die wie ein perfekter, rauschfreier Probelauf ist), um zu sehen, wie sich diese beiden Sprachen verhielten. Sie stellten viele zufällige Szenarien mit unterschiedlichen Anzahlen von Autos, Fahrten und Zeitfenstern auf.

Hier ist, was sie herausfanden:

• Der Suchraum schrumpfte: Die „Qudit"-Methode (Drehregler) reduzierte die Größe des Suchraums exponentiell. Stellen Sie sich vor, Sie versuchen, eine Nadel im Heuhaufen zu finden. Die Qubit-Methode gab Ihnen einen Heuhaufen in Berggröße. Die Qudit-Methode gab Ihnen einen Heuhaufen in Schuhkartongröße.
• Schnellere Ergebnisse: Da der „Schuhkarton" so viel kleiner war, lief die Simulation viel schneller. Die Qudit-Methode benötigte deutlich weniger Zeit, um eine Lösung zu finden.
• Bessere Qualität: Überraschenderweise lief die Qudit-Methode nicht nur schneller; sie fand bessere oder gleichwertige Lösungen. Die gefundenen Lösungen lagen näher an der perfekten Antwort, und die Ergebnisse waren konsistenter (weniger „zitternd" oder zufällig).
• Das „Tiefe"-Problem: Sie versuchten, den Quantencomputer durch Hinzufügen weiterer Schichten (Tiefe) zum Algorithmus „tiefgründiger" denken zu lassen. Normalerweise hilft tieferes Denken. Aber hier geriet die Qubit-Methode in Verwirrung und performte schlechter, je tiefer sie wurde, wahrscheinlich weil sie zu viele Variablen zu jonglieren hatte und der Computer zu früh aufhörte zu optimieren. Die Qudit-Methode blieb auch dann stabil und robust, als das Problem komplexer wurde.

Das Fazit

Die Studie kommt zu dem Schluss, dass für Probleme, die die Planung und Zuweisung von Dingen betreffen (wie Elektroautos zu Fahrten), der Qudit (Drehregler)-Ansatz eine viel klügere Wahl ist als der traditionelle Qubit (Schalter)-Ansatz.

Es ist wie beim Packen für eine Reise:

• Qubit: Sie bringen einen Koffer voller einzelner Socken, eine nach der anderen, und versuchen, sie in eine Box zu packen. Sie verschwenden Platz und Zeit.
• Qudit: Sie bringen ein einzelnes, ordentlich gefaltetes Bündel Socken mit. Es passt perfekt, nimmt weniger Platz ein, und Sie können es sofort greifen.

Die Forscher schlagen vor, dass für reale Planungsprobleme mit vielen Optionen die Verwendung dieser „mehrwertigen" Quanten-Drehregler (Qudits) ein praktischer und effizienter Weg nach vorne ist, der sowohl Zeit als auch Rechenleistung spart.

Technische Zusammenfassung

Technisches Fazit: Vergleich von Qubit- und Qudit-Codierungen für EV-Lade- und Trip-Zuordnungsprobleme

Problemstellung
Die Arbeit behandelt das eingeschränkte Optimierungsproblem des Managements einer Flotte elektrischer Fahrzeuge (EVs). Dies umfasst zwei gekoppelte Entscheidungsprozesse: die Planung des bidirektionalen (oder unidirektionalen) Ladens von $N_{EV}$ Fahrzeugen über einen diskreten Zeithorizont $T$ sowie die Zuweisung dieser Fahrzeuge zu $R$ Kunden-Trip-Anfragen. Das Ziel ist die Minimierung der Ladekosten bei Einhaltung strenger betrieblicher Randbedingungen, einschließlich der Begrenzung des Batterieladezustands (SOC), von Trip-Überlappungen, Netzleistungsbeschränkungen und der Anforderung, dass ein Fahrzeug während der Erbringung eines Trips nicht laden darf.

Die zentrale untersuchte Herausforderung besteht darin, wie die Wahl der Codierung für die Trip-Zuordnungsvariablen die Ressourcenanforderungen und das Optimierungsverhalten von Variationalen Quantenalgorithmen (VQAs), speziell dem Quantum Approximate Optimization Algorithm (QAOA), beeinflusst. Die Autoren vergleichen zwei unterschiedliche Darstellungen:

1. Binäre (Qubit-)Codierung: Verwendet eine binäre Variable ($r_{n,i} \in \{0,1\}$) für jedes EV-Trip-Paar. Dies erfordert explizite Randbedingungen, um sicherzustellen, dass jeder Trip von höchstens einem EV bedient wird und dass überlappende Trips nicht demselben Fahrzeug zugewiesen werden.
2. Ganzzahlige (Qudit-)Codierung: Verwendet eine ganzzahlige Variable ($q_i \in \{0, \dots, N_{EV}\}$) pro Trip, wobei der Wert direkt das zugewiesene EV (oder einen nicht bedienten Zustand) spezifiziert. Diese Codierung erfüllt die Bedingung „ein EV pro Trip" inhärent und macht explizite binäre Randbedingungen für die Zuweisung überflüssig.

Methodik
Die Autoren formulieren das Problem unter Verwendung von QAOA. Beide Codierungen nutzen Qudit-Variablen für die Ladeleistungsstufen ($l_{n,t}$), unterscheiden sich jedoch in der rechnerischen Basis für die Trip-Zuordnungen.

• Hamiltonian-Konstruktion: Die klassischen Kostenfunktionen und Randbedingungen werden zu diagonalen Operatoren in der rechnerischen Basis erhoben. Randbedingungen (z. B. SOC-Grenzen, kein Laden während Trips) werden durch nichtlineare Strafterme erfüllt, die zum Kosten-Hamiltonian hinzugefügt werden.
• Simulation: Die Studie verwendet exakte Zustandsvektor-Simulationen, um die Algorithmen zu bewerten. Um realistische Hardware-Beschränkungen nachzuahmen, werden die Erwartungswerte der Kostenfunktion unter Verwendung einer endlichen Anzahl von Mess-Shots ($M=256$) geschätzt, anstatt eine exakte Berechnung durchzuführen.
• Optimierung: Ein klassischer Optimierer (Powell-Methode) minimiert die Kostenfunktion durch Variation der QAOA-Parameter ($\gamma, \beta$). Die Studie führt 10 zufällige Instanzen für jede Problemklasse durch, mit 10 Optimierungsläufen pro Instanz, unter Verwendung eines festen Budgets von 200 internen Optimierer-Iterationen.
• Testfälle: Zwei Problemklassen werden analysiert:
  • Bidirektionales Laden: 3 EVs, 2 Zeitschritte, 2 Trips, 3 Ladelevel ($d=3$).
  • Unidirektionales Laden: 2 EVs, 3 Zeitschritte, variable Trips ($R=2,3,4$), 2 Ladelevel ($d=2$).

Hauptbeiträge und Ergebnisse
Die Arbeit bietet eine vergleichende Analyse der beiden Codierungen über mehrere Metriken hinweg:

1. Reduktion des Hilbert-Raums: Die ganzzahlige (Qudit-)Codierung reduziert die Dimension des Hilbert-Raums im Vergleich zur binären (Qubit-)Codierung exponentiell. Das Verhältnis der Konfigurationen wird durch $N_{int}/N_{bin} \approx 2^{-R N_{EV} + R \log_2(N_{EV}+1)}$ gegeben. Für die getesteten Instanzen ergibt dies eine Reduktion des Suchraums von Zehntausenden auf einige Tausend Zustände.
2. Optimierungsleistung:
   • Mittlere Energielücke: Die Qudit-Codierung erzielt konsistent eine mittlere Energielücke, die mit der Qubit-Codierung vergleichbar oder leicht besser ist.
   • Varianz: Die Qudit-Ergebnisse weisen eine signifikant geringere Varianz in den Energielücken über verschiedene Läufe hinweg auf.
   • Erfolgswahrscheinlichkeit: Der Anteil der Läufe, die das globale Optimum finden, und der Anteil der gesampelten zulässigen Zustände sind für die Qudit-Codierung im Allgemeinen höher oder stabiler.
3. Laufzeit und Konvergenz:
   • Simulationslaufzeit: Aufgrund des kleineren Hilbert-Raums erfordert die Qudit-Codierung erheblich kürzere Simulationslaufzeiten (linear in der Schaltungstiefe, jedoch mit einem deutlich kleineren Koeffizienten).
   • Verhalten der Schichtentiefe: Mit zunehmender QAOA-Tiefe ($L$) verschlechtert sich die Leistung der Qubit-Codierung signifikant stärker als die der Qudit-Codierung. Die Autoren führen dies auf die erhöhte Anzahl variationaler Parameter zurück, die die Optimierungslandschaft innerhalb eines festen Iterationsbudgets schwerer navigierbar machen. Die Qudit-Codierung ist robuster gegenüber einem vorzeitigen Abbruch des klassischen Optimierers.
4. Kostenlandschaft: Die Kostenlandschaften für die Qubit-Codierung zeigen einen größeren Energieskalenbereich und höhere Oszillationsfrequenzen aufgrund des größeren Anteils an unzulässigen Zuständen (die hohe Strafkosten verursachen) im Vergleich zur Qudit-Codierung.

Bedeutung und Behauptungen
Die Arbeit behauptet, dass Qudit-native Codierungen einen praktischen Weg zur Lösung ganzzahliger und mehrwertiger Planungsprobleme in der variationalen Quantenoptimierung bieten. Die primäre Bedeutung liegt darin zu demonstrieren, dass die direkte Darstellung diskreter mehrwertiger Variablen durch Qudits, anstatt deren Expansion in binäre Qubits, folgende Vorteile bietet:

• Exponentielle Ressourceneinsparungen in der Dimension des Hilbert-Raums.
• Reduzierter Rechenaufwand in klassischen Simulationen (als Proxy für die Repräsentationskomplexität).
• Verbesserte Robustheit im Optimierungsprozess, insbesondere in stark eingeschränkten Regimen, in denen zulässige Lösungen selten sind.

Die Autoren weisen darauf hin, dass die Studie zwar Zustandsvektor-Simulationen verwendet, die kompakte Darstellung jedoch potenzielle Vorteile für Hardware-Implementierungen nahelegt, indem sie den Aufwand für die Handhabung von Randbedingungen und die logische Variablenzuordnung reduziert. Sie schließen, dass für eingeschränkte Planungsprobleme die Qudit-Codierung eine überlegene Wahl ist, die die Optimierungsleistung beibehält oder verbessert und gleichzeitig die Ressourcenanforderungen drastisch reduziert. Die Arbeit schlägt bescheiden vor, dass zukünftige Arbeiten diese Trends an größeren Instanzen und auf echter Quantenhardware testen sollten, um zu verifizieren, ob die Vorteile über die Simulation hinaus bestehen bleiben.