Quantum Vehicle Routing Problem: a smart initialization strategy for ill-conditioned optimization landscapes

Technische Samenvatting: Quantum Vehicle Routing Problem met Slimme Initialisatie en Subtour-codering

Probleemdefinitie
Het Vehicle Routing Problem (VRP) is een combinatorisch optimalisatievraagstuk dat gericht is op het bepalen van optimale routes voor een vloot voertuigen om een reeks bestemmingen te bezoeken, uitgaande van en terugkerend naar een centraal depot. Het probleem is NP-hard, wat betekent dat er een exponentieel aantal operaties vereist is voor exacte klassieke oplossingen, wat de schaalbaarheid van exacte solvers voor grote instanties beperkt. Hoewel er heuristische methoden bestaan, leveren deze vaak suboptimale resultaten op. Het artikel richt zich op het oplossen van VRP met behoud van de Quantum Approximate Optimization Algorithm (QAOA) op digitale kwantumapparaten. Een specifieke uitdaging bij het coderen van VRP voor kwantumsolvers is de "subtour elimination" beperking (Vergelijking 1f), die gesloten cycli voorkomt die het depot niet bevatten. Traditionele QUBO (Quadratic Unconstrained Binary Optimization) formuleringen sluiten deze beperking vaak uit of vereisen een exponentieel aantal aanvullende binaire slack-variabelen om deze af te dwingen, wat leidt tot excessieve qubit-vereisten en complexe post-processing.

Methodologie
De auteurs stellen een QAOA-gebaseerd framework voor dat twee primaire knelpunten in kwantumoptimalisatie aanpakt: slechte parameter-initialisatie in slecht geconditioneerde landschappen en de hoge qubit-overhead die vereist is voor ongelijkheidsbeperkingen.

1. Slimme Initialisatiestrategie:
   Om het "barren plateau" fenomeen te mitigeren — waarbij gradiënten exponentieel verdwijnen met de systeemgrootte, wat de variationele training hindert — introduceren de auteurs een deterministische initialisatiestrategie. In plaats van willekeurige parameterselectie, voeren zij een grid search uit over een specifiek deel van de parameterruimte. Zij evalueren de verwachte energie $\langle\psi(\gamma, \beta)| H_C |\psi(\gamma, \beta)\rangle$ voor configuraties waar $\gamma_k = \beta_k = \alpha_d$, met $\alpha_d = d\pi/D$. De configuratie die de laagste energie oplevert, wordt geselecteerd als het startpunt voor de klassieke optimizer. Deze aanpak beoogt de training te laten beginnen nabij een laag-energetische staat, om regio's met verdwijnende gradiënten te vermijden.

2. Subtour-beperking Codering zonder Slack-variabelen:
   Voortbouwend op het werk van Montañez-Barrera et al. (2024), integreren de auteurs de subtour elimination beperking direct in de QUBO Hamiltonian zonder extra qubits te introduceren. Zij benaderen de ongelijkheidsbeperking met een tweede-orde Taylor-expansie van een exponentiële functie. Specifiek wordt de ongelijkheidsbeperking $h_S(x) \geq 0$ getransformeerd naar een gerelaxeerd optimalisatieprobleem met behulp van de benadering $e^{-h(x)} \approx e - e \cdot h(x) + \frac{e}{2}h(x)^2$. Dit resulteert in een aangepaste QUBO objectieve functie die lineaire en kwadratische termen bevat voor de subtour-beperkingen, gestuurd door hyper-parameters $\lambda_1$ en $\lambda_2$, naast de standaard Lagrange-multiplier $\lambda$ voor andere beperkingen.

Belangrijkste Bijdragen

• Nieuwe Initialisatie: Een strategie voor parameter-initialisatie die de convergentiekans verbetert en het effect van barren plateaus onder willekeurige initialisatie beperkt, bewezen effectief zelfs naarmate het aantal qubits toeneemt.
• Directe Subtour-integratie: Een coderingsmethode die subtour elimination beperkingen direct in de QAOA-optimalisatielus integreert. Dit elimineert de noodzaak voor extra slack-variabelen en de exponentiële overhead in qubit-aantal, wat een "end-to-end" kwantumoplossing mogelijk maakt.
• Hyper-parameter Afstemming: Het gebruik van Optuna om optimale hyper-parameter configuraties ($\lambda, \lambda_1, \lambda_2$) te identificeren die de QUBO-codering vormgeven, waardoor wordt gewaarborgd dat de grondtoestand van de Hamiltonian overeenkomt met de optimale haalbare oplossing.

Resultaten
De auteurs valideerden hun aanpak op ruisvrije simulatoren voor VRP-instanties met $N$ knopen variërend van 3 tot 5 en een variabel aantal voertuigen ($K$).

• Initialisatie Prestaties: Vergelijkingen met willekeurige initialisatie lieten zien dat de slimme initialisatiestrategie een consistente succeswaarschijnlijkheid behoudt over verschillende probleemklassen, terwijl willekeurige initialisatie significant lijdt onder barren plateaus naarmate $N$ toeneemt.
• Beperkingsnaleving: De voorgestelde codering loste instanties tot $N=5$ succesvol op met een hoge waarschijnlijkheid. Voor $N=3$ wordt de subtour beperking natuurlijk voldaan door andere beperkingen, maar de codering blijft geldig. Voor $N=4$ en $N=5$ concentreerden de QAOA-output waarschijnlijkheden zich scherp op de theoretisch correcte oplossingen, waardoor optimale routes effectief werden geïsoleerd van onhaalbare of suboptimale configuraties.
• Qubit Efficiëntie: De voorgestelde codering vermindert de vereiste qubit-registergrootte met $O(2^N)$ vergeleken met standaard slack-variable formuleringen, omdat het de exponentiële groei van variabelen nodig voor ongelijkheidsbeperkingen vermijdt.

Betekenis en Claims
Het artikel claimt de eerste te zijn die een effectieve, probleemgrootte-onafhankelijke initialisatie van QAOA-parameters bereikt die specifiek voor de VRP-context is ontwikkeld. Bovendien stelt het te de eerste te zijn die de directe codering van subtour ongelijkheden in de QAOA-optimalisatieroutine adopteert zonder hulp-qubits of klassieke post-processing.

De auteurs positioneren deze bijdragen als een weg vrijmaken voor het effectief oplossen van VRP-instanties met behulp van kwantumgebaseerde oplossingen. Zij argumenteren dat door gebruik te maken van ruimte-efficiënte probleemcodering en verbeterde initialisatie, kwantumoptimalisatie een levensvatbaar alternatief of aanvulling kan worden op klassieke routingmethoden, met name wanneer fouttolerante kwantumcomputers beschikbaar komen. De auteurs blijven echter bescheiden over de huidige beperkingen: de experimenten waren beperkt tot kleine instanties ($N \leq 5$) op ruisvrije simulatoren, en de conversie naar QUBO blijft sterk gevoelig voor de selectie van hyper-parameters, wat momenteel een zoekproces vereist. Zij suggereren dat toekomstig werk zich moet richten op het bepalen van algemene hyper-parameter configuraties gebaseerd op probleem-invarianten (bijv. functies van $N$ en $K$) om de aanpak verder te stroomlijnen.