Solving The Travelling Salesman Problem Using A Single Qubit

Technische Samenvatting: Het oplossen van het Handelsreizigersprobleem met behulp van een enkele qubit

Probleemstelling
Het Handelsreizigersprobleem (Travelling Salesman Problem, TSP) is een fundamenteel NP-hard combinatorisch optimalisatieprobleem dat vereist dat de kortst mogelijke route wordt geïdentificeerd die een reeks steden precies één keer bezoekt en terugkeert naar de oorsprong. Hoewel er klassieke algoritmen bestaan, schalen exacte oplossingen exponentieel met het aantal steden, en garanderen heuristische methoden geen optimaliteit. Bestaande kwantumbenaderingen, zoals die gebruikmaken van Quadratic Unconstrained Binary Optimization (QUBO) gemapt naar Ising-Hamiltonianen of fase-estimatiecircuits, zijn zeer resource-intensief. Deze vereisen doorgaans een groot aantal qubits (bijvoorbeeld duizenden fysieke qubits voor een 10-steden probleem) en kampen vaak met een lage succeswaarschijnlijkheid op de huidige ruisgevoelige hardware.

Methodologie
De auteurs stellen een algoritme voor dat een willekeurig TSP mapt op een enkele qubit, waarbij gebruik wordt gemaakt van het principe van kwantumparallelisme in plaats van verstrengeling. De kernmethodologie bestaat uit drie hoofdfasen:

1. Mapping naar een discreet Brachistochrone-probleem:
   Het TSP wordt eerst geherformuleerd als een discreet Brachistochrone-probleem. In deze klassieke analogie worden steden gerepresenteerd als punten op een 2D-vlak, en routes zijn lineaire stuksgewijze functies. Het doel is om een tijdfunctional $Q$ te minimaliseren, wat overeenkomt met de totale reisafstand. Het probleem is zodanig begrensd dat het pad moet terugkeren naar de beginstad, wat wordt gecodeerd door een extra lineair segment naar een eindpunt $F$.

2. Codering op de Bloch-bol:
   Het discrete Brachistochrone-probleem wordt gemapt op de geometrie van de Bloch-bol van een enkele qubit.

• Toestandsrepresentatie: Steden ($c_i$) worden gerepresenteerd door kwantumtoestanden $|P_{ii}\rangle$ gelegen op de evenaar van de Bloch-bol.
• Afstandscodering: De relatieve afstanden tussen steden worden gecodeerd als geometrische afstanden (geodesieken) op de bol. Tussenliggende toestanden $|P_{ij}\rangle$ worden geplaatst op geodesische curven die de equatoriale toestanden verbinden met een pool $P_0$. De hoekafstand tussen toestanden komt overeen met de Euclidische afstand tussen steden.
• Traject: Beweging tussen steden wordt bereikt via rotatie-operatoren ($U^u$ en $U^d$). Een "stap" van stad $i$ naar stad $j$ houdt een "opwaartse" rotatie in van de evenaar naar een tussenliggende toestand $|P_{ij}\rangle$ (dichter bij de pool), gevolgd door een "neerwaartse" rotatie naar de equatoriale toestand $|P_{jj}\rangle$.

3. Kwantumoptimalisatie via Superpositie:
   In tegenstelling tot een brute-force aanpak die paden sequentieel doorloopt, maakt het voorgestelde algoritme gebruik van kwantumsuperpositie om meerdere paden gelijktijdig te doorlopen.

• Creatie van superpositie: Het systeem wordt geïnitialiseerd in een toestand die overeenkomt met de startstad. Een reeks instelbare rotatie-operatoren creëert een superpositietoestand in elk niveau van de routing-grafiek, waardoor alle geldige en ongeldige paden tegelijkertijd worden verkend.
• Optimalisatie: Het algoritme maakt gebruik van optimal control-methoden, specifiek de Simultaneous Perturbation Stochastic Approximation (SPSA), om de rotatie-operatoren af te stemmen.
• Doelfunctie: Hoewel een brute-force kwantumbenadering een tijdfunctional $T$ zou kunnen minimaliseren, minimaliseert de superpositie-gebaseerde aanpak de klassieke kostenfunctie $D$ (totale afstand). Dit is noodzakelijk omdat de superpositie ook "klassiek verboden" paden bevat die geen geldige Hamiltoniaanse cycli vormen. De optimalisatie streeft ernaar de populatie van de geldige Hamiltoniaanse cyclus in de eindtoestand te maximaliseren.
• Meting en Post-verwerking: Het algoritme wordt afgesloten met een projectieve meting van de voorlaatste toestand. Via kwantumtoestandstomografie wordt de populatieverdeling geanalyseerd om het dominante pad te identificeren, wat overeenkomt met de optimale TSP-route.

Belangrijkste Resultaten
De auteurs presenteren numerieke simulaties die TSP-instanties met 4 tot 9 steden oplossen met behulp van een enkele qubit.

• Nauwkeurigheid: Voor de geteste probleemgroottes verkreeg het algoritme exacte oplossingen (approximatieverhouding $\sim 1$) voor meer dan 90% van de probleeminstanties.
• Approximatie: In gevallen waarin geen exacte oplossingen werden gevonden, behaalde het algoritme hoge approximatieverhoudingen ($\sim 0,90$).
• Resource-efficiëntie: De methode vereist slechts één qubit, een scherp contrast met bestaande kwantumalgoritmen die honderden of duizenden qubits vereisen voor vergelijkbare probleemgroottes.
• Platform-agnostisch: Het algoritme is ontworien om implementeerbaar te zijn op elk kwantumplatform dat in staat is tot hoogwaardige willekeurige qubit-rotaties en toestandstomografie, inclus overlapping van supergeleidende qubits, gevangen ionen, stikstof-vacaturecentra en Rydberg-atomen.

Betekenis en Claims
Het artikel beweert dat deze aanpak een meer resource-efficiënt en nauwkeurig alternatief biedt voor bestaande kwantumalgoritmen voor kleine tot middelgrote TSP-instanties. Door gebruik te maken van het superpositieprincipe op een enkele qubit, omzeilt de methode de noodzaak voor grootschalige verstrengeling en uitgebreide qubit-aantallen, wat een primaire flessenhals vormt voor de huidige kwantumhardware.

De auteurs bespreken een potentiële polynomiale tijdsversnelling ten opzichte van klassieke algoritmen, waarbij zij suggereren dat de kwantumparallelisme die inherent is aan de superpositie van paden een praktisch voordeel kan bieden in zowel tijd als nauwkeurigheid. Het werk positioneert het TSP niet alleen als een routingprobleem, maar als een specifieke instantie van een geconstraineerd Brachistochrone-probleem dat oplosbaar is via kwantumcontrole, wat een pad opent naar schaalbare kwantumoptimalisatie op nabije hardware (near-term devices).