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

Stellen Sie sich einen Lieferfahrer vor, der eine Liste von Städten genau einmal besuchen und nach Hause zurückkehren muss, wobei das Ziel darin besteht, die kürzestmögliche Strecke zurückzulegen. Dies ist das Problem des Handlungsreisenden (Traveling Salesman Problem), ein klassisches Rätsel, das im Zentrum von Logistik, Zeitplanung und Schaltungsdesign steht. Während das Finden der perfekten Route für wenige Städte einfach ist, explodiert der Schwierigkeitsgrad, wenn die Liste wächst; für jede neu hinzugefügte Stadt vervielfacht sich die Anzahl der möglichen Routen so schnell, dass selbst die schnellsten Supercomputer Schwierigkeiten haben, das Beste zu finden. Seit Jahrzehnten blicken Wissenschaftler auf Quantencomputer – Maschinen, die die seltsamen Regeln subatomarer Teilchen nutzen, um Informationen zu verarbeiten –, um diese Rätsel schneller zu lösen. Ein großes Hindernis blieb jedoch: wie man das Problem in eine Sprache übersetzt, die der Quantencomputer versteht, ohne die Berechnung in Fehlern und unnötiger Komplexität ertrinken zu lassen.

Ein Forscher bei QuantScape Inc. hat nun einen neuen Weg demonstriert, um einen Quantencomputer durch dieses Labyrinth zu führen, und dabei erfolgreich die kürzeste Route für Karten mit bis zu zehn Städten gefunden. Die Arbeit, die auf Simulationen von Quantenhardware statt auf physischen Maschinen basiert, führt eine Methode ein, die weit weniger Quantenbits – die Basiseinheiten der Information in einem Quantencomputer – benötigt als bisherige Ansätze.ت Viel wichtiger ist, dass sie zeigt, dass ein einzener Satz von Anweisungen sich an wechselnde Straßenbedingungen anpassen kann, wie etwa Verkehr, der im Laufe des Tages variiert, ohne für jedes neue Szenario neu trainiert werden zu müssen. Die Ergebnisse legen nahe, dass Quantencomputer mit der richtigen Kodierung und den richtigen Trainingsmethoden bald Optimierungsprobleme bewältigen könnten, die derzeit noch außer Reichweite liegen, vorausgesetzt, die Hardware verbessert sich kontinuierlich.

Die Kernherausforderung liegt darin, wie das Problem für die Maschine aufgeschrieben wird. Traditionelle Methoden weisen jedem Bit eine separate Kombination aus einer Stadt und einer Position in der Route zu. Für eine Karte mit zehn Städten erfordert dieser Ansatz einundachtzig Bits und zwingt den Computer dazu, ständig ungültige Routen zu prüfen und zu verwerfen, was Zeit und Energie durch Strafen verschwendet. Die neue Studie verwendet eine andere Strategie, die von einem mathematischen System namens Lehmer-Code inspiriert ist, welches im Wesentlichen jede mögliche Route nach ihrer Ordnung in einer Liste bewertet. Diese Methode benötigt nur neunzehn Bits für zehn Städte, eine signifikante Reduktion. Durch die Verwendung dieses kompakten Codes repräsentiert jeder Zustand des Quantencomputers eine gültige Route, wodurch die Notwendigkeit von Strafprüfungen entfällt. Um die Suche effizient zu gestalten, ordneten die Forscher diese Zustände so an, dass das Umkehren eines einzelnen Bits im Code einer kleinen, logischen Änderung in der Route entspricht, was es dem Computer ermöglicht, den Lösungsraum reibungslos zu explorieren.

Um den Quantencomputer zu steuern, setzten die Forscher ein hybrides System namens „variational quantum Kolmogorov–Arnold network“ ein. Stellen Sie sich dies als eine intelligente Steuerung vor, die die Karte und die Tageszeit beobachtet und dann die Regler des Quantenschaltkreises in die richtigen Positionen dreht. Anstatt die Einstellungen für jede spezifische Karte fest zu codieren, lernt dieser Controller eine allgemeine Regel: wie man den Schaltkreis basierend auf den Entfernungen zwischen den Städten und der aktuellen Zeit anpasst. Dies ermöglicht es dem System, zeitabhängige Graphen zu handhaben, bei denen sich die Fahrzeiten ändern, wie etwa ein Stromnetz oder ein Straßennetz während der Rushhour. Der Controller wurde mit einem spezifischen Ziel trainiert: das Risiko zu minimieren, eine lange Route zu wählen. Anstatt nur nach der absoluten durchschnittlichen Länge zu suchen, konzentrierte sich das Training auf die Worst-Case-Szenarien innerhalb der obersten Prozentsätze der wahrscheinlichen Ergebnisse, um sicherzustellen, dass das Endergebnis robust und zuverlässig ist.

