Quantum Optimization Methods for the Generalized Traveling Salesman Problem

Dit artikel evalueert kwantume optimalisatiemethoden, specifiek een nieuwe QUBO-formulering voor kwantum-annealing en een beperkte QAOA-variant met een XY-mixer, voor het gegeneraliseerde reizigersprobleem, en komt tot de conclusie dat hoewel ze op kleine instanties een concurrerende oplossingskwaliteit bieden, ze momenteel aanzienlijke uitdagingen ondervinden op het gebied van haalbaarheid, schaalbaarheid en doorlooptijd in vergelijking met klassieke oplosmethoden.

De kern

Stel je voor dat je een bezorgrobot bent met een zeer specifieke taak. Je hebt een lijst met taken, maar deze taken zijn gegroepeerd in "wijken" (clusters). Je regel is simpel: je moet precies één stop bezoeken in elke wijk, en je moet dit doen in een volgorde die de meeste brandstof bespaart. Je kunt niet twee stops in dezelfde wijk bezoeken, en je kunt ook niet een hele wijk overslaan. Dit is het Algemene Reisverkopersprobleem (GTSP).

Stel je nu voor dat je deze puzzel probeert op te lossen, niet met een gewone computer, maar met een Quantumcomputer. Dit zijn futuristische machines die de vreemde regels van de fysica gebruiken (zoals op twee plaatsen tegelijk zijn) om antwoorden te vinden.

Dit artikel is een rapportcijfer over hoe goed huidige quantumcomputers deze specifieke "wijkbezorging"-puzzel kunnen oplossen. Hier is de uiteenzetting van wat de onderzoekers deden en wat ze ontdekten, met behulp van eenvoudige analogieën.

De twee quantumtools die ze probeerden

Het team testte twee verschillende "quantummotoren" om de puzzel op te lossen:

1. De Quantum Annealer (Het "Magnetische Labyrint"):
   Denk hierbij aan een marmer dat een hobbelige, complexe heuvel afrolt. De onderkant van de heuvel vertegenwoordigt de perfecte oplossing (de goedkoopste route). De machine probeert het marmer naar beneden te rollen om het laagste punt te vinden.

   • Het probleem: De heuvel zit vol met "valkuilen" (ongeldige routes). Het marmer blijft vaak steken in een ondiepe kuiltje dat eruitziet als de bodem, maar niet het echte antwoord is. De onderzoekers moesten een zeer specifieke kaart maken (een QUBO-formulering) om ervoor te zorgen dat het marmer alleen over geldige paden rolt.

2. De Gate-based QAOA (De "Draadloopster"):
   Dit is als een draadloopster die probeert het beste pad over een ravijn te vinden. Ze zet stappen (lagen van een circuit) en past haar evenwicht (parameters) aan om dichter bij het doel te komen.

   • De innovatie: De onderzoekers bouwden een speciaal "veiligheidsriem" (een XY-mixer) voor deze loopster. Deze riem dwingt de loopster om op het touw te blijven (precies één stop per wijk bezoeken) bij elke stap. Echter, ze moesten nog steeds vertrouwen op "boetesignalen" om te voorkomen dat de loopster helemaal van de kaart stapt (de verkeerde wijken bezoekt of niet-bestaande wegen).

Het "Groottebeperking"-probleem

Huidige quantumcomputers zijn als kleine rekenmachines vergeleken met de supercomputers die we vandaag de dag gebruiken. Ze hebben niet genoeg "knoppen" (qubits) om grote problemen aan te kunnen.

Om de puzzel op deze kleine machines te laten passen, bedachten de onderzoekers een voorverwerkingstruc:

• Stel je voor dat je een stad hebt met 100 wijken, maar je robot kan er maar 5 aan.
• In plaats van te proberen de hele stad op te lossen, keken ze naar elke wijk en zeiden: "Oké, welke één stop in deze wijk ligt het dichtst bij de volgende wijk?"
• Ze gooiden alle andere stops weg en hielden alleen de "beste ingang" en "beste uitgang" voor elke wijk over.
• Hierdoor werd de enorme stad verkleind tot een klein dorpje dat de quantumcomputer daadwerkelijk kon aanpakken.

