⚛️ Quantenphysik

Whither quantum advantage? New classical lower bounds for Max-Cut on large-girth 3-regular graphs

Diese Arbeit zeigt, dass ein klassischer lokaler Algorithmus, der Variational Iterative Rotation Algorithm (VIRAL), den Quantum Approximate Optimization Algorithm (QAOA) bei der Ermittlung neuer unterer Schranken für die Max-Cut-Fraktion auf 3-regulären Graphen mit großem Girth übertrifft und damit die asymptotische untere Schranke von 0,912 auf 0,9127 anhebt und die Aussichten auf einen Quantenvorteil in diesem spezifischen Bereich infrage stellt.

Ursprüngliche Autoren: Flaviano Morone, Shivang Rawat, Dries Sels

Veröffentlicht 2026-10-14

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Flaviano Morone, Shivang Rawat, Dries Sels

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

In der weiten Landschaft der Informatik gibt es eine Klasse von Problemen, die so komplex sind, dass das Finden der perfekten Lösung für ein großes System selbst mit den leistungsstärksten Supercomputern praktisch unmöglich ist. Eine solche Herausforderung ist das „Maximum Cut“-Problem. Stellen Sie sich ein Netzwerk aus Punkten vor, die durch Linien verbunden sind, wobei jeder Punkt mit genau drei anderen verbunden ist. Das Ziel besteht darin, diese Punkte in zwei Gruppen aufzuteilen, sodass die Anzahl der Linien, die zwischen den Gruppen verlaufen, so hoch wie möglich ist. Während das Finden der absolut besten Aufteilung ein mathematischer Albtraum ist, sind Forscher besonders daran interessiert, wie gut verschiedene Methoden auf diesen Netzwerken abschneiden können, insbesondere wenn das Netzwerk so konzipiert ist, dass es kleine Schleifen vermeidet. Diese spezifische Art von Netzwerk, bekannt als ein Graph mit großer Girth (Großschleifen-Graph), dient als Testgelände für die Grenzen der Berechnung. Jahrzehntelang war die Frage, ob Quantencomputer, die die seltsamen Gesetze der Physik nutzen, um Informationen zu verarbeiten, diese Probleme signifikant besser lösen können als klassische Computer, die auf Standardlogik und binären Schaltern beruhen.

Ein Team von Forschern hat nun die vorherrschende Hoffnung in Frage gestellt, dass Quantencomputer in diesem speziellen Bereich einen entscheidenden Vorsprung besitzen. Durch die Verfeinerung einer klassischen Methode, die einfache, lokale Regeln zur Entscheidungsfindung nutzt, haben sie demonstriert, dass ein traditioneller Algorithmus auf diesen schleifenfreien Netzwerken bei bestimmten Tiefen die führende Quantenmethode übertreffen kann. Die Studie konzentriert sich auf einen spezifischen Algorithmus namens Variational Iterative Rotation Algorithm, oder kurz VIRAL. Im Gegensatz zu Quantenmethoden, die versuchen, viele Möglichkeiten gleichzeitig durch komplexe Wahrscheinlichkeitswellen zu erkunden, weist VIRAL jedem Punkt im Netzwerk eine Richtung zu und rotiert diese Richtungen basierend auf dem Einfluss ihrer unmittelbaren Nachbarn. Dieser Prozess geschieht in Schichten, wobei jede Schicht den Punkten ermöglicht, auf die neuen Positionen ihrer Nachbarn zu reagieren. Die Forscher testeten diese Methode an einem theoretischen Modell eines Netzwerks, das keine kleinen Schleifen besitzt – eine Bedingung, die den Algorithmus dazu zwingt, sich strikt auf lokale Informationen zu verlassen, ohne durch entfernte Verbindungen verwirrt zu werden.

