Quantum-Assisted Vehicle Routing: Realizing QAOA-based Approach on Gate-Based Quantum Computer

Technische Samenvatting: Kwantum-ondersteunde Voertuigrouteplanning via QAOA op Gate-Based Hardware

Probleemdefinitie
Het Vehicle Routing Problem (VRP) is een fundamentele NP-hard combinatorische optimalisatieuitdaging die centraal staat in de logistiek en het transport, waarbij het doel is om kosten (afstand, tijd, brandstof) te minimalizeren terwijl aan beperkingen zoals klantbezoeken, voertuigcapaciteit en routecontinuïteit wordt voldaan. Klassieke algoritmen hebben moeite met het vinden van optimale oplossingen voor zelfs matig grote instanties vanwege exponentiële schaling. Dit werk adresseert de uitdaging om VRP te mappen op gate-based kwantumcomputers binnen het Noisy Intermediate-Scale Quantum (NISQ) regime, waarbij specifief wordt gefocust op de beperkingen opgelegd door circuitdiepte, qubit-connectiviteit en hardware-ruis.

Methodologie
De auteurs stellen een hardware-gegrond framework voor dat de Quantum Approximate Optimization Algorithm (QAOA) integreert met een link-gebaseerde formulering van het VRP. De methodologie verloopt via de volgende stadia:

1. Probleemformulering: Het VRP wordt gemodelleerd met directionele randvariabelen ($x_{i,j}$) die vertegenwoordigen of een voertuig een verbinding tussen knopen $i$ en $j$ aflegt. In tegenstelling tot tijd-geëxpandeerde of route-volgorde formuleringen, vermijdt deze aanpak expliciete sequentievariabelen.
2. Constraint Codering: Cruciale beperkingen—flow conservatie (elke klant wordt precies één keer bezocht), depot entree/exit tellingen, en subtour eliminatie—worden direct gecodeerd in de kosten-Hamiltoniaan ($H_C$) via penalty-termen. Dit transformeert het beperkte probleem naar een Quadratic Unconstrained Binary Optimization (QUBO) probleem.
3. Hamiltoniaan Mapping: De QUBO wordt gemapt naar een Ising-Hamiltoniaan die geschikt is voor QAOA. De kosten-Hamiltoniaan bestaat uit Pauli-Z termen ($Z_i$) voor lineaire kosten en Pauli-Z interacties ($Z_i Z_j$) voor kwadratische penalties. Een standaard mixing-Hamiltoniaan ($H_M = \sum X_i$) wordt gebruikt om de oplossingsruimte te verkennen.
4. Circuit Implementatie: Het algoritme wordt geïmplementeerd op de IBM Quantum System One (Eagle r3, 127 qubits). De workflow omvat:
   • Transpilatie: Het mappen van logische qubits naar de fysieke heavy-hex lattice topologie, waarbij noodzakelijke swap-gates worden geïntroduceerd.
   • Foutmitigatie: Toepassing van dynamic decoupling (om coherentie op idle qubits te behouden) en Pauli twirling (om ruiskanalen om te zetten in specifieke signaturen).
   • Hybride Optimalisatie: Een klassieke optimizer (COBYQA) stemt iteratief de variabele parameters ($\gamma, \beta$) af om de verwachte kosten $\langle \psi | H_C | \psi \rangle$ te minimaliseren.
5. Experimentele Parameters: De studie onderzoekt de impact van penalty schaling (specifiek het instellen van penalty coëfficiënten op twee keer de som van de randgewichten) en coëfficiënt normalisatie (het begrenzen van de magnitude van Pauli-termen tot één) op de haalbaarheid van de oplossing.

Belangrijkste Bijdragen