Wat ze vonden (De resultaten)

De onderzoekers vergeleken hun quantumrobots met een zeer slimme, klassieke computer (een standaardalgoritme genaamd GLNS).

1. Het goede nieuws (Kleine puzzels):
Wanneer de puzzel klein was (3 tot 5 wijken), waren de quantumcomputers indrukwekkend. Ze vonden vaak de perfecte route of een route die er zeer dichtbij zat. In deze kleine scenario's presteerden ze net zo goed als de beste klassieke computers.

2. Het slechte nieuws (Groeipijnen):
Zodra de puzzel iets groter werd (meer dan 5 of 7 wijken), begonnen de quantumcomputers ernstig te worstelen.

• De "Haalbaarheid"-crash: Het grootste probleem was niet dat ze een slechte route vonden; het is dat ze vaak geen geldige route vonden. Stel je voor dat de draadloopster van het touw valt, of het marmer tegen een muur rolt.
• De "Ruis"-factor: Naarmate het probleem groeide, raakten de quantumcomputers "in de war" door ruis en beperkingen. Bij de grootste tests slaagden ze er meer dan 99% van de tijd niet in om ook maar één geldige oplossing te vinden.
• De bottleneck: De onderzoekers ontdekten dat het hoofdprobleem bemonstering is. De quantumcomputer moet heel, heel vaak proberen om een goed antwoord te krijgen. Maar naarmate de puzzel groter wordt, daalt de kans om enig geldig antwoord te krijgen binnen de toegestane tijd naar bijna nul.

Het oordeel

Het artikel concludeert dat quantumcomputers momenteel geweldig zijn voor kleine, specifieke puzzels, maar nog niet klaar zijn om grote, real-world routeplanningsproblemen op zichzelf op te lossen.

• Voor kleine taken: Ze werken goed en kunnen concurreren met klassieke computers.
• Voor grote taken: Ze falen momenteel omdat ze de oplossing niet "geldig" (haalbaar) kunnen houden naarmate het probleem complexer wordt.

De onderzoekers suggereren dat quantumcomputers in de toekomst nuttig zullen zijn voor dit soort problemen, maar dat we betere manieren nodig hebben om de computer te dwingen op het "geldige pad" te blijven zonder te crashen, en dat we grotere, minder ruisende machines nodig hebben. Tot die tijd is de "voorverwerkingstruc" de enige manier om deze problemen op de huidige quantumhardware te laten passen, maar zelfs dat heeft grenzen.

Technische samenvatting

1. Probleemdefinitie

Het artikel behandelt het Generalized Traveling Salesman Problem (GTSP), een NP-moeilijke uitbreiding van het klassieke TSP.

• Definitie: Het probleem omvat een graaf waarbij knopen zijn onderverdeeld in disjuncte clusters. Het doel is om een tour met minimale kosten te vinden die exact één knoop uit elk cluster bezoekt en terugkeert naar het startpunt.
• Toepassingen: GTSP modelleert real-world industriële scenario's zoals flexibele productieschema's, geautomatiseerde opslag/ophaling, orderpicking in magazijnen en robotbewegingsplanning (waarbij een robot één uitvoeringsvariant moet selecteren uit meerdere opties voor een reeks subtaken).
• Uitdaging: Hoewel quantumoplossingen voor het standaard TSP bestaan, zijn GTSP-formuleringen schaars. Het probleem introduceert complexe constraints (clusterselectie en -sequencing) die moeilijk zijn om te mappen naar huidige Noisy Intermediate-Scale Quantum (NISQ)-hardware vanwege beperkingen in het aantal qubits en de moeilijkheid om de haalbaarheid van oplossingen te behouden.

2. Methodologie

