ParaQAOA beschleunigt QAOA für Max-Cut

Das Problem zeigt sich nicht sofort — bis zu dem Zeitpunkt, an dem QAOA mit dem Anstieg der Dimension konfrontiert wird. Für Max-Cut äußert sich dies in den exponentiellen Kosten der Simulation von Quanten-Schaltungen und dem Anstieg der Tiefe der Schaltungen. Klassische Divide-and-Conquer-Ansätze reduzieren die Größe der Teilaufgaben, verlagern jedoch die Last in die Vorverarbeitung und das Zusammenführen. Infolgedessen stößt das System an die Ausführungszeit und nicht an die Qualität der Lösung: Einige Methoden erreichen eine hohe Genauigkeit, benötigen jedoch Stunden oder Tage selbst bei moderaten Graphen. Das Gleichgewicht zwischen dem Approximationsverhältnis und der Laufzeit bleibt instabil.

ParaQAOA wählt einen pragmatischen Kompromiss: die Dekomposition nicht zu komplizieren, sondern die gesamte Pipeline durch Parallelität zu beschleunigen. Anstelle komplexer Partitionierungsalgorithmen wird eine lineare Aufteilung des Graphen unter Beibehaltung der Konnektivität (connectivity-preserving partitioning) verwendet. Der Hauptfokus liegt auf der parallelen Ausführung (parallel execution) der Teilaufgaben und einem kontrollierten Trade-off zwischen Qualität und Geschwindigkeit. In die Architektur sind Parameter integriert, die es ermöglichen, die Suchtiefe (durch die Anzahl der Kandidaten) und die Hardwareauslastung zu regulieren. Dies macht das System anpassungsfähig an verschiedene Einschränkungen — von Latenz bis zu verfügbaren GPUs.

Die Implementierung ist in drei Phasen unterteilt. Zuerst wird der Graph in Teilgraphen in O(|V|+|E|) aufgeteilt, wobei benachbarte Teile einen Knoten teilen, um die Struktur zu erhalten. Dies senkt die Kosten der Vorverarbeitung und beseitigt den Engpass, der für frühere Lösungen mit quadratischer Komplexität charakteristisch war. Anschließend wird die parallele QAOA-Ausführung gestartet: Jede Teilaufgabe wird unabhängig verarbeitet, und das Ergebnis ist eine Menge von top-K Bitstrings mit der höchsten Wahrscheinlichkeit. K ist ein steuerbarer Parameter, der direkt das Gleichgewicht zwischen Durchsatz und Qualität beeinflusst. Die letzte Phase ist das level-aware Merge, bei dem Kombinationen von Lösungen zu einer globalen Antwort unter Berücksichtigung des ursprünglichen Graphen zusammengeführt werden. Hier wird auch die Kontrolle über die Rechenkosten durch Einschränkung des Suchraums beibehalten.

Ein separates Element ist die Metrik Performance Efficiency Index (PEI), die die Qualität der Lösung und die Ausführungszeit kombiniert. Dies ist ein Versuch, den Kompromiss zu formalisieren, der zuvor implizit blieb. Unter Bedingungen von Highload-Aufgaben ist eine solche Metrik nützlicher als eine isolierte Bewertung des Approximationsverhältnisses.

Die Ergebnisse zeigen, dass der Ansatz über 10.000 Knoten hinaus skalierbar ist, ohne in praktische Unbrauchbarkeit zu degenerieren. Eine Beschleunigung von bis zu 1.600x bei mittelgroßen Graphen wurde festgestellt, während die Genauigkeit innerhalb von 2% der besten bekannten Lösungen bleibt. Für einen Graphen mit 16.000 Knoten wird die Zeit von mehr als 13,6 Tagen auf 19 Minuten reduziert. Dies bedeutet nicht, dass die Heuristik von QAOA selbst verbessert wird, sondern zeigt, dass architektonische Lösungen Einschränkungen auf Systemebene beseitigen können.

Im industriellen Kontext sieht dies wie eine erwartete Evolution aus. Anstatt zu versuchen, „den Algorithmus um jeden Preis zu verbessern“, verschiebt sich der Fokus auf Orchestrierung und die Nutzung verfügbarer Hardware. ParaQAOA beseitigt nicht die grundlegende Komplexität von QAOA, sondern macht sie beherrschbar. Genau das bestimmt normalerweise die Eignung des Algorithmus in einer Produktionsumgebung.