Ein variationaler qubit-effizienter MaxCut-Heuristik-Algorithmus

Warum winzige Quantenchips für große Probleme wichtig sind

Viele praktische Aufgaben – vom Entwurf von Schaltkreisen bis zur Modellierung von Materialien – lassen sich darauf zurückführen, ein Netzwerk in zwei Gruppen zu teilen und dabei möglichst viele Verbindungen zwischen ihnen zu durchtrennen. Diese Herausforderung, bekannt als MaxCut, ist für klassische Computer notorisch schwer. Der Artikel stellt eine neue, von der Quantenrechnung inspirierte Methode vor, die überraschend große Netzwerke mit nur wenigen Quantenbits (Qubits) verarbeiten kann und so einen neuen Weg bietet, sowohl Quanten- als auch klassische Optimierungswerkzeuge zu testen und zu verbessern.

Ein Netzwerk in zwei nützliche Hälften teilen

MaxCut stellt eine einfach klingende Frage: Wenn man eine Menge Punkte (Knoten) hat, die durch Linien (Kanten) verbunden sind, wie sollte man jeden Knoten färben, etwa blau oder weiß, sodass möglichst viele Linien Knoten unterschiedlicher Farbe verbinden? Diese bestmögliche Aufteilung ist in Bereichen wie Schaltkreis-Design und statistischer Physik wertvoll, ist aber bei großen Netzwerken sehr schwer exakt zu finden. Ein verbreiteter klassischer Ansatz, der Goemans–Williamson-(GW-)Algorithmus, verwendet eine clevere Relaxation des Problems und garantiert, einen Cut zu finden, der mindestens etwa 88% so gut ist wie der optimale. Die Quantenrechnung verspricht neue Angriffspunkte für solche Probleme, doch aktuelle Geräte sind rauschbehaftet und in der Größe begrenzt, sodass es schwierig ist, große, tiefe Schaltkreise auszuführen.

Große Graphen mit nur wenigen Qubits lösen

Standard-Quantenansätze wie der Quantum Approximate Optimization Algorithm (QAOA) benötigen ein Qubit pro Netzwerkknoten, sodass ein Graph mit 1.000 Knoten 1.000 Qubits erfordern würde – weit jenseits heutiger Maschinen. Die neue Methode, Qubit-Efficient MaxCut (QEMC) genannt, kehrt diese Skalierung um: Sie verwendet nur etwa den Logarithmus der Knotenzahl, das heißt 11 Qubits können Informationen über mehr als 2.000 Knoten kodieren. Anstatt jedes Qubit an einen einzelnen Knoten zu binden, nutzt QEMC den gesamten Quantenzustand als kompakten Adressraum und ordnet verschiedenen Knoten unterschiedliche Basiszustände dieses kleinen Registers zu. Diese Qubit-Ökonomie hält die Schaltkreise flach und leichter auf rauschbehafteter Hardware ausführbar, während sie dennoch sehr große Graphen darstellen kann.

Knoten nach Wahrscheinlichkeit färben statt nach festen Zuständen

Die zentrale Innovation liegt in der Art, wie QEMC die "Farbe" jedes Knotens kodiert. Anstatt jeden Knoten in einem einzelnen Quantenzustand zwingend als genau blau oder weiß festzulegen, lässt die Methode die Farbe eines Knotens aus der Messwahrscheinlichkeit ableiten. Ein Knoten, dessen Basiszustand mit niedriger Wahrscheinlichkeit auftritt, wird als eine Farbe behandelt; ein Knoten mit höherer Wahrscheinlichkeit als die andere. Ein Schwellenwert trennt die beiden Bereiche. Das bedeutet, dass viele verschiedene Quantenzustände im Wesentlichen derselben Graphpartition entsprechen. Die Kostenfunktion, die QEMC minimiert, ist so konstruiert, dass verbundene Knoten dazu angeregt werden, auf unterschiedlichen Seiten dieses Wahrscheinlichkeits-Schwellenwertes zu liegen, was tendenziell die Anzahl der Kanten zwischen den beiden Farbgruppen erhöht und somit den Cut verbessert.

Leistungstests auf realen und simulierten Geräten

Die Autoren testen QEMC auf zwei Ebenen: auf echten Quantenprozessoren und in klassischen Simulationen der Quantenschaltkreise. Bei kleinen regulären Graphen mit bis zu 32 Knoten (unter Verwendung von nur 2 bis 5 Qubits) findet QEMC auf IBM-Supraleitungs-Hardware Schnitte, die mit den durch Exhaustive Search gefundenen besten Antworten übereinstimmen oder diesen nahezu entsprechen und deutlich besser sind als zufällige Schätzungen sowie frühere Quantenstudien basierend auf QAOA. In rauschfreien Simulationen erreicht QEMC für diese kleinen Graphen konsistent über 97% des optimalen Cuts. Die Stärke der Kodierung wird bei größeren Graphen noch sichtbarer: Für 9-reguläre Graphen mit bis zu 2.048 Knoten übertreffen klassische Simulationen von QEMC weiterhin GW bei sowohl durchschnittlichen als auch besten Cuts um einige Prozent, und ähnliche Vorteile zeigen sich bei zufälligen Graphen mit 128 Knoten und unterschiedlichen Dichten.

Geschwindigkeit, Grenzen und quanten-inspirierte Perspektiven

Trotz des Erfolgs liefert QEMC noch keinen formalen quantenmechanischen Vorteil. Da es nur etwa log N Qubits verwendet, skaliert die klassische Simulation seiner Schaltkreise ebenfalls annähernd linear mit der Knotenzahl, und die Zeit zur Auswertung der Kostenfunktion wächst mit der Anzahl der Kanten. Empirische Studien deuten darauf hin, dass die Gesamtzeit, um GW-ähnliche Leistung zu erreichen, ungefähr quadratisch mit der Graphgröße wächst, was für viele Probleme trotzdem praktisch erreichbar ist. Das bedeutet, dass QEMC in seiner jetzigen Form eher als leistungsfähige, quanten-inspirierte Heuristik denn als Beleg für einen quantenmechanischen Vorteil dient.

Was diese Arbeit für die Zukunft bedeutet

Für Nicht-Spezialisten lautet die Hauptbotschaft, dass kleine, rauschbehaftete Quantengeräte dennoch wissenschaftlich nützlich sein können, wenn man Algorithmen entwickelt, die zu ihren Stärken passen. Indem Knotfarben in flexiblen Wahrscheinlichkeitsbereichen statt in starren Bitwerten kodiert werden, nutzt QEMC sehr wenige Qubits, um sehr große Netzwerkprobleme anzugehen, und toleriert dabei Hardware-Rauschen auf natürliche Weise. Die Methode setzt einen neuen Maßstab für das Testen von Quantenoptimierungsalgorithmen und liefert zugleich einen praktischen klassischen Algorithmus auf derselben Ideenbasis. Allgemeiner zeigt sie, wie ein Umdenken in der Informationskodierung – statt nur größere Maschinen zu bauen – vielversprechende Wege zur Lösung schwerer Rechenprobleme eröffnen kann.

Zitation: Tene-Cohen, Y., Kelman, T., Lev, O. et al. A Variational Qubit-Efficient MaxCut Heuristic Algorithm. npj Quantum Inf 12, 50 (2026). https://doi.org/10.1038/s41534-026-01186-2

Schlüsselwörter: MaxCut, Quantenoptimierung, variationale Algorithmen, Graphpartitionierung, quanten-inspirierte Berechnung