Quantum Optimization Methods for the Generalized Traveling Salesman Problem

Diese Arbeit bewertet Quantenoptimierungsmethoden, insbesondere eine neuartige QUBO-Formulierung für Quanten-Annealing und eine eingeschränkte QAOA-Variante mit einem XY-Mischer, für das verallgemeinerte Traveling-Salesman-Problem und stellt fest, dass diese zwar auf kleinen Instanzen eine wettbewerbsfähige Lösungsqualität bieten, jedoch im Vergleich zu klassischen Lösern derzeit erhebliche Herausforderungen hinsichtlich der Durchführbarkeit, Skalierbarkeit und Laufzeit bewältigen müssen.

Das Wesentliche

Stellen Sie sich vor, Sie sind ein Lieferroboter mit einer sehr spezifischen Aufgabe. Sie haben eine Liste von Aufgaben zu erledigen, die jedoch in „Stadtteile" (Cluster) gruppiert sind. Ihre Regel ist einfach: Sie müssen genau einen Halt in jedem Stadtteil besuchen, und zwar in einer Reihenfolge, die den meisten Kraftstoff spart. Sie können nicht zwei Halte im selben Stadtteil besuchen und dürfen auch keinen Stadtteil vollständig auslassen. Dies ist das Generalized Traveling Salesman Problem (GTSP).

Stellen Sie sich nun vor, Sie versuchen, dieses Rätsel nicht mit einem herkömmlichen Computer, sondern mit einem Quantencomputer zu lösen. Dies sind futuristische Maschinen, die die seltsamen Gesetze der Physik (wie das gleichzeitige Befinden an zwei Orten) nutzen, um Antworten zu finden.

Dieser Bericht ist ein Zeugnis dafür, wie gut aktuelle Quantencomputer dieses spezifische „Stadtteil-Liefer"-Rätsel lösen können. Hier ist die Aufschlüsselung dessen, was die Forscher taten und was sie fanden, unter Verwendung einfacher Analogien.

Die zwei Quantenwerkzeuge, die sie versuchten

Das Team testete zwei verschiedene „Quantenmotoren", um das Rätsel zu lösen:

1. Der Quanten-Annealer (Das „Magnet-Labyrinth"):
   Stellen Sie sich dies als einen Murmel vor, der einen hügeligen, komplexen Hang hinunterrollt. Der Fuß des Hügels repräsentiert die perfekte Lösung (die günstigste Route). Die Maschine versucht, den Murmel hinunterrollen zu lassen, um den tiefsten Punkt zu finden.

   • Das Problem: Der Hügel ist voller „Fallen" (ungültige Routen). Der Murmel bleibt oft in einer flachen Mulde stecken, die wie der Boden aussieht, aber nicht die eigentliche Antwort ist. Die Forscher mussten eine sehr spezifische Karte erstellen (eine QUBO-Formulierung), um sicherzustellen, dass der Murmel nur auf gültigen Pfaden rollt.

2. Der Gate-basierte QAOA (Der „Seiltänzer"):
   Dies ist wie ein Seiltänzer, der versucht, den besten Weg über eine Schlucht zu finden. Er macht Schritte (Schichten eines Schaltkreises) und passt sein Gleichgewicht (Parameter) an, um dem Ziel näher zu kommen.

   • Die Innovation: Die Forscher bauten einen speziellen „Sicherheitsgurt" (einen XY-Mixer) für diesen Tänzer. Dieser Gurt zwingt den Tänzer, bei jedem Schritt auf dem Seil zu bleiben (genau einen Halt pro Stadtteil zu besuchen). Dennoch mussten sie sich auf „Strafschilder" verlassen, um zu verhindern, dass der Tänzer komplett von der Karte abkommt (falsche Stadtteile besucht oder nicht existierende Straßen nimmt).

Das Problem der „Größenbegrenzung"

Aktuelle Quantencomputer sind wie kleine Taschenrechner im Vergleich zu den Supercomputern, die wir heute verwenden. Sie haben nicht genug „Tasten" (Qubits), um große Probleme zu bewältigen.

Um das Rätsel auf diese kleinen Maschinen zu passen, erfanden die Forscher einen Vorverarbeitungs-Trick:

• Stellen Sie sich vor, Sie haben eine Stadt mit 100 Stadtteilen, aber Ihr Roboter kann nur 5 bewältigen.
• Anstatt die ganze Stadt zu lösen, betrachteten sie jeden Stadtteil und sagten: „Okay, welcher eine Halt in diesem Stadtteil ist dem nächsten Stadtteil am nächsten?"
• Sie warfen alle anderen Halte weg und behielten nur den „besten Einstieg" und den „besten Ausstieg" für jeden Stadtteil.
• Dies schrumpfte die riesige Stadt auf ein winziges Dorf zusammen, das der Quantencomputer tatsächlich bewältigen konnte.

Was sie fanden (Die Ergebnisse)

Die Forscher verglichen ihre Quantenroboter mit einem sehr intelligenten, klassischen Computer (einem Standardalgorithmus namens GLNS).

1. Die gute Nachricht (kleine Rätsel):
Wenn das Rätsel klein war (3 bis 5 Stadtteile), waren die Quantencomputer beeindruckend. Sie fanden oft die perfekte Route oder eine Route, die ihr sehr nahe kam. In diesen winzigen Szenarien schnitten sie genauso gut ab wie die besten klassischen Computer.

2. Die schlechte Nachricht (Wachstumsschmerzen):
Sobald das Rätsel etwas größer wurde (mehr als 5 oder 7 Stadtteile), begannen die Quantencomputer stark zu kämpfen.

• Der „Durchführbarkeits"-Crash: Das größte Problem war nicht, dass sie eine schlechte Route fanden; es war, dass sie oft überhaupt keine gültige Route fanden. Stellen Sie sich vor, der Seiltänzer fällt vom Seil oder der Murmel rollt gegen eine Wand.
• Der „Rauschen"-Faktor: Mit wachsendem Problem wurden die Quantencomputer durch Rauschen und Einschränkungen „verwirrt". Bei den größten Tests scheiterten sie in mehr als 99 % der Fälle daran, überhaupt eine einzige gültige Lösung zu finden.
• Die Engpass: Die Forscher stellten fest, dass das Hauptproblem das Sampling ist. Der Quantencomputer muss sehr, sehr oft versuchen, eine gute Antwort zu erhalten. Aber je größer das Rätsel wird, desto mehr sinkt die Chance, innerhalb der verfügbaren Zeit irgendeine gültige Antwort zu erhalten, auf nahezu Null.

Das Urteil

Der Bericht kommt zu dem Schluss, dass Quantencomputer zwar derzeit großartig für kleine, spezifische Rätsel sind, aber noch nicht bereit sind, große, reale Routing-Probleme allein zu lösen.

• Für kleine Jobs: Sie funktionieren gut und können mit klassischen Computern konkurrieren.
• Für große Jobs: Sie scheitern derzeit, weil sie die Lösung nicht „gültig" (durchführbar) halten können, sobald das Problem komplex wird.

Die Forscher schlagen vor, dass Quantencomputer für diese Art von Problem in der Zukunft nützlich sein sollen, wir bessere Wege benötigen, um den Computer dazu zu zwingen, auf dem „gültigen Pfad" zu bleiben, ohne abzustürzen, und wir größere, weniger verrauschte Maschinen benötigen. Bis dahin ist der „Vorverarbeitungs-Trick" der einzige Weg, um diese Probleme auf die heutige Quantenhardware zu passen, aber selbst das hat Grenzen.

Technische Zusammenfassung

1. Problemdefinition

Das Paper behandelt das Generalized Traveling Salesman Problem (GTSP), eine NP-schwere Erweiterung des klassischen TSP.

• Definition: Das Problem umfasst einen Graphen, dessen Knoten in disjunkte Cluster partitioniert sind. Das Ziel ist es, eine Tour minimaler Kosten zu finden, die genau einen Knoten aus jedem Cluster besucht und zum Ursprung zurückkehrt.
• Anwendungen: GTSP modelliert reale industrielle Szenarien wie flexible Fertigungsplanung, automatisierte Lagerung/Entnahme, Kommissionierung in Lagern und robotische Bewegungsplanung (wobei ein Roboter für eine Folge von Teilaufgaben genau eine Ausführungsvariante aus mehreren Optionen auswählen muss).
• Herausforderung: Während es Quantenlösungen für das Standard-TSP gibt, sind GTSP-Formulierungen selten. Das Problem führt komplexe Einschränkungen ein (Clusterauswahl und -sequenzierung), die aufgrund von Qubit-Beschränkungen und der Schwierigkeit, die Lösungsfeasibility aufrechtzuerhalten, nur schwer auf aktuelle Noisy Intermediate-Scale Quantum (NISQ)-Hardware abgebildet werden können.

2. Methodik

Die Autoren schlagen und evaluieren zwei unterschiedliche Quantenoptimierungsparadigmen vor, ergänzt durch eine klassische Vorverarbeitungsstrategie zur Minderung von Hardwarebeschränkungen.

A. Vorverarbeitung: Extended Nearest Nodes to Clusters (NN2C)

Um die begrenzte Qubit-Anzahl aktueller Hardware zu adressieren, erweitern die Autoren den NN2C-Algorithmus, um die Instanzgröße vor der Lösung zu reduzieren:

• Mechanismus: Für jedes Cluster wählt der Algorithmus den „besten Eintrittsknoten" (minimiert die eingehende Distanz von anderen Clustern) und den „besten Austrittsknoten" (minimiert die ausgehende Distanz).
• Ergebnis: Dies reduziert die Anzahl der Knoten pro Cluster auf maximal zwei und verkleinert die Problemgröße effektiv, während die Clusterstruktur erhalten bleibt. Dies ermöglicht es, größere ursprüngliche GTSPLIB-Instanzen auf lösbare Quanteninstanzen abzubilden.

B. Quanten-Annealing-Ansatz (Q-GTSP)

• Formulierung: Die Autoren schlagen eine neuartige QUBO (Quadratic Unconstrained Binary Optimization)-Codierung vor, die eine One-Hot-Darstellung verwendet ($x_{c,i} = 1$, wenn Knoten $i$ im Schritt $c$ besucht wird).
• Einschränkungen: Die Kostenfunktion wird um quadratische Strafterme erweitert, um Folgendes durchzusetzen:
  1. Genau ein Knoten pro Schritt besucht ($p_0$).
  2. Genau ein Knoten pro Cluster besucht ($p_1$).
  3. Gültige Kantentransitionen ($p_2$).
• Strafgewichtung: Ein spezifischer Straffaktor $\lambda$ wird berechnet, um sicherzustellen, dass jede ungültige Lösung strikt teurer ist als die teuerste gültige Lösung, was theoretisch garantiert, dass der Grundzustand einer zulässigen Tour entspricht.
• Hardware: Ausgeführt auf dem Advantage2 QPU von D-Wave (Zephyr-Topologie).

C. Gate-basierter Ansatz (C-QAOA)

• Algorithmus: Eine eingeschränkte Variante des Quantum Approximate Optimization Algorithm (QAOA).
• Mixer-Design: Anstelle eines Standard-Transversalfeld-Mixers verwenden die Autoren einen XY-Mixer. Dieser Mixer erhält die „One-Hot"-Einschränkung (Hamming-Gewicht schrittweise) durch Beschränkung der Quantenentwicklung auf den zulässigen Unterraum der Schritteinschränkung.
• Umgang mit Einschränkungen: Während der XY-Mixer die Schritteinschränkung intrinsisch handhabt, werden die Cluster- und Kanteinschränkungen weiterhin über Strafterme im Kosten-Hamiltonian durchgesetzt.
• Initialisierung: Der Schaltkreis startet in einem einzelnen zulässigen zufälligen One-Hot-Zustand statt in einer gleichmäßigen Superposition, um die Schaltungstiefe und Hardwareanforderungen zu reduzieren.
• Simulation: Simuliert mit Qiskit Aer (aufgrund begrenzten Zugangs zu IBM QPUs für die vollständige Parameteroptimierung), mit Zielrichtung auf Heron-Prozessorarchitekturen.

3. Hauptbeiträge

1. Neuartige GTSP-QUBO-Codierung: Eine spezifische Formulierung, die darauf abzielt, durch sorgfältig abgestimmte Strafterme zulässige Lösungen zu generieren.
2. Eingeschränkter QAOA-Pipeline: Implementierung einer hardwareorientierten C-QAOA unter Verwendung eines XY-Mixers, um die schrittweise Zulässigkeit intrinsisch zu erhalten – ein bedeutender Schritt hin zu einschränkungserhaltenden Quantenalgorithmen.
3. Erweiterte Vorverarbeitung: Ein modifizierter NN2C-Algorithmus, der auf asymmetrische GTSP-Instanzen zugeschnitten ist, um die Problemdimensionen für NISQ-Geräte zu reduzieren.
4. Umfassendes Benchmarking: Ein direkter Vergleich von Quanten-Annealing- und gate-basierten Ansätzen mit klassischen State-of-the-Art-Lösern (GLNS/Gurobi) auf dem GTSPLIB-Datensatz.

4. Experimentelle Ergebnisse

Die Studie bewertete die Leistung an Subsample-Instanzen (zufällig ausgewählte Cluster) und vorverarbeiteten (via NN2C reduzierten) Instanzen aus GTSPLIB.

• Kleine Instanzen (3–5 Knoten):

  • Beide Quantenansätze fanden häufig optimale oder nahezu optimale Lösungen.
  • Zulässigkeit: Quanten-Annealing (Q-GTSP) zeigte hohe Zulässigkeitsraten (bis zu 98 % bei vorverarbeiteten Instanzen). C-QAOA zeigte niedrigere Zulässigkeit (oft <50 %), konnte aber in der „Best-Shot"-Analyse dennoch optimale Lösungen finden.
  • Vergleich: Bei sehr kleinen Graphen waren Quantenlöser mit klassischen Lösern konkurrenzfähig.

• Skalierung und größere Instanzen (6–20+ Knoten):

  • Zusammenbruch der Zulässigkeit: Mit wachsender Instanzgröße sank der Anteil zulässiger Lösungen drastisch. Bei C-QAOA fiel die Zulässigkeit bei Instanzen mit 13–15 Knoten unter 1 %. Bei Q-GTSP sank die Zulässigkeit jenseits von 15 Knoten signifikant.
  • Lösungsqualität: Das mittlere Approximationsverhältnis fiel oft unter die Zufallsguessing-Baseline, was darauf hindeutet, dass die Mehrheit der gesampelten Shots ungültig oder von schlechter Qualität war.
  • Hardwaregrenzen:
    • Q-GTSP: Stieß bei vorverarbeiteten mittleren Instanzen auf „Embedding-Fehler", bei denen die Anforderungen an logische Qubits (bis zu 400) die Kapazität der physikalischen Qubits überschritten.
    • C-QAOA: Litt unter niedrigen Sampling-Raten; 1500 Shots reichten nicht aus, um den exponentiell wachsenden Suchraum abzudecken.

• Auswirkung der Vorverarbeitung:

  • Die Vorverarbeitung verbesserte die Zulässigkeit des Quanten-Annealing-Ansatzes erheblich und ermöglichte ihm, größere zugrunde liegende Problemstrukturen zu bewältigen.
  • Die Vorverarbeitung hatte einen negativen oder neutralen Effekt auf C-QAOA, wahrscheinlich aufgrund der erhöhten strukturellen Komplexität (mehr Cluster), die die flache Schaltungstiefe ($p=1$) nicht bewältigen konnte.

5. Bedeutung und Fazit

• Aktueller Stand: Quantenoptimierer zeigen Potenzial für kleinskalige GTSP-Instanzen und sind in der Lage, optimale Lösungen zu finden. Allerdings leiden sie derzeit unter schlechter Skalierbarkeit und niedrigen Zulässigkeitsraten, wenn die Problemgröße zunimmt.
• Primärer Engpass: Das Hauptversagensmuster liegt nicht nur in der Lösungsqualität, sondern in der Unfähigkeit, innerhalb eines festen Shot-Budgets zulässige Lösungen zu generieren. Strafbasiertes Umgang mit Einschränkungen (in QUBO) und flache Mixer (in QAOA) haben Schwierigkeiten, den eingeschränkten Suchraum effektiv zu navigieren.
• Zukünftige Richtungen: Die Autoren schließen, dass für eine praktikable Quantenoptimierung für GTSP zukünftige Arbeiten sich auf Folgendes konzentrieren müssen:
  1. Umgang mit Einschränkungen: Über Strafterme hinausgehen hin zu intrinsischer Einschränkungsdurchsetzung (z. B. ausgefeiltere Mixer in QAOA).
  2. Skalierbarkeit: Verbesserung der Codierungseffizienz und des Managements der Schaltungstiefe.
  3. Hardware: Nutzung größerer, besser verbundener Qubit-Topologien, um den Embedding-Overhead zu reduzieren.

Zusammenfassend stellt das Paper zwar ein grundlegendes Framework für das Quanten-GTSP auf, hebt jedoch hervor, dass die aktuelle NISQ-Hardware und -Algorithmen noch nicht bereit sind, klassische Löser für praktische Routenplanungsprobleme im mittleren bis großen Maßstab ohne signifikante algorithmische Durchbrüche im Umgang mit Einschränkungen zu ersetzen.