De auteurs stellen twee verschillende quantum-optimalisatieparadigma's voor en evalueren deze, naast een klassieke voorverwerkingsstrategie om hardwarebeperkingen te mitigeren.

A. Voorverwerking: Extended Nearest Nodes to Clusters (NN2C)

Om het beperkte aantal qubits van huidige hardware aan te pakken, breiden de auteurs het NN2C-algoritme uit om de grootte van het voorbeeld te verkleinen voordat het wordt opgelost:

• Mechanisme: Voor elk cluster selecteert het algoritme de "beste instapknoop" (die de binnenkomende afstand vanuit andere clusters minimaliseert) en de "beste uitstapknoop" (die de uitgaande afstand minimaliseert).
• Resultaat: Dit vermindert het aantal knopen per cluster tot maximaal twee, waardoor de probleemgrootte effectief wordt verkleind terwijl de clusterstructuur behouden blijft. Dit maakt het mogelijk om grotere oorspronkelijke GTSPLIB-voorbeelden te mappen naar oplosbare quantumvoorbeelden.

B. Quantum Annealing Benadering (Q-GTSP)

• Formulering: De auteurs stellen een nieuwe QUBO (Quadratic Unconstrained Binary Optimization)-codering voor met een one-hot representatie ($x_{c,i} = 1$ als knoop $i$ wordt bezocht in stap $c$).
• Constraints: De kostenfunctie wordt aangevuld met kwadratische straftermen om de volgende eisen af te dwingen:
  1. Exact één knoop bezocht per stap ($p_0$).
  2. Exact één knoop bezocht per cluster ($p_1$).
  3. Geldige overgangen tussen randen ($p_2$).
• Strafgewichting: Een specifieke straffactor $\lambda$ wordt berekend om ervoor te zorgen dat elke ongeldige oplossing strikt duurder is dan de duurste geldige oplossing, wat theoretisch garandeert dat de grondtoestand overeenkomt met een haalbare tour.
• Hardware: Uitgevoerd op de D-Wave Advantage2 QPU (Zephyr-topologie).

C. Gate-Based Benadering (C-QAOA)

• Algoritme: Een geconstrueerde variant van het Quantum Approximate Optimization Algorithm (QAOA).
• Mixer Ontwerp: In plaats van een standaard transverse-field mixer, gebruiken de auteurs een XY-mixer. Deze mixer behoudt de "one-hot" constraint (Hamming-gewicht per stap) door de quantum-evolutie te beperken tot de haalbare deelruimte van de stap-constraint.
• Constraint Handling: Waar de XY-mixer de stap-constraint intrinsiek behandelt, worden de cluster- en rand-constraints nog steeds afgedwongen via straftermen in de kosten-Hamiltoniaan.
• Initialisatie: De schakeling start in één haalbare, willekeurige one-hot-toestand in plaats van een uniforme superpositie om de schakelingsdiepte en hardware-eisen te verminderen.
• Simulatie: Gesimuleerd met Qiskit Aer (vanwege beperkte toegang tot IBM QPUs voor volledige parameteroptimalisatie), gericht op Heron-processorarchitecturen.

3. Belangrijkste Bijdragen

1. Nieuwe GTSP QUBO Codering: Een specifieke formulering gericht op het genereren van haalbare oplossingen door zorgvuldig afgestemde straftermen.
2. Geconstrueerde QAOA-pijplijn: Implementatie van een hardware-gerichte C-QAOA met behulp van een XY-mixer om stap-voor-stap haalbaarheid intrinsiek te behouden, een belangrijke stap richting constraint-preserving quantum-algoritmen.
3. Uitgebreide Voorverwerking: Een gewijzigd NN2C-algoritme dat is toegespitst op asymmetrische GTSP-voorbeelden om de probleemdimensies te verkleinen voor NISQ-apparaten.
4. Uitgebreide Benchmarking: Een directe vergelijking van quantum annealing en gate-based benaderingen met klassieke state-of-the-art oplossers (GLNS/Gurobi) op het GTSPLIB-dataset.

