⚛️ quantum physics

Solving The Travelling Salesman Problem Using A Single Qubit

Diese Arbeit präsentiert einen ressourceneffizienten Quantenalgorithmus, der das Problem des Handlungsreisenden für bis zu neun Städte unter Verwendung eines einzelnen Qubits löst, indem er Quantenparallelität und optimale Kontrollmethoden auf Basis eines Quanten-Brachistochronen-Ansatzes nutzt, was eine überlegene Genauigkeit und ein potenzielles polynomiales Speed-up gegenüber bestehenden Quanten- und klassischen Methoden demonstriert.

Ursprüngliche Autoren: Kapil Goswami, Gagan Anekonda Veereshi, Peter Schmelcher, Rick Mukherjee

Veröffentlicht 2026-01-28

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Kapil Goswami, Gagan Anekonda Veereshi, Peter Schmelcher, Rick Mukherjee

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Das große Problem: Der müde Reisende

Stellen Sie sich vor, Sie sind ein fahrender Händler mit einer Karte von Städten. Ihre Aufgabe ist es, jede Stadt genau einmal zu besuchen und nach Hause zurückzukehren, aber Sie möchten dies mit der kürzestmöglichen Entfernung tun.

Dies ist das berühmte Traveling Salesman Problem (TSP) (Problem des Handlungsreisenden). Es ist ein klassisches Rätsel, das unglaublich schnell extrem schwierig wird. Wenn Sie 4 Städte haben, ist es einfach. Wenn Sie 10 haben, ist es bewältigbar. Aber wenn Sie 20 haben, ist die Anzahl der möglichen Routen so gewaltig, dass selbst die schnellsten Supercomputer der Welt länger als das Alter des Universums bräuchten, um sie alle einzeln zu überprüfen.

Der alte Quantenweg: Der „Zu viele Schlüssel“-Ansatz

Normalerweise versuchen Wissenschaftler, dieses Problem auf einem Quantencomputer zu lösen, indem sie es wie ein riesiges Schloss mit vielen Tumblern behandeln. Sie benötigen für jede Stadt und jede mögliche Verbindung einen separaten „Tumbler“ (ein Qubit).

Das Problem: Um ein Problem mit nur 9 oder 10 Städten zu lösen, benötigen bestehende Quantenmethoden hunderte oder sogar tausende Qubits.
Die Realität: Heutige Quantencomputer sind verrauscht und fragil. Sie haben Schwierigkeiten, so viele Qubits zusammen am Laufen zu halten, und scheitern oft daran, die perfekte Antwort zu finden, selbst bei kleinen Karten.

Die neue Idee: Das „Ein-Wunder“-Qubit

Dieses Paper schlägt einen radikal neuen Weg vor, das TSP unter Verwendung von nur einem einzigen Qubit (der Grundeinheit der Quanteninformation) zu lösen. Betrachten Sie dieses einzelne Qubit nicht als einen winzigen Schalter, sondern als einen magischen Kreisel, der in jede beliebige Richtung im 3D-Raum zeigen kann.

So machen sie es Schritt für Schritt möglich:

1. Die Karte ist ein Globus (Die Bloch-Sphäre)

Anstatt Städte auf einem flachen Blatt Papier einzuzeichnen, bilden die Autoren sie auf der Oberfläche einer Kugel ab (wie einen Globus).

Die Städte: Die „echten“ Städte werden entlang des Äquators dieses Globus platziert.
Die Entfernungen: Die Entfernung zwischen zwei Städten wird nicht in Meilen gemessen, sondern dadurch, wie weit man den Kreisel drehen muss, um von einem Stadtpunkt zum nächsten zu gelangen.
Das Ziel: Der Reisende muss den Kreisel von Stadt zu Stadt drehen, jeden Äquatorpunkt einmal besuchen und nach Hause zurückkehren, während er den gesamten „Drehaufwand“ minimiert.

2. Die Superpositions-Superautobahn

Auf dem alten Weg prüfen Sie Route A, dann Route B, dann Route C, nacheinander.
In dieser neuen Methode nutzen die Autoren die Quantensuperposition. Stellen Sie sich vor, der Kreisel ist ein magischer Reisender, der an mehreren Orten gleichzeitig sein kann.

Anstatt einen Pfad zu gehen, erkundet der „Kreisel“ gleichzeitig jede mögliche Route.
Es ist, als würde man tausend Entdecker gleichzeitig auf tausend verschiedenen Wegen ausschicken, aber sie sind alle derselbe Entdecker, der sich lediglich in einer „Superposition“ aller Pfade befindet.

3. Die „Brachistochrone“-Abkürzung

Das Paper nutzt ein Konzept aus der Physik namens Brachistochronen-Problem. Historisch gesehen fragt dieses: „Was ist der schnellste Weg für einen Ball, um zwischen zwei Punkten zu rollen?“