Die Ergebnisse dieser Untersuchung sind präzise und überraschend. Die Forscher ließen ihren klassischen Algorithmus auf einer theoretischen Baumstruktur laufen, die die lokale Sichtweise eines jeden Punktes in diesen großen, schleifenfreien Netzwerken darstellt. Sie trieben den Algorithmus bis zu einer Tiefe von zweiunddreißig Schichten, was eine signifikante Steigerung gegenüber früheren Tests darstellt. Bei jeder getesteten geraden Tiefe von p=4 bis p=32 lieferte die klassische Methode ein besseres Ergebnis als der Quantum Approximate Optimization Algorithm, oder QAOA, der der Standard für die Quantenleistung auf diesen Graphen ist. Konkret garantierte der klassische Algorithmus, dass er einen größeren Anteil der verbindenden Linien schneiden konnte als die Quantenmethode, wobei sich die Lücke mit zunehmender Komplexität der Schichten vergrößerte. Auf der tiefsten getesteten Ebene erreichte die klassische Methode eine Erfolgsrate von etwa 91,27 Prozent, eine Zahl, die die bisher beste Garantie für diese Arten von Netzwerken übertrifft. Dieser Befund legt nahe, dass der Quantenvorteil – die Idee, dass Quantencomputer Dinge tun können, die klassische Computer nicht können – für diese spezifische Klasse von Problemen bei diesen spezifischen Tiefen nicht existiert, zumindest nicht in der Weise, wie es zuvor angenommen wurde.

Die Bedeutung dieser Arbeit liegt ebenso in dem, was sie ausschließt, wie in dem, was sie beweist. Es wurde eine Zeit lang geglaubt, dass Quantenalgorithmen einen klaren Vorsprung vor klassischen Algorithmen bei diesen spezifischen Netzwerken hätten, sobald die Komplexität einen gewissen Schwellenwert erreichte. Die neue Studie revidiert diesen Glauben explizit für den Fall von drei-verbundenen Netzwerken bei geraden Tiefen bis p=32. Die Forscher schlugen die klassische Methode nicht nur vor, dass sie wettbewerbsfähig sei; sie lieferten rigorose mathematische Grenzwerte, die zeigen, dass die klassische Methode bei jeder getesteten geraden Tiefe ab p=4 streng überlegen ist. Sie berechneten, dass die Wahrscheinlichkeit, dass ihr Ergebnis ein statistischer Zufall ist, weniger als eins zu zehn Millionen beträgt. Darüber hinaus zeigten sie, dass dieser klassische Ansatz nicht nur eine theoretische Kuriosität ist, sondern eine konstruktive: Er bietet ein klares, schrittweises Rezept, das ein Standardcomputer befolgen kann, um diese Ergebnisse in einer Zeit zu erzielen, die linear mit der Größe des Netzwerks wächst.

Diese Entdeckung gestaltet das Verständnis darüber neu, wo Quantencomputer einen Vorteil bieten könnten. Die Studie deutet darauf hin, dass die komplexen Quantenfluktuationen, die Quantencomputern ihre Kraft verleihen, nicht immer eine notwendige Ressource sind. In diesem speziellen Szenario war die Zufälligkeit, die durch einfache, klassische Seeds bereitgestellt wird – im Wesentlichen zufällige Startpunkte für den Algorithmus –, ausreichend, um das System zu einer besseren Lösung als die Quantenmethode zu führen. Die Forscher fanden heraus, dass sich die Leistung des klassischen Algorithmus verbesserte, wenn sie mehr Schichten hinzufügten, wodurch sie die Lücke zum theoretisch maximal Möglichen in diesen Netzwerken schlossen. Während das exakte Limit dessen, was ein lokaler Algorithmus erreichen kann, unbekannt bleibt, hebt das neue Datenmaterial die bekannte untere Grenze höher als je zuvor und erhöht damit den Boden dessen, was mit klassischer Computertechnik als möglich gilt. Die Arbeit dient als Erinnerung daran, dass die ausgeklügeltsten Werkzeuge nicht immer die effektivsten sind und dass manchmal eine gut abgestimmte klassische Strategie die fortschrittlichste Quantenmaschinerie übermannt.

Technische Zusammenfassung: Wohin mit dem Quantenvorteil? Neue klassische untere Schranken für Max-Cut auf 3-regulären Graphen mit großer Girth

