Accuracy and Performance Evaluation of Quantum, Classical and Hybrid Solvers for the Max-Cut Problem

Technische Zusammenfassung: Genauigkeits- und Leistungsbewertung von Quanten-, klassischen und hybriden Solvern für das Max-Cut-Problem

Problemdefinition
Diese Studie befasst sich mit dem NP-schweren Max-Cut-Problem und seiner äquivalenten Formulierung, dem Quadratic Unconstrained Binary Optimization (QUBO) Problem. Das Ziel besteht darin, die Knoten eines gewichteten ungerichteten Graphen in zwei disjunkte Mengen zu partitionieren, sodass die Summe der Gewichte der Kanten, die die Mengen verbinden, maximiert wird. Die Arbeit bewertet die Fähigkeit verschiedener Solver, Lösungen nahe am globalen Optimum zu finden, wobei anerkannt wird, dass für große Instanzen exakte Lösungen oft rechnerisch unpraktikabel sind, was den Einsatz approximativer Heuristiken erforderlich macht.

Methodik und Experimenteller Aufbau
Die Autoren führten eine umfassende Benchmarking-Studie unter Verwendung von drei unterschiedlichen Datensätzen durch, die 139 Probleminstanzen mit Größen von 100 bis 10.000 Knoten umfassen.

• Datensätze:
  1. Billionnet und Elloumi (be): 50 Instanzen mit $n \in \{101, 121, 151\}$. Die globalen Optima wurden mit den exakten Solvern BiqBin und MADAM berechnet.
  2. Beasley-Kollektion (bqp): 20 Instanzen mit $n \in \{251, 501\}$. Die Optima für $n=251$ wurden exakt berechnet; für $n=501$ wurden die in der Literatur angegebenen Best-Known-Werte verwendet.
  3. G-Datensatz (G): 69 Instanzen mit $n \in \{800, 1000, 2000, 3000, 5000, 7000, 8000, 9000, 10000\}$. Die globalen Optima sind unbekannt; als Benchmarks wurden die in der Literatur bekannten besten Lösungen verwendet.
• Evaluierte Solver:
  • Quantum Annealing (QPU): Ein D-Wave Advantage System unter Nutzung einer „Fast Annealing“-Funktion, um Qubits von Umwelteffekten zu isolieren. Begrenzt auf Instanzen mit $n \le 151$.
  • Hybrid-Solver: D-Waves cloudbasierter „LeapHybridSampler“, der iterativ klassische Methoden (unterbrechbares Simulated Annealing, Tabu-Suche, Parallel Tempering) mit QPU-Aufrufen kombiniert. Er ist in der Lage, alle Instanzgrößen zu handhaben.
  • Klassisches Simulated Annealing (SA): Zwei Varianten des Algorithmus aus [3] wurden implementiert:
    • SA1: Aggressive Schrittweite, Anfangstemperatur 10.000 (optimiert für eine mit der QPU vergleichbare Laufzeit).
    • SA2: Konservative Schrittweite, Anfangstemperatur 40.000 (optimiert für die Lösungsqualität).
  • Simulated Bifurcation Machine (SBM): Toshibas Hardware-Solver. Die Ergebnisse wurden aus der bestehenden Literatur [4] entnommen, da die Autoren keinen direkten Zugriff auf den Solver hatten.

Wichtigste Ergebnisse

• Kleine Instanzen ($n \le 151$): Der Hybrid-Solver und beide SA-Varianten (SA1, SA2) erreichten konsistent das globale Optimum für alle Instanzen. Die QPU hingegen lieferte konsistent Lösungen, die signifikant weit vom globalen Optimum entfernt waren.
• Mittlere Instanzen ($n = 251, 501$): Der Hybrid-Solver und die SA-Varianten erreichten erneut die globalen Optima (für $n=251$) bzw. die Best-Known-Werte (für $n=501$). Die QPU konnte aufgrund von Kapazitätsbeschränkungen nicht getestet werden.
• Große Instanzen ($n \ge 800$):
  • Lösungsqualität: Die SBM und SA2 erzeugten die qualitativ hochwertigsten Lösungen und fanden oft die Best-Known-Werte. Der Hybrid-Solver schnitt spürbar schlechter ab als SBM und SA2, während SA1 die geringste Lösungsqualität unter den getesteten Methoden lieferte.
  • Rechenzeit: Der Hybrid-Solver und die SBM zeigten effiziente Rechenzeiten (Sekunden bis hin zu einigen Zehn-Sekunden-Bereichen). SA2 benötigte signifikant mehr Zeit (Hunderte von Sekunden, etwa 1000-mal langsamer als Hybrid/SBM in einigen Vergleichen), um die überlegene Lösungsqualität zu erreichen. SA1 hatte eine Laufzeit, die mit der des Hybrid-Solvers vergleichbar war, lieferte jedoch minderwertige Lösungen.

Bedeutung und Behauptungen
Das Paper behauptet, das Verständnis der quantengestützten Optimierung voranzutreiben, indem es den neuen D-Wave Fast Annealing QPU und den Hybrid-Solver streng gegen modernste klassische Methoden auf einem standardisierten, öffentlich verfügbaren Satz von Max-Cut-Instanzen testet.

Die Autoren kommen zu folgenden Schlüssen:

1. Limitierungen der QPU: Die D-Wave QPU findet selbst mit Fast Annealing keine optimalen Lösungen für die getesteten Instanzen und ist durch die Problemgröße ($n \le 151$) begrenzt.
2. Effektivität des Hybrids: Der D-Wave Hybrid-Solver ist in Bezug auf Geschwindigkeit und Skalierbarkeit (Handhabung von bis zu 10.000 Knoten) hocheffizient und liefert für kleinere Instanzen nahezu optimale Lösungen. Für die größten Instanzen wird er jedoch in der Lösungsqualität von klassischem SA (speziell SA2) und SBM übertroffen.
3. Wettbewerbsfähigkeit klassischer Methoden: Transparente, klassische Simulated-Annealing-Algorithmen (speziell die SA2-Variante) bleiben hochgradig wettbewerbsfähig und übertreffen oft die Qualität des Black-Box-Hybrid-Solvers, wenn auch zu einem höheren Rechenaufwand.
4. Transparenzlücke: Die Autoren äußern Frustration über die „Black-Box“-Natur des Hybrid-Solvers und merken an, dass der Mangel an Einblicken in dessen internen Workflow und die Nutzung quantenbasierter Ressourcen die wissenschaftliche Analyse erschwert.

Die Studie beansprucht keinen Quantenvorteil für die spezifischen getesteten Solver und Probleminstanzen; vielmehr hebt sie hervor, dass für Max-Cut aktuelle klassische Heuristiken (insbesondere wenn sie auf Qualität getrimmt sind) und spezialisierte Hardware wie SBM die Leistung der getesteten Quanten- und Hybrid-Ansätze übertreffen oder mit ihnen gleichziehen können.