Die Autoren haben das TSP in eine Version dieses Problems verwandelt. Sie behandeln die Routenfindung als ein Wettrennen gegen die Zeit.
Sie nutzen eine Technik namens Optimale Steuerung (denken Sie an einen sehr intelligenten Autopiloten), um das einzelne Qubit sanft zu lenken und zu rotieren.
Der Autopilot passt die „Drehung“ so an, dass Pfade, die zu lang sind, sich gegenseitig auslöschen (wie bei Noise-Cancelling-Kopfhörern), während der kürzeste Pfad verstärkt wird und hervorsticht.

4. Die abschließende Prüfung

Nachdem das Qubit alle Routen gleichzeitig „bereist“ hat, messen die Wissenschaftler die endgültige Position des kreiselnden Objekts.

Sie schauen sich nicht jeden einzelnen Pfad an. Sie schauen auf das Ende der Reise.
Durch die Analyse des Endzustands können sie rückwärts arbeiten, um die gewinnende Route zu rekonstruieren.
Es ist, als würde man einem Magier bei einem Trick zusehen, bei dem er ein Kartendeck mischt, und indem man nur die letzte Karte betrachtet, kann man die exakte Reihenfolge des gesamten Decks bestimmen.

Die Ergebnisse: Was haben sie herausgefunden?

Das Team führte Computersimulationen durch, um diese „Ein-Qubit“-Methode zu testen.

Der Test: Sie lösten TSP-Rätsel mit 4 bis 9 Städten.
Der Erfolg: Bei mehr als 90 % der Probleme fand ihre Methode die perfekte, kürzeste Route.
Die Sicherheitsnetz-Funktion: In den seltenen Fällen, in denen sie nicht die perfekte Antwort fanden, erhielten sie immer noch eine sehr gute Annäherung (etwa 90 % so gut wie das Bestmögliche).
Die Effizienz: Sie erledigten all dies mit nur einem Qubit, während andere Methoden Dutzende oder Hunderte benötigt hätten.

Das Fazit

Dieses Paper behauptet nicht, das TSP für eine Million Städte von morgen zu lösen. Stattdessen beweist es ein kraftvolles Konzept: Man braucht keinen massiven Quantencomputer, um komplexe Routing-Probleme zu lösen.

Indem sie das Problem als ein Geometrie-Rätsel auf einem einzigen rotierenden Globus behandelten und die Kraft nutzten, „an vielen Orten gleichzeitig zu sein“, zeigten sie, dass ein einzelnes Qubit effizient komplexe Irrgärten navigieren kann. Es ist eine ressourcenschonendere Art, über Quantenoptimierung nachzudenken, die letztendlich auf jeder Quantenplattform aufgebaut werden könnte, die ein Qubit präzise drehen kann.

Technische Zusammenfassung: Lösung des Travelling Salesman Problems mittels eines einzelnen Qubits

Problemstellung
Das Travelling Salesman Problem (TSP) ist ein fundamentales NP-schweres kombinatorisches Optimierungsproblem, bei dem die kürzestmögliche Route identifiziert werden muss, die eine Menge von Städten genau einmal besucht und zum Ursprung zurückkehrt. Während klassische Algorithmen existieren, skalieren exakte Lösungen exponentiell mit der Anzahl der Städte, und heuristische Methoden garantieren keine Optimalität. Bestehende Quantenansätze, wie etwa jene, die quadratische unbeschränkte binäre Optimierung (QUBO) auf Ising-Hamilton-Funktionen abbilden oder Phasen-Schätzungs-Schaltkreise nutzen, sind ressourcenintensiv. Sie erfordern typischerweise eine große Anzahl von Qubits (z. B. Tausende physikalische Qubits für ein 10-Städte-Problem) und leiden oft unter geringen Erfolgswahrscheinlichkeiten auf aktueller verrauschter Hardware.

Methodik
Die Autoren schlagen einen Algorithmus vor, der ein beliebiges TSP auf ein einzelnes Qubit abbildet, indem er das Prinzip der Quantenparallelität anstelle von Verschränkung nutzt. Die Kernmethodik umfasst drei Hauptphasen:

Abbildung auf ein diskretes Brachistochronen-Problem:
Das TSP wird zunächst als endliches diskretes Brachistochronen-Problem formuliert. In dieser klassischen Analogie werden Städte als Punkte auf einer 2D-Ebene dargestellt, und Routen sind als lineare stückweise Funktionen definiert. Das Ziel ist die Minimierung eines Zeitfunktionals $Q$ , welches der gesamten Reiseentfernung entspricht. Das Problem ist so beschränkt, dass der Pfad zum Ausgangspunkt zurückkehren muss, was durch ein zusätzliches lineares Segment zu einem Endpunkt $F$ kodiert wird.
Kodierung auf der Bloch-Sphäre:
Das diskrete Brachistochronen-Problem wird auf die Geometrie der Bloch-Sphäre eines einzelnen Qubits abgebildet.