Problemdefinition
Die Arbeit befasst sich mit der Problemstellung, den maximalen Anteil der Kanten, bezeichnet als $M_g$ , zu bestimmen, der in jedem 3-regulären Graphen mit Girth $g$ (der Länge des kürzesten Zyklus) garantiert geschnitten werden kann. Die Größe $M_g$ ist definiert als das Infimum des maximalen Schnittanteils über alle 3-regulären Graphen mit einer Girth von mindestens $g$ . Während der asymptotische Grenzwert $\lim_{g\to\infty} M_g$ bekannt ist und in einem engen Fenster liegt ( $0,912 \le \lim M_g \le 0,92386$ ), bleibt die präzise untere Schranke unbekannt.

Eine zentrale Motivation dieser Arbeit ist der Vergleich zwischen klassischen lokalen Algorithmen und dem Quantum Approximate Optimization Algorithm (QAOA). Frühere Forschungen haben etabliert, dass der QAOA der Tiefe $p$ bei 3-regulären Graphen mit $g \ge 16$ die besten bekannten klassischen lokalen Algorithmen mit nachweisbaren Garantien übertrifft. Dies deutete auf einen potenziellen „Quantenvorteil“ lokaler Algorithmen bei moderater Girth hin. Die Autoren untersuchen, ob dieser Vorteil bestehen bleibt, wenn ein leistungsfähigerer klassischer lokaler Algorithmus auf dieselbe theoretische Umgebung angewendet wird.

Methodik
Die Autoren evaluieren den Variational Iterative Rotation Algorithm (VIRAL), einen klassischen lokalen Algorithmus, auf der spezifischen geometrischen Struktur, die für Graphen mit großer Girth relevant ist.

Algorithmischer Rahmen: VIRAL weist jedem Knoten einen klassischen Einheitsvektor (Spin) zu. Über $p$ Schichten werden diese Spins synchron mittels Rotationen aktualisiert, die durch die lokalen Felder der $z$ -Komponenten der Nachbarn bestimmt werden. Die Aktualisierungsregel lautet:
$s_i(n+1) = R_x(\beta_n) R_z(\gamma_n h_i(n)) s_i(n)$
wobei $h_i(n) = \sum_{j \in \partial i} s^z_j(n)$ . Der Prozess wird mit zufälligen „Seeds“ $\epsilon_i \in \{-1, +1\}$ initialisiert, um Symmetrien zu brechen, was entscheidend ist, um einen nicht-trivialen Schnitt auf regulären Graphen zu erzeugen. Nach $p$ Schichten werden die Spins geschwellt (thresholded), um die Schnittpartition zu bestimmen.
Analyse der lokalen Nachbarschaft: Die Autoren nutzen die Eigenschaft, dass auf einem Graphen mit Girth $g \ge 2p+2$ die Radius- $p$ -Nachbarschaft jeder Kante ein endlicher Baum ist (speziell zwei durch eine Kante verbundene Knoten, die jeweils zu einem vollständigen binären Baum der Tiefe $p$ wurzeln). Da der Algorithmus lokal ist, hängt die Wahrscheinlichkeit, dass eine Kante geschnitten wird, nur von den zufälligen Seeds innerhalb dieses Baums ab.
Ableitung der Schranken: Anstatt VIRAL auf endlichen Zufallsgraphen auszuführen (die kurze Zyklen enthalten können, welche strikte untere Schranken für $M_g$ ungültig machen), berechnen die Autoren den erwarteten Schnittanteil $c_{\text{VIRAL}}(p)$ direkt auf diesem Tiefen- $p$ -Baum. Durch die Definition von $M_g$ gilt: Wenn ein lokaler Algorithmus einen erwarteten Schnittanteil $c$ auf dem Baum erreicht, garantiert er einen Schnittanteil von mindestens $c$ für jeden 3-regulären Graphen mit Girth $g \ge 2p+2$ . Somit gilt $M_g \ge c_{\text{VIRAL}}(p)$ .
Berechnung und Statistik: Die Parameter für VIRAL wurden auf Zufallsgraphen mit dem Grad 3 vorab trainiert (wie in Ref. [15] beschrieben) und wurden konstant gehalten. Die Autoren schätzten $c_{\text{VIRAL}}(p)$ durch das Sampling von $10^7$ unabhängigen Seed-Konfigurationen auf dem Baum für jede gerade Tiefe $p$ bis zu $p=32$ . Für $p=2$ wurde der Wert durch Enumeration aller $2^{14}$ Konfigurationen exakt berechnet. Statistische untere Schranken ( $L$ ) wurden auf einem Konfidenzniveau von 99,99999 % berechnet.