4. Experimentele Resultaten

De studie evalueerde de prestaties op Subsample (willekeurig geselecteerde clusters) en Preprocessed (via NN2C verkleinde) voorbeelden uit GTSPLIB.

• Kleine Voorbeelden (3–5 knopen):

  • Beide quantumbenaderingen vonden vaak optimale of near-optimale oplossingen.
  • Haalbaarheid: Quantum Annealing (Q-GTSP) toonde hoge haalbaarheidspercentages (tot 98% op gepreprocessioneerde voorbeelden). C-QAOA toonde lagere haalbaarheid (vaak <50%), maar kon nog steeds optimale oplossingen vinden in de "best-shot" analyse.
  • Vergelijking: Op zeer kleine grafieken waren quantumoplossers concurrerend met klassieke oplossers.

• Schaling en Grotere Voorbeelden (6–20+ knopen):

  • Ineenstorting van Haalbaarheid: Naarmate de voorbeeldgrootte groeide, daalde het percentage haalbare oplossingen scherp. Voor C-QAOA daalde de haalbaarheid onder 1% voor voorbeelden met 13–15 knopen. Voor Q-GTSP daalde de haalbaarheid significant na 15 knopen.
  • Oplossingskwaliteit: De gemiddelde benaderingsratio viel vaak onder de baseline van willekeurig gissen, wat aangeeft dat het merendeel van de bemonsterde shots ongeldig was of van slechte kwaliteit.
  • Hardware-grenzen:
    • Q-GTSP: Trof "embedding failures" aan op gepreprocessioneerde medium-voorbeelden waar de eisen voor logische qubits (tot 400) de capaciteit van fysieke qubits overschreden.
    • C-QAOA: Lijd aan lage bemonsteringssnelheden; 1500 shots waren onvoldoende om de exponentieel groeiende zoekruimte te bestrijken.

• Impact van Voorverwerking:

  • Voorverwerking verbeterde de haalbaarheid van de Quantum Annealing-benadering aanzienlijk, waardoor deze grotere onderliggende probleemstructuren kon hanteren.
  • Voorverwerking had een negatief of neutraal effect op C-QAOA, waarschijnlijk vanwege de toegenomen structurele complexiteit (meer clusters) die de ondiepe schakelingsdiepte ($p=1$) niet aankon.

5. Betekenis en Conclusie

• Huidige Staat: Quantum-optimalisatoren tonen veelbelovende resultaten voor kleinschalige GTSP-voorbeelden en zijn in staat om optimale oplossingen te vinden. Ze lijden echter momenteel onder slechte schaalbaarheid en lage haalbaarheidspercentages naarmate de probleemgrootte toeneemt.
• Primaire Knelpunt: De belangrijkste faalmodus is niet alleen de oplossingskwaliteit, maar het vermogen om haalbare oplossingen te genereren binnen een vast shot-budget. Constraint handling op basis van straffen (in QUBO) en ondiepe mixers (in QAOA) hebben moeite om effectief door de geconstrueerde zoekruimte te navigeren.
• Toekomstige Richtingen: De auteurs concluderen dat quantum-optimalisatie voor GTSP haalbaar moet worden, moet toekomstig werk zich richten op:
  1. Constraint Handling: Voorbijgaan aan straftermen naar intrinsieke constraint-handhaving (bijv. meer geavanceerde mixers in QAOA).
  2. Schaalbaarheid: Verbetering van de coderingsefficiëntie en het beheer van schakelingsdiepte.
  3. Hardware: Het gebruik van grotere, beter verbonden qubit-topologieën om de overhead van embedding te verminderen.

Kortom, hoewel het artikel een fundamenteel kader voor quantum GTSP vaststelt, benadrukt het dat huidige NISQ-hardware en algoritmen nog niet klaar zijn om klassieke oplossers te vervangen voor praktische, middelgrote tot grote routeplanningsproblemen zonder significante doorbraken in algoritmen voor constraint handling.