Zustandsrepräsentation: Städte ( $c_i$ ) werden als Quantenzustände $|P_{ii}\rangle$ dargestellt, die sich auf dem Äquator der Bloch-Sphäre befinden.
Distanzkodierung: Die relativen Distanzen zwischen den Städten werden als geometrische Distanzen (Geodäten) auf der Sphäre kodiert. Zwischenzustände $|P_{ij}\rangle$ werden auf Geodäten platend, die die Äquatorialzustände mit einem Pol $P_0$ verbinden. Der Winkelabstand zwischen den Zuständen entspricht der euklidischen Distanz zwischen den Städten.
Traversierung: Die Bewegung zwischen Städten erfolgt über Rotationsoperatoren ( $U^u$ und $U^d$ ). Ein „Schritt“ von Stadt $i$ zu Stadt $j$ beinhaltet eine Aufwärtsrotation („up“) vom Äquator zu einem Zwischenzustand $|P_{ij}\rangle$ (näher am Pol), gefolgt von einer Abwärtsrotation („down“) zum Äquatorialzustand $|P_{jj}\rangle$ .

Quantenoptimierung via Superposition:
Im Gegensatz zu einem Brute-Force-Ansatz, der Pfade sequenziell durchläuft, nutzt der vorgeschlagene Algorithmus die Quantensuperposition, um mehrere Pfade gleichzeitig zu traversieren.

Erzeugung der Superposition: Das System wird in einem Zustand entsprechend der Startstadt initialisiert. Eine Serie von abstimmbaren Rotationsoperatoren erzeugt einen Superpositionszustand auf jeder Ebene des Routing-Diagramms, wodurch effektiv alle gültigen und ungültigen Pfade gleichzeitig exploriert werden.
Optimierung: Der Algorithmus verwendet Methoden der optimalen Steuerung, spezifisch die Simultaneous Perturbation Stochastic Approximation (SPSA), um die Rotationsoperatoren abzustimmen.
Zielfunktion: Während ein Brute-Force-Quantenansatz ein Zeitfunktional $T$ minimieren könnte, minimiert der Superpositions-basierte Ansatz die klassische Kostenfunktion $D$ (Gesamtdistanz). Dies ist notwendig, da die Superposition auch „klassisch unzulässige“ Pfade enthält, die keine gültigen Hamiltonkreise bilden. Die Optimierung sucht nach der Maximierung der Population des gültigen Hamiltonkreises im Endzustand.
Messung und Post-Processing: Der Algorithmus schließt mit einer projektiven Messung des vorletzten Zustands ab. Durch Quantenzustandstomographie wird die Populationsverteilung analysiert, um den dominanten Pfad zu identifizieren, welcher der optimale TSP-Weg ist.

Hauptergebnisse
Die Autoren präsentieren numerische Simulationen zur Lösung von TSP-Instanzen mit 4 bis 9 Städten unter Verwendung eines einzelnen Qubits.

Genauigkeit: Für die getesteten Problemgrößen erzielte der Algorithmus exakte Lösungen (Approximationsverhältnis $\sim 1$ ) für mehr als 90 % der Probleminstanzen.
Approximation: In Fällen, in denen keine exakten Lösungen gefunden wurden, erreichte der Algorithmus hohe Approximationsverhältnisse ( $\sim 0,90$ ).
Ressourceneffizienz: Die Methode benötigt nur ein einziges Qubit, ein starker Kontrast zu bestehenden Quantenalgorithmen, die für ähnliche Problemgrößen hunderte oder tausende Qubits erfordern.
Plattformagnostik: Der Algorithmus ist so konzipiert, dass er auf jeder Quantenplattform implementierbar ist, die über hochpräzise Arbitrary-Qubit-Rotationen und Zustandstomographie verfügt, einschließlich supraleitender Qubits, gefangener Ionen, Stickstoff-Fehlstellen-Zentren und Rydberg-Atomen.

Bedeutung und Ansprüche
Das Paper behauptet, dass dieser Ansatz eine ressourceneffizientere und genauere Alternative zu bestehenden Quantenalgorithmen für kleine bis mittlere TSP-Instanzen darstellt. Durch die Nutzung des Superpositionsprinzips auf einem einzelnen Qubit umgeht die Methode die Notwendigkeit großflächiger Verschränkung und hoher Qubit-Anzahlen, was eines der primären Hindernisse aktueller Quantenhardware adressiert.

Die Autoren diskutieren einen potenziellen polynomiellen Geschwindigkeitsvorteil gegenüber klassischen Algorithmen und deuten an, dass die inhärente Quantenparallelität durch die Superposition von Pfaden einen praktischen Vorteil in Bezug auf Zeit und Genauigkeit bieten könnte. Die Arbeit positioniert das TSP nicht nur als Routing-Problem, sondern als einen spezifischen Fall eines beschränkten Brachistochronen-Problems, das mittels Quantensteuerung lösbar ist, und eröffnet damit einen Weg für skalierbare Quantenoptimierung auf Geräten der Near-Term-Ära.