• Directionele Rand-gebaseerde Formulering: De auteurs ontwikkelen een formulering die flow conservatie en subtour eliminatie direct in de kosten-Hamiltoniaan inbedt. Deze aanpak vermijdt de hoge qubit-overhead van tijd-geëxpandeerde formuleringen en de faculteit-complexiteit van route-volgorde formuleringen, wat het geschikter maakt voor nabije hardware.
• Volledige Hardware Pipeline: Het werk voert de volledige pipeline uit—van probleemcodering en Ising-mapping tot circuit synthese, transpilatie en executie—op echte kwantumhardware, in plaats van enkel te vertrouwen op geïdealiseerde simulaties.
• Empirische Analyse van Bottlenecks: De studie evalueert kwantitatief hoe VRP-formuleringen de qubit-aantallen en twee-qubit gate-diepte na transpilatie beïnvloeden, waarbij circuitdiepte wordt geïdentificeerd als de primaire bottleneck voor geconstreinde routeplanning op huidige supergeleidende architecturen.
• Inzichten in Parametergevoeligheid: Het onderzoek toont aan dat de haalbaarheid van de oplossing kritisch afhankelijk is van de selectie van de penalty parameters en de normalisatie van de Hamiltoniaan-coëfficiënten. Specifiek verbetert normalisatie de sampling van haalbare oplossingen voor grotere instanties (4 en 5 knopen) waar niet-genormaliseerde benaderingen falen.

Resultaten

• Succes op Kleine Schaal: Voor een 3-knopen, 2-voertuig instantie identificeerde de QAOA succesvol de optimale oplossing (bit-string 111010) met een hoge waarschijnlijkheid, waarbij alle beperkingen inclusief subtour eliminatie werden voldaan.
• Schaalbaarheidsuitdagingen: Naarmate de probleemgrootte toenam (bijv. 4- en 5-knopen instanties), groeide het aantal vereiste gates exponentieel. Een 4-knopen probleem vereiste een 14-qubit circuit met meer dan 3.000 gates, wat meer dan twee uur duurde om uit te voeren, maar onhaalbare oplossingen opleverde. Een 5-knopen probleem vereiste een 30-qubit circuit met ~30.000 gates.
• Impact van Normalisatie: Zonder coëfficiënt normalisatie slaagde het algoritme er niet in om consistent optimale routes te identificeren in de hoog-waarschijnlijkheidsregio voor 4- en 5-knopen instanties. Met normalisatie en een penalty multiplier van 1.5–2.0 verbeterde de haalbaarheidsratio van de top 1.000 gesamplede bitstrings aanzienlijk.
• Hardware Beperkingen: De studie bevestigt dat de huidige hardware-ruis en beperkte coherentietijden de executie van diepe QAOA-circuits die nodig zijn voor grotere VRP-instanties verhinderen. De top 10 gesamplede staten voor het 4-knopen probleem waren allemaal onhaalbaar zonder zorgvuldige parameter afstemming.

Significantie en Claims
Het artikel claimt significantie niet als een demonstratie van kwantumvoordeel ten opzichte van klassieke solvers voor grootschalige VRP, maar als een praktische, op hardware uitgevoerde evaluatie die de huidige beperkingen in het NISQ-tijdperk verheldert. De auteurs argumenteren dat hoewel QAOA theoretisch VRP kan oplossen, de snelle groei in circuitcomplexiteit (specifiek twee-qubit gate diepte) en ruisaccumulatie de toepassing momenteel beperken tot zeer kleine instanties.

De primaire waarde van de studie ligt in het bieden van concrete ontwerp inzichten voor toekomstige kwantumoptimalisatie:

1. Formulering Keuze: Rand-gebaseerde formuleringen zijn momenteel haalbaarder dan tijd-geëxpandeerde of route-volgorde coderingen op beschikbare hardware vanwege lagere qubit en gate vereisten.
2. Parameter Heuristieken: Coëfficiënt normalisatie en specifieke penalty schaling (ongeveer 2x de som van de randgewichten) zijn essentieel voor het terugwinnen van haalbare oplossingen voor grotere instanties.
3. Methodologische Richting: Het werk schetst dat het bevorderen van kwantumoptimalisatie voor VRP niet alleen algoritmische verbeteringen vereist, maar ook hardware-vooruitgang (hogere qubit-aantallen, lagere foutpercentages) en hybride strategieën (bijv. transfer learning van parameters, dynamische circuits) om ruis en diepte-beperkingen te mitigeren.

De auteurs concluderen dat hoewel schaalbaarheid beperkt blijft, dit werk een praktisch pad legt voor de implementatie van VRP op kwanthardware en specifieke methodologische richtingen identificeert die noodzakelijk zijn voor toekomstige vooruitgang in nabije kwantumoptimalisatie.