Wichtigste Ergebnisse
Die Studie liefert rigorose untere Schranken für $M_g$ , die vorangegangene Rekorde übertreffen:

Überlegenheit gegenüber QAOA: Für jede gerade Tiefe $p \ge 4$ übersteigt der VIRAL-Baumwert $c_{\text{VIRAL}}(p)$ die entsprechenden QAOA-Schranken aus Ref. [4]. Die Verbesserung liegt zwischen 0,005 und 0,011.
Überlegenheit gegenüber klassischen Vektor-Algorithmen: VIRAL übertrifft auch den expliziten Vektor-Algorithmus von Thompson, Parekh und Marwaha (TPM) [8] bei allen Tiefen $p \ge 4$ .
Erweiterung des Girth-Bereichs: Die Ergebnisse erweitern den Bereich der Girths, für die verbesserte untere Schranken bekannt sind, von $g=36$ (der Grenze bisheriger QAOA-Ergebnisse) auf $g=66$ .
Neue asymptotische untere Schranke: Bei $g=66$ (entspricht $p=32$ ) erhalten die Autoren eine rigorose untere Schranke von $M_{66} \ge 0,91271$ bei einem Konfidenzniveau von 99,99999 %. Dies erhöht die bekannte asymptotische untere Schranke für $\lim_{g\to\infty} M_g$ von 0,912 auf 0,9127.
Konvergenzverhalten: Die Zuwächse in der Performance ( $c_{\text{VIRAL}}(p) - c_{\text{VIRAL}}(p-2)$ ) nehmen bei $p=32$ immer noch ab, was darauf hindeutet, dass der Grenzwert $p \to \infty$ noch nicht erreicht ist, der Algorithmus aber gegen die theoretische obere Schranke von 0,92386 konvergiert.

Bedeutung und Behauptungen
Das Paper behauptet, dass der scheinbare Quantenvorteil des QAOA gegenüber klassischen lokalen Algorithmen für Max-Cut auf 3-regulären Graphen bei moderater Girth ein Artefakt des spezifisch verwendeten klassischen Algorithmus zum Vergleich ist. Durch den Einsatz von VIRAL, einem klassischen Algorithmus, der zufällige Seeds nutzt, um das inhärente Rauschen semiklassischer Approximationen der Quantendynamik nachzuahmen, zeigen die Autoren, dass klassische Methoden QAOA bei jeder Tiefe $p \ge 4$ auf den relevanten Baumstrukturen übertreffen können.

Die Autoren kommen zu dem Schluss, dass für den speziellen Fall von Max-Cut auf 3-regulären Graphen Quantenfluktuationen (wie sie im QAOA genutzt werden) keinen Ressourcenvorteil gegenüber der durch Zufallseeds getriebenen klassischen Dynamik bieten. Der beobachtete „Quantenvorteil“ in früheren Studien verschwindet, wenn die klassische Baseline optimiert wird. Die Arbeit stellt fest, dass der Vorteil in diesem spezifischen Regime nicht existiert, wenngleich die Autoren anmerken, dass dies eine offene Frage bleibt, ob dies auch für höhere Grade oder $k \ge 3$ (Max- $k$ -Cut) gilt. Die Ergebnisse sind konstruktiv und liefern einen Algorithmus, der in linearer Zeit relativ zur Anzahl der Kanten läuft, um diese Schranken zu erreichen.

Mehr davon