Solving the traveling salesman problem on $\lceil \log_2 (N-1)! \rceil$ qubits with a variational quantum Kolmogorov--Arnold network: exact-gradient CVaR training and generalization over time-dependent graphs

Stel je een bezorger voor die precies één keer elke stad op een lijst moet bezoeken en vervolgens weer naar huis moet terugkeren, met als doel de kortst mogelijke afstand af te leggen. Dit is het handelsreizigersprobleem, een klassieke puzzel die zich in het hart van logistiek, planning en circuitontwerp bevindt. Hoewel het vinden van de perfecte route voor een paar steden eenvoudig is, explodeert de moeilijkheid naarmate de lijst groeit; voor elke nieuwe stad toegevoegd wordt, vermenigvuldigt het aantal mogelijke routes zo snel dat zelfs de snelste supercomputers vastlopen bij het proberen te vinden van de beste route. Decennialang hebben wetenschappers gekeken naar quantumcomputers, machines die de vreemde regels van subatomaire deeltjes gebruiken om informatie te verwerken, om deze puzzels sneller op te lossen. Echter, een grote hindernis bleef bestaan: hoe vertaal je het probleem naar een taal die de quantumcomputer begrijpt zonder de berekening te laten verdrinken in fouten en onnodige complexiteit.

Een onderzoeker bij QuantScape Inc. heeft nu een nieuwe manier gedemonstreerd om een quantumcomputer door dit doolhof te leiden, waarbij succesvol de kortste route voor kaarten met tot tien steden is gevonden. Het werk, dat steunt op simulaties van quantumhardware in plaats van fysieke machines, introduceert een methode die veel minder quantum bits gebruikt — de basisunits van informatie in een quantumcomputer — dan eerdere benaderingen. Belangrijker nog is dat het aantoont dat een enkele set instructies kan aanpassen aan veranderende verkeersomstandigheden, zoals verkeer dat gedurende de dag varieert, zonder dat er voor elk nieuw scenario opnieuw getraind hoeft te worden. De resultaten suggereren dat quantumcomputers met de juiste codering en trainingsmethoden binnenkort optimalisatieproblemen zouden kunnen aanpakken die momenteel buiten bereik liggen, mits de hardware blijft verbeteren.

De kern van de uitdaging ligt in de manier waarop het probleem voor de machine wordt opgeschreven. Traditionele methoden wijzen een aparte quantum bit toe aan elke mogelijke combinatie van een stad en een positie in de route. Voor een kaart met tien steden vereist deze aanpak drieëntachtig bits, en dwingt het de computer om constant ongeldige routes te controleren en te verwerpen, wat tijd en energie verspilt aan boetes (penalties). De nieuwe studie gebruikt een andere strategie, geïnspireerd door een wiskundig systeem genaamd de Lehmer-code, die in feite elke mogelijke route rangschikt op basis van de volgorde in een lijst. Deze methode vereist slechts negentien bits voor tien steden, een significante reductie. Door deze compacte code te gebruiken, vertegenwoordigt elke mogelijke staat van de quantumcomputer een geldige route, waardoor de noodzaak voor controle op boetes vervalt. Om de zoektocht efficiënt te maken, hebben de onderzoekers deze staten zo gerangschikt dat het omdraaien van een enkele bit in de code overeenkomt met een kleine, logische verandering in de route, waardoor de computer de oplossingsruimte soepel kan verkennen.

Om de quantumcomputer te begeleiden, gebruikten de onderzoekers een hybride systeem genaamd een variational quantum Kolmogorov–Arnold network. Denk aan dit als een slimme controller die de kaart en het tijdstip van de dag in de gaten houdt, en vervolgens de knoppen van de quantumcircuit op de juiste posities zet. In plaats van de instellingen voor elke specifieke kaart hard te coderen, leert deze controller een algemene regel: hoe de circuit aan te passen op basis van de afstanden tussen de steden en de huidige tijd. Dit stelt het systeem in staat om tijd-afhankelijke grafen te verwerken, waarbij reistijden veranderen, zoals een elektriciteitsnet of een wegennetwerk tijdens de ochtendspits. De controller werd getraind met een specifiek doel: het minimaliseren van het risico op het kiezen van een lange route. In plaats van alleen te kijken naar de absolute gemiddelde lengte, richtte de training zich op de worst-case scenario's binnen de top paar procent van de waarschijnlijke uitkomsten, om ervoor te zorgen dat het eindresultaat robuust en betrouwbaar is.