Der Trainingsprozess selbst war streng, um die häufige Falle zu vermeiden, in einem lokalen Minimum stecken zu bleiben – dort, wo der Computer sich mit einer „gut genug“ Antwort zufrieden gibt, anstatt die beste zu finden. Die Forscher nutzten eine mehrstufige Strategie, die mit breiten Suchen begann und sich allmählich verengte, kombiniert mit einer Technik, die die Einstellungen absichtlich „durchschüttelte“, um aus Sackgassen auszubrechen. Sie verwendeten auch eine Methode namens „Basin Hopping“, die wie ein sanftes Schütteln wirkt, um das System aus flachen Tälern im Suchraum springen zu lassen. Bei Tests auf Karten mit vier bis zehn Städten, einschließlich symmetrischer Formen und zufälliger, unebener Netzwerke, fand dieser Ansatz in jedem einzelnen Fall die perfekte Route für die kleineren Karten. Für die Zehn-Städte-Karten, die wesentlich schwieriger sind, fand die Methode die optimale Route in 112 von 120 Versuchen; die verbleibenden Fehler lagen lediglich ein Prozent unter der perfekten Distanz.

Entscheidend ist, dass die Studie mehrere alternative Ideen ausschloss, die vielversprechend erschienen sein könnten. Die Forscher testeten einen einfacheren Ansatz, der nur zehn Bits verwendet – eines für jede Stadt –, um die Position des Fahrers Schritt für Schritt zu verfolgen. Diese Methode versagte bei Karten mit sechs oder mehr Städten vollständig, da sie nicht in der Lage war, die komplexen Beziehungen zwischen aufeinanderfolgenden Stopps darzustellen. Sie verglichen ihre Ergebnisse auch mit einem Standard-Klassik-Algorithmus namens „2-opt“, der eine Route verbessert, indem er zwei Segmente vertauscht. Während 2-opt effektiv ist, lieferte der Quantenschaltkreis einen wesentlich besseren Startpunkt, und die Kombination aus beiden übertraf jede Methode allein. Die Studie bestätigte, dass der Erfolg auf der spezifischen Art und Weise der Kodierung des Problems und dem anspruchsvollen Training des Controllers beruhte, und nicht nur auf der Leistung des Quantenschaltkreises selbst.

Die Ergebnisse unterstreichen auch die Effizienz der Methode hinsichtlich der Messung. In einem echten Quantencomputer erfordert das Auslesen der Antwort viele Wiederholungen des Prozesses, um ein klares Signal zu erhalten. Die Simulationen zeigten, dass das System selbst mit nur einhundert Messungen zuverlässig die beste Route identifizieren konnte. Dies deutet darauf hin, dass, sobald physische Quantencomputer mit genügend Bits verfügbar sind, diese Methode schnelle Ergebnisse liefern kann, ohne Millionen von Wiederholungen zu benötigen. Die Forscher merkten an, dass die aktuelle Arbeit zwar auf einem klassischen Computer durchgeführt wurde, der Quantenverhalten simuliert, die Techniken jedoch darauf ausgelegt sind, auf tatsächlicher Hardware zu funktionieren. Die nächsten Schritte bestehen darin, das System unter den verrauschten Bedingungen echter Maschinen zu testen und es auf größere Karten zu skalieren, bei denen die Anzahl der möglichen Routen zu groß ist, um sie von Hand zu überprüfen.

Diese Arbeit stellt einen bedeutenden Schritt dar, um die praktische Anwendung von Quantenoptimierung zu ermöglichen. Indem sie das Kodierungsproblem gelöst und einen Controller geschaffen haben, der über verschiedene Karten und Zeiten hinweg generalisiert, haben die Forscher einen Weg aufgezeigt, wie Maschinen komplexe Routing-Probleme effizient lösen können. Die Fähigkeit, zeitabhängige Änderungen mit einem einzigen Satz von Parametern zu handhaben, ist besonders vielversprechend für reale Anwendungen, in denen die Bedingungen niemals statisch sind. Während der Weg zu einem voll funktionsfähigen Quanten-Optimizer noch andauert, bietet diese Studie einen klaren Bauplan dafür, wie man diese Maschinen trainiert, um den kürzesten Pfad durch eine komplexe Welt zu finden.