⚛️ quantum physics

A Quantum Encoding of Traveling Salesperson Tours via Route Generation, Cost Phases, and a Valid-Permutation

Dit artikel presenteert een compacte kwantumberekening voor het Travelling Salesman-probleem die tours encodeert via een tijdsregister en orakels voor validiteit en kosten, maar concludeert dat de exponentieel kleine fractie van geldige tours de algehele complexiteit exponentieel blijft houden, zelfs met amplitudeversterking.

Oorspronkelijke auteurs: Alexander Johannes Stasik, Franz Georg Fuchs

Gepubliceerd 2026-03-24

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Alexander Johannes Stasik, Franz Georg Fuchs

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je een postbode bent in een grote stad met honderden straten. Je moet elke straat precies één keer bezoeken en weer terugkeren naar je startpunt, maar je wilt de kortste route vinden. Dit is het beroemde Reizende Verkoper Probleem (Traveling Salesperson Problem). Hoe meer straten er zijn, hoe meer mogelijke routes er zijn – en dat aantal groeit zo snel dat zelfs de krachtigste supercomputers er duizenden jaren voor nodig hebben om de beste route te vinden door gewoon alles na te rekenen.

De auteurs van dit artikel, Alexander en Franz, hebben een nieuwe manier bedacht om dit probleem op te lossen met een kwantumcomputer. Ze gebruiken geen traditionele rekenmethode, maar spelen met de unieke eigenschappen van kwantumdeeltjes. Hier is hoe hun idee werkt, vertaald naar alledaagse taal:

1. De "Magische Lijst" (De Kwantum Superpositie)

Stel je voor dat je een enorme lijst hebt met alle mogelijke routes die je zou kunnen nemen. In een normale computer zou je deze lijst één voor één moeten aflopen. Een kwantumcomputer kan echter alles tegelijk doen.

De auteurs bouwen een "register" (een soort digitale notitieblok) waarin ze een superpositie maken. Dit is alsof je een magische kaart hebt waarop elke mogelijke route tegelijkertijd getekend staat. Je hebt nu niet één route, maar een wolk van miljarden routes die allemaal op hetzelfde moment bestaan.

2. De "Controleur" (De Validiteits-Oracle)

Niet elke route op die magische kaart is goed. Sommige routes gaan twee keer langs dezelfde straat, of missen een straat helemaal. Die zijn onbruikbaar.

De auteurs bouwen een kwantum-controleur (een speciaal programma). Deze controleur kijkt naar elke route in die wolk en zegt:

"Is dit een geldige route waarbij elke stad precies één keer wordt bezocht?"
Zo ja, dan krijgt de route een groen lichtje (een '1').
Zo nee, dan krijgt het een rood lichtje (een '0').

Dit is als een strenge chef die elke route controleert. Als de route niet klopt, wordt hij gemarkeerd als 'fout'.

3. De "Prijsmeter" (De Kosten-Oracle)

Nu we weten welke routes geldig zijn, moeten we weten welke de goedkoopste is. De auteurs voegen een tweede magische tool toe: een prijsmeter.

Deze meter kijkt naar elke geldige route en rekent de totale afstand uit. In plaats van een getal op een scherm te tonen, verandert de prijsmeter de fase van de kwantumroute.

Denk aan een orkest. Als een route lang en duur is, spelen de muzikanten een toon die iets 'anders' klinkt (bijvoorbeeld een beetje vertraagd).
Als een route kort en goedkoop is, klinkt de toon 'schoon' en perfect.

Zo zit de informatie over de kosten nu 'verstop' in de manier waarop de kwantumgolven trillen.

Het Grote Probleem: De Naald in de Hooiberg

Hier komt de twist. Hoewel de kwantumcomputer slim is, is het probleem enorm.

Stel je hebt 10 steden. Er zijn dan 3.6 miljoen mogelijke routes, maar slechts 362.000 zijn geldig.
Stel je hebt 20 steden. Dan zijn er biljoenen mogelijke routes, maar slechts een klein fractie daarvan is geldig.

De auteurs waarschuwen: zelfs met deze slimme kwantumtechniek is het aantal geldige routes zo klein vergeleken met het totale aantal mogelijke routes, dat het vinden van de beste route nog steeds extreem moeilijk blijft. Het is alsof je in een berg van 1 miljard hooibalen moet zoeken naar één specifieke naald. De kwantumcomputer kan wel sneller zoeken dan een mens, maar omdat de berg zo enorm groot is, duurt het nog steeds heel lang.

Waarom is dit dan nuttig?

Je zou kunnen denken: "Als het nog steeds zo lang duurt, waarom doen ze dit dan?"

Een nieuwe manier van kijken: Ze tonen een heel compacte en elegante manier om het probleem in een kwantumcomputer te "pakken". Het is als het vinden van een nieuwe, efficiëntere manier om een puzzel in een doos te leggen.
Basis voor de toekomst: Hoewel de huidige methode nog niet direct een snelle oplossing biedt voor enorme steden, legt het de basis. Als er in de toekomst betere kwantum-algoritmen worden bedacht (zoals een nog slimmere manier om die naald te vinden), kunnen wetenschappers dit werk gebruiken om die nieuwe technieken toe te passen.
Kleine testen: Voor kleine steden (bijvoorbeeld 5 of 6) werkt dit prima en kan het helpen om te zien hoe kwantumcomputers met complexe problemen omgaan.

Samenvatting in één zin

De auteurs hebben een slimme manier bedacht om alle mogelijke reisroutes tegelijk in een kwantumcomputer te stoppen, ze te controleren op geldigheid en de prijs te meten, maar omdat het aantal verkeerde routes zo enorm groot is, blijft het vinden van de perfecte route nog steeds een enorme uitdaging, zelfs voor deze krachtige machines.

Het is een mooi, theoretisch stappenplan voor de toekomst van kwantumrekenen, maar nog geen magische toverstaf die het probleem vandaag al volledig oplost.

Titel en Context

Het paper beschrijft een compacte kwantumcodering voor het Reizend Verkoper Probleem (TSP). De auteurs, Alexander Johannes Stasik en Franz Georg Fuchs, presenteren een circuit-gebaseerde aanpak die tours (rondreizen) representeert als tijd-geordende sequenties van steden, in plaats van de gebruikelijke rand-gebaseerde benaderingen (zoals in QUBO-modellen).

1. Het Probleem

Het TSP is een klassiek combinatorisch optimalisatieprobleem waarbij de doelstelling is om een Hamilton-cyclus met minimale kosten te vinden die elke stad precies één keer bezoekt en terugkeert naar het startpunt.

Uitdaging: Het aantal geldige tours groeit factorieel met het aantal steden ( $n$ ), wat het probleem NP-moeilijk maakt.
Kwantumuitdaging: Hoewel kwantumalgoritmes grote zoekruimtes in superpositie kunnen representeren, is de fractie van geldige tours (permutaties) extreem klein ten opzichte van het totale aantal mogelijke toewijzingen. Dit maakt het efficiënt isoleren van de oplossing lastig.

2. Methodologie en Codering

De auteurs gebruiken een route-gebaseerde codering binnen een kwantumcircuitmodel.

Registerstructuur:
- Er is een vast start- en eindpunt (stad $n-1$ ).
- De overige $n-1$ steden worden gecodeerd in een route-register over $T = n-1$ tijdstappen.
- Elke tijdstap bevat een stadslabel, gecodeerd in $b = \lceil \log_2(n-1) \rceil$ qubits.
- Totale qubits: $O(n \log n)$ .
- De initiële staat is een uniforme superpositie van alle mogelijke labelreeksen (zowel geldig als ongeldig), bereikt via Hadamard-poorten.
Drie Kerncomponenten van het Circuit:
1. Uniforme Route-Generatie: Creëert de superpositie van alle mogelijke sequenties van steden.
2. Validiteits-Oracle ( $O_{valid}$ ):
  - Dit is een reversibele oracle die markeert of een sequentie een geldige permutatie is (d.w.z. elke niet-startstad komt precies één keer voor).
  - Implementatie: Het gebruikt pariteitscontroles voor elk stadslabel. Voor elke label $i$ wordt de frequentie geteld (via XOR-operaties op ancilla-qubits). Een multi-controlled X-poort (MCX) controleert of alle pariteiten oneven zijn (wat betekent dat elk label precies één keer voorkomt).
  - Complexiteit: Vereist $O(n^2 \log n)$ CX-poorten en T-poorten.
3. Kosten-Oracle ( $O_{cost}$ ):
  - Codeert de totale tourlengte als een fase in de kwantumtoestand: $e^{i L(x)/\Lambda}$ .
  - De kosten $L(x)$ zijn de som van de startrand, de overgangsranden tussen opeenvolgende steden, en de terugkeer-rand.
  - Implementatie: Gebruikt gecontroleerde fase-rotaties voor elke randbijdrage. De "naïeve" implementatie vereist gecontroleerde poorten voor elke mogelijke overgang.
  - Complexiteit: De naïeve implementatie heeft een gate-complexiteit van $O(n^3 \log n)$ , maar door parallelle uitvoering op disjuncte tijdstappen is de circuitdiepte $O(n^2 \log n)$ .

3. Belangrijkste Resultaten en Complexiteit

Qubit-efficiëntie: De codering vereist $O(n \log n)$ qubits, wat aanzienlijk compacter is dan sommige andere benaderingen.
Gate-complexiteit:
- Aantal CX-poorten: $O(n^3 \log n)$ .
- Aantal T-poorten: $O(n^3 (\log n + \log(1/\epsilon)))$ .
- Circuitdiepte: $O(n^2 \log n)$ (door parallelisatie).
Algoritmische Beperking:
- De fractie van geldige tours in de totale zoekruimte is $\frac{(n-1)!}{(n-1)^{n-1}}$ , wat volgens de Stirling-benadering exponentieel klein is ( $\sim e^{-(n-1)}$ ).
- Zelfs met Amplitude Amplification (zoals Grover's algoritme) om de geldige subspace te isoleren, blijft de totale complexiteit exponentieel in $n$ , omdat de succeskans exponentieel klein is.
- Het paper concludeert dat dit geen polynomiale kwantumoplossing biedt voor het TSP, maar wel een duidelijke baseline-codering.

4. Gebruik van de Toestand en Toekomstige Richtingen

De bereide toestand is ontworpen als input voor verdere verwerking:

Filteren: Eerst de geldige subspace isoleren (via amplitude amplification gebaseerd op de validiteits-oracle).
Optimalisatie: Vervolgens technieken toepassen om kortere tours te selecteren binnen de geldige subspace, zoals:
- Drempelgebaseerde amplitude amplification.
- Polynoomfiltering.
- QSVT (Quantum Singular Value Transformation): Spectrale methoden om de toestand te biasen naar lage kosten zonder expliciete projectie.

De auteurs wijzen erop dat het proberen om de volledige superpositie te biasen naar lage kosten voordat geldigheid wordt gecontroleerd inefficiënt is, omdat ongeldige routes de Hilbertruimte domineren.

5. Betekenis en Conclusie

Innovatie: Het paper biedt een expliciete, reversibele circuit-constructie die de permutatiestructuur van het TSP direct in een tijd-register encodeert. Dit is een alternatief voor de gebruikelijke rand-gecodeerde QUBO-modellen.
Praktische Toepassing: Hoewel het geen polynomiale versnelling belooft voor grote $n$ , is de codering ideaal voor kleine gesimuleerde instances en als testbed voor het combineren van orakels met geavanceerde spectrale methoden (zoals QSVT).
Toekomstig Werk: De auteurs suggereren dat verdere verbeteringen nodig zijn in de efficiëntie van de orakels (bijv. via reversibele rekenkunde of block-encoding) en het zoeken naar coderingen die een grotere fractie van geldige toestanden genereren om de complexiteit te verlagen.

Kortom, dit paper levert een solide theoretisch fundament en een concrete circuit-implementatie voor het kwantumberekenen van TSP-tours, met een eerlijke evaluatie van de huidige beperkingen door de exponentieel kleine kans op geldige oplossingen.