Het trainingsproces zelf was rigoureus, ontworpen om de veelvoorkomende valkuil te vermijden van vastlopen in een lokaal minimum, waar de computer genoegen neemt met een "goed genoeg" antwoord in plaats van het beste antwoord. De onderzoekers gebruikten een meerstapsstrategie die begon met brede zoektochten en geleidelijk de focus vernauwde, gecombineerd met een techniek die doelbewust de instellingen opschudde om uit doodlopende wegen te ontsnappen. Ze gebruikten ook een methode genaamd basin hopping, wat werkt als een zachte schudbeweging om het systeem uit ondiepe dalen te helpen springen in het zoeklandschap. Wanneer getest op kaarten met vier tot tien steden, inclusief zowel symmetrische vormen als willekeurige, onregelmatige netwerken, vond deze aanpak de perfecte route in elk geval voor de kleinere kaarten. Voor de kaarten met tien steden, die aanzienlijk moeilijker zijn, vond de methode de optimale route in 112 van de 120 pogingen, waarbij de resterende mislukkingen slechts één procent afweek van de perfecte afstand.

Cruciaal is dat de studie verschillende alternatieve ideeën die veelbelovend leken, heeft uitgesloten. De onderzoekers testten een simpelere aanpak die slechts tien bits gebruikt, één voor elke stad, om de positie van de bestuurder stap voor stap te volgen. Deze methode faalde volledig voor kaarten met zes of meer steden omdat het niet in staat was de complexe relaties tussen opeenvolgende stops te representeren. Ze vergeleken hun resultaten ook met een standaard klassiek algoritme bekend als 2-opt, dat een route verbetert door twee segmenten te wisselen. Hoewel 2-opt effectief is, bood het quantumcircuit een veel beter startpunt, en de combinatie van beide presteerde beter dan elk van de methoden alleen. De studie bevestigde dat het succes voortkwam uit de specifieke manier waarop het probleem werd gecodeerd en de geavanceerde training van de controller, en niet alleen uit de kracht van het quantumcircuit zelf.

De bevindingen benadrukken ook de efficiëntie van de methode met betrekking tot meting. In een echte quantumcomputer vereist het uitlezen van het antwoord het herhalen van het proces vele malen om een duidelijk signaal te krijgen. De simulaties toonden aan dat zelfs met slechts honderd metingen het systeem betrouwbaar de beste route kan identificeren. Dit suggereert dat wanneer fysieke quantumcomputers met voldoende bits beschikbaar komen, deze methode resultaten snel kan leveren zonder dat miljoenen herhalingen nodig zijn. De onderzoekers merkten op dat hoewel het huidige werk werd uitgevoerd op een klassieke computer die quantumgedrag simuleert, de technieken zijn ontworpen om op werkelijke hardware te werken. De volgende stappen omvatten het testen van het systeem onder de ruisige omstandigheden van echte machines en het opschalen naar grotere kaarten waar het aantal mogelijke routes te groot is om met de hand te controleren.

Dit werk vormt een belangrijke stap voorwaarts in het praktisch maken van quantumoptimalisatie. Door het encoding-probleem op te lossen en een controller te creëren die generaliseert over verschillende kaarten en tijden, hebben de onderzoekers een pad getoond naar machines die complexe routeringsproblemen efficiënt kunnen oplossen. Het vermogen om tijd-afhankelijke veranderingen met een enkele set parameters te verwerken, is bijzonder veelbelovend voor real-world toepassingen waar omstandigheden nooit statisch zijn. Hoewel de reis naar een volledig functionele quantumoptimizer nog gaande is, biedt deze studie een duidelijk blauwdruk voor hoe we deze machines kunnen trainen om de kortste weg door een complexe wereld te vinden.