A Hybrid Classical-Quantum Annealing Algorithm for the TSP

Dit artikel stelt een hybride klassiek-quantum-annealingalgoritme voor het Probleem van de Reisende Verkoper voor dat grafconversie gebruikt om de probleemdimensionaliteit te verminderen, waardoor een efficiënte oplossing mogelijk wordt op huidige quantumapparaten zoals de D-Wave-annealer, met prestaties die zowel door klassieke simulatie als door quantumhardware zijn gevalideerd.

De kern

Stel je voor dat je een reisagent bent die probeert de perfecte roadtrip voor een klant te plannen. Je hebt een lijst met 1.000 steden die ze willen bezoeken, en je moet de enige kortste route bepalen die elke stad precies één keer aandoet en hen weer thuisbrengt. Dit is het beroemde Reizigersprobleem (TSP).

Het probleem is dat naarmate het aantal steden groeit, het aantal mogelijke routes zo snel explodeert dat zelfs 's werelds krachtigste supercomputers vastlopen bij het proberen de absoluut beste route te vinden. Het is alsof je probeert een specifiek korreltje zand te vinden op een strand dat elke seconde groter wordt.

Dit artikel stelt een slimme "samenwerking"-strategie voor om deze puzzel op te lossen door het beste van twee werelden te combineren: klassieke computers (het soort dat we vandaag de dag gebruiken) en kwantumcomputers (het futuristische, experimentele soort).

Hier is hoe hun methode werkt, uitgelegd via eenvoudige analogieën:

1. Het Probleem: Te Veel Opties

Stel je het TSP voor als een gigantische, verwarde bal van garen. Als je probeert het hele ding in één keer uit te wikkelen, is het onmogelijk. Huidige kwantumcomputers zijn als kleine, delicate handen; ze zijn ongelooflijk krachtig maar kunnen slechts een klein stukje garen tegelijk vasthouden. Ze kunnen de hele bal van 1.000 steden niet aan, omdat ze niet genoeg "vingers" (qubits) of de juiste verbindingen hebben om alles vast te grijpen.

2. De Oplossing: Het "Zeker Ruggegraat"-Principe

Het geheime wapen van de auteurs is een techniek die Grafiekcontractie heet. Stel je voor dat je een groep van 500 verschillende reisagenten hebt, die elk hun eigen idee van een goede route voor de 1.000 steden schetsen.

• De Pool: Je verzamelt al deze 500 schetsen.
• Het Patroon: Je kijkt goed naar de kaarten. Je merkt op dat in bijna elke schets de agenten het erover eens zijn dat Stad A verbonden moet zijn met Stad B, en Stad C met Stad D. Dit zijn de "zekere" verbindingen.
• De Kortweg: In plaats van elke stad als een aparte stop te behandelen, neem je die afgesproken verbindingen en "lijm" je ze aan elkaar. Je verandert een lange keten van steden (A-B-C-D) in één enkele, supergrote "megastad".

Door dit te doen, verander je niet de bestemming; je vereenvoudigt alleen de kaart. Je kunt een probleem van 1.000 steden omzetten in een probleem van 50 steden. Dit is de contractie.

3. De Kwantumstap: Het "Magische Kompas"

Nu je de kaart hebt verkleind tot een beheersbare grootte (zeg maar 50 steden), geef je deze kleinere puzzel aan de Kwantum-Annealer (zoals de D-Wave-machine die ze gebruikten).

• Klassieke Computers lossen deze puzzels meestal op door één route te proberen, vast te lopen, en er een andere te proberen (zoals een muis in een doolhof).
• Kwantumcomputers gebruiken een fenomeen dat "kwantumtunneling" heet. Stel je voor dat het doolhof diepe valleien heeft waar de muis vastloopt. Een kwantumcomputer is als een geest dat simpelweg door de muren van de vallei kan tunnelen om de uitgang aan de andere kant te vinden.

De auteurs gebruikten een simulatie van deze kwantum "geest"-capaciteit (genaamd Path Integral Monte Carlo) om de beste route voor de kleine, gecontracteerde kaart te vinden. Omdat de kaart nu klein genoeg is, kan de kwantumcomputer dit daadwerkelijk efficiënt oplossen.

4. Het Resultaat: Het weer Samenvoegen

Zodra de kwantumcomputer de beste route voor de "megasteden" heeft gevonden, maakt het algoritme ze los en breidt het pad weer uit naar de oorspronkelijke 1.000 steden. Omdat de "gelijmde" delen de meest betrouwbare verbindingen waren die in eerste instantie werden gevonden, is de uiteindelijke route zeer dicht bij de perfecte oplossing.

Wat Vonden Ze?

Het team testte dit op reële reizen data (uit een bibliotheek genaamd TSPLIB):

• Kleine Reizen: Voor kleine groepen steden vond hun methode elke keer de perfecte route.
• Grote Reizen: Voor enorme reizen (zoals 1.000+ steden) slaagden ze erin het probleem te verkleinen tot een grootte die een kwantumcomputer aankan. De resulterende routes waren zeer goed (meestal binnen 2-4% van de perfecte afstand), wat een enorme verbetering is ten opzichte van het proberen het hele ding alleen met een kwantumcomputer op te lossen.
• De Afweging: Ze ontdekten dat als ze te veel steden aan elkaar lieten (te agressief), ze het risico liepen een fout te maken. Als ze te weinig lieten, werd de kwantumcomputer nog steeds overweldigd. Ze moesten een "Goudlokje"-drempel vinden om de beste resultaten te krijgen.

De Conclusie

Het artikel beweert niet dat dit elk reisperfectie-probleem direct oplost. In plaats daarvan toont het een praktische manier om de beperkte kwantumcomputers van vandaag te gebruiken. Door een klassieke computer te gebruiken om eerst het zware werk van het "vereenvoudigen" van de kaart te doen, kunnen ze een beheersbare puzzel aan de kwantummachine overhandigen, die vervolgens zijn speciale "tunneling"-krachten gebruikt om een bijna-perfect antwoord te vinden. Het is een hybride team waarbij de klassieke computer optreedt als de organisator, en de kwantumcomputer als de expert-oplosser voor het laatste, lastige deel.

Technische samenvatting

Technische Samenvatting: Een Hybride Klassiek-Quantum Annealing Algoritme voor het TSP

Probleemstelling

Het Probleem van de Reizende Verkoper (TSP) is een fundamenteel NP-moeilijk optimalisatieprobleem dat vereist dat de kortste Hamilton-cyclus in een volledig gewogen graaf wordt geïdentificeerd. Hoewel exacte klassieke oplossers (bijvoorbeeld Concorde) grote instanties aankunnen, kampen ze vaak met schaalbaarheidsproblemen in polynomiale tijd. Omgekeerd bieden quantumbenaderingen, met name Quantum Annealing (QA), een veelbelovend alternatief mechanisme voor thermische ruis om lokale minima te ontvluchten. Echter, huidige Noisy Intermediate-Scale Quantum (NISQ)-apparaten, zoals D-Wave annealers, ondervinden ernstige fysieke beperkingen wat betreft het aantal qubits en topologische connectiviteit. Deze beperkingen voorkomen de directe mapping van grootschalige TSP-instanties, die een dichte connectiviteit vereisen, naar bestaande Quantum Processing Units (QPUs).

Methodologie

De auteurs stellen een hybride klassiek-quantum algoritme voor dat de kloof overbrugt tussen grootschalige TSP-instanties en de huidige capaciteiten van quantumhardware. De aanpak synthetiseert twee fundamentele methodologieën: een Pad-Integral Monte Carlo (PIMC)-simulatie van quantum annealing en een subQUBO-extractiestrategie.

1. Graafcontractie via Randfrequentie

De kerninnovatie is een graafcontractietechniek die de dimensionaliteit van het oorspronkelijke probleem reduceert.

• Poolgeneratie: Het algoritme initialiseert een pool van kandidaatoplossingen ($P$) met behulp van willekeurige permutaties die worden verfijnd door Simulated Annealing (SA) met 2-opt-bewegingen.
• Identificatie van een Zeker Ruggraat: In plaats van de volledige pool te analyseren, steekt het algoritme een subset ($S$) om de frequentie van randen te berekenen die in oplossingen voorkomen. Randen die met een frequentie boven een betrouwbaarheidsthorshoud ($\tau$) voorkomen, worden geïdentificeerd als een "zeker ruggraat".
• Contractie: Deze hoogfrequente randen worden gefixeerd en de verbonden knopen worden samengevoegd tot "super-knopen". Dit transformeert de oorspronkelijke graaf $G$ in een aanzienlijk kleinere sub-TSP-instantie ($G_{sub}$). De afstandsmatrix voor het subprobleem wordt opnieuw berekend om rekening te houden met de logische samenvoeging van paden (hoofd en staart van super-knopen).

2. Hybride Optimalisatielus

Het algoritme werkt in een iteratieve lus:

1. Verfijning: Klassieke heuristieken verfijnen de oplossingspool om de betrouwbaarheid van randfrequenties te verbeteren.
2. Steekproefneming & Contractie: Een subset van oplossingen wordt gestoken om gefixeerde randen te bepalen en de graaf te contracteren.
3. Quantum Oplossing: De gereduceerde sub-TSP wordt opgelost met een quantumoplosser. In de experimenten van het artikel werd dit geïmplementeerd via:
   • Klassieke Simulatie: Pad-Integral Monte Carlo (PIMC) gebaseerd op het schema van Martoňák et al., dat de TSP mappert naar een beperkt Ising-achtig systeem met behulp van 2-opt-bewegingen als kinetische energie-operatoren.
   • Hardware-uitvoering: Directe uitvoering op een D-Wave Advantage_system 4.1 QPU.
4. Expansie & Update: De oplossing voor het subprobleem wordt teruggeëxpandeerd naar de oorspronkelijke graaf door de gefixeerde randen opnieuw in te voegen. De nieuwe tour wordt toegevoegd aan de pool en het globale beste resultaat wordt bijgewerkt als er een verbetering is gevonden.
5. Beëindiging: Het proces herhaalt zich totdat $K$ opeenvolgende iteraties geen verbetering opleveren.

Belangrijkste Bijdragen

• Schaalbaar Hybride Kader: Het artikel introduceert een methode om de qubit- en connectiviteitslimieten van NISQ-apparaten te omzeilen door grote TSP-instanties te reduceren tot maten die beheersbaar zijn door huidige hardware (bijvoorbeeld het reduceren van een instantie van 1.002 steden tot ongeveer 185 knopen).
• Integratie van PIMC en SubQUBO: Het werk combineert de theoretische belofte van PIMC-quantumtunneling (effectief voor het navigeren door complexe energielandschappen) met de praktische noodzaak van subQUBO-extractie (iteratieve probleempartitionering).
• Empirische Validatie op Hardware: De auteurs hebben het algoritme succesvol gedemonstreerd op een D-Wave quantumannealer, waarbij bleek dat de contractiestrategie toelaat dat TSP-subproblemen die anders onoplosbaar zouden zijn, direct worden ingebed.

Experimentele Resultaten

Het algoritme werd geëvalueerd op TSPLIB-instanties variërend van 14 tot 11.849 steden.

• Parametergevoeligheid:
  • Drempel ($\tau$): Het verlagen van $\tau$ verhoogt de compressie (vermindering van probleemgrootte) maar riskeert het fixeren van suboptimale randen, waardoor de optimaliteitskloof toeneemt. Een drempel van $\tau=0,75$ bood een gunstig evenwicht voor medium-instanties.
  • Poolgrootte ($N_I$) en Steekproefgrootte ($N_S$): Een poolgrootte van 500 met een steekproefgrootte van 250 (50%) leverde de beste resultaten op voor medium-tot-grote instanties, wat suggereert dat stochastische steekproefneming voorkomt dat de randselectie te deterministisch wordt.
• Prestaties versus Klassieke Baselines:
  • Voor kleine instanties (bijvoorbeeld burma14, ulysses22) vond het algoritme het globale optimum (0% kloof).
  • Voor grote instanties (bijvoorbeeld pr2392) handhaafde het algoritme een gemiddelde optimaliteitskloof onder de 4%, en presteerde het in enkele gevallen beter dan Google's OR-Tools (bijvoorbeeld rl11849 behaalde een kloof van 7,36% versus 14,58% voor OR-Tools).
• D-Wave Hardware Resultaten:
  • Bij uitvoering op de D-Wave QPU behaalde de hybride aanpak aanzienlijk betere optimaliteitskloven dan de D-Wave native BQM Hybrid-oplosser. Bijvoorbeeld, op ulysses22 behaalde de voorgestelde methode een kloof van 2,57% vergeleken met 16,88% voor de hybride oplosser, door subproblemen van slechts ongeveer 5 knopen op te lossen.
• Knelpunten:
  • De PIMC-simulatiefase werd geïdentificeerd als het primaire computatieknelpunt in de klassieke simulatie.
  • Voor zeer grote instanties (bijvoorbeeld rl11849) werd de klassieke overhead (poolinitialisatie en verfijning) dominant, goed voor ongeveer 70% van de runtime, wat suggereert dat de voordelen van quantumversnelling momenteel worden opgeheven door klassieke voorverwerkingskosten bij extreme schalen.

Betekenis en Claims

Het artikel beweert dat de hybride techniek effectief de fysieke beperkingen van huidige quantumapparaten mitigeert. Door klassieke optimalisatie te benutten om de graaf te contracteren, tonen de auteurs aan dat:

1. Haalbaarheid: Grote TSP-instanties kunnen worden gereduceerd tot een schaal die geschikt is voor inbedding in NISQ-annealers zonder de structurele integriteit te verliezen die nodig is voor oplossingen van hoge kwaliteit.
2. Potentieel voor Quantum Voordeel: Hoewel de huidige PIMC-simulatie klassiek is, is het kader ontworpen om direct aanpasbaar te zijn aan quantumhardware. De resultaten suggereren dat als de PIMC-stap op een quantumannealer zou worden uitgevoerd, de computatiekosten drastisch kunnen worden gereduceerd, wat potentieel exponentiële snelheidswinsten biedt voor de optimalisatiefase.
3. Robuustheid: De methode is robuust over variërende instantiegroottes, waarbij exacte oplossingen worden bereikt voor kleine problemen en lage optimaliteitskloven worden behouden voor grootschalige problemen waar klassieke heuristieken moeite hebben.

De auteurs concluderen dat hoewel klassieke overhead een uitdaging blijft voor massale instanties, de voorgestelde contractiestrategie de TSP succesvol binnen bereik brengt van huidige quantumannealing-technologie, waarmee de levensvatbaarheid van hybride klassiek-quantum benaderingen voor combinatorische optimalisatie wordt gevalideerd.