Evaluating QAOA expectation values can be as hard as counting optimal solutions

Stellen Sie sich eine Welt vor, in der Computer nicht nur Zahlen berechnen, sondern mit Wahrscheinlichkeiten tanzen. Dies ist das Reich des Quantencomputings, ein Feld, das verspricht, Probleme zu lösen, die so verschlungen und komplex sind, dass heutige Supercomputer länger als das Alter des Universums bräuchten, um sie zu lösen. Das Herzstück dieses Tanzes ist eine populäre Routine namens Quantum Approximate Optimization Algorithm, oder QAOA. Stellen Sie sich QAOA wie eine hochtechnologische Schatzsuche vor. Sie haben eine Karte (ein Problem) mit vielen möglichen Pfaden, und Sie wollen den einen Pfad finden, der zum meisten Gold führt (die beste Lösung). Der Quantencomputer bereitet einen speziellen „Superpositions“-Zustand vor – eine magische Mischung aus allen möglichen Pfaden gleichzeitig – und versucht dann durch eine Serie von Schritten, die „Layer“ oder „Tiefe“ genannt werden, die Gewinnchancen so zu beeinflern, dass der beste Pfad am hellsten leuchtet, wenn man schließlich hinsieht.

Um zu wissen, ob die Schatzsuche gut läuft, müssen Wissenschaftler den „Erwartungswert“ überprüfen. In einfachem Deutsch ausgedrückt, ist dies wie ein kurzer Blick auf den Tanz des Quantencomputers, um zu sehen, wie nah er dem Gold ist, ohne den Tanz tatsächlich zu stoppen, um jede einzelne Münze zu zählen. Lange Zeit wussten Forscher, dass es einfach war, diesen Wert zu prüfen, wenn der Tanz nur einen Schritt (Tiefe $p=1$) hatte, so wie das Lesen eines einfachen Rezepts. Aber was passiert, wenn der Tanz komplizierter wird, mit zwei oder mehr Schritten? Eine aktuelle Studie von Wang und Kollegen zeigte, dass es unglaublich schwer ist, den Wert für diese tieferen Tänze zu prüfen – so schwer, dass es so schwierig ist wie das Lösen der ursprünglichen Schatzsuche selbst. Aber ist es nur genauso schwer, einen guten Pfad zu finden, oder sogar noch schwerer?

Dieses Papier, geschrieben von Stuart Hadfield, taucht tief in diese Frage ein. Der Autor beweist, dass für QAOA mit zwei oder mehr Layern das Überprüfen des Scores nicht nur so schwer ist wie das Finden einer einzigen besten Lösung; es ist so schwer wie das Zählen jeder einzelnen existierenden besten Lösung. In der Welt der Informatik ist das Finden einer Lösung eine harte Herausforderung, aber das Zählen aller Lösungen ist ein Monster ganz anderer Größenordnung, das oft als noch unmöglicher für klassische Computer gilt. Hadfield zeigt, dass dieses „Zähl-Monster“ erscheint, sobald man einen zweiten Layer zu dem Algorithmus hinzufügt. Das Papier suggeriert dies nicht nur; es liefert einen strengen mathematischen Beweis, indem es einen spezifischen Typ von Problemgraph konstruiert, der jeden Computer, der versucht, den QAOA-Score zu berechnen, dazu zwingt, im Wesentlichen das unmögliche Zählproblem zu lösen. Das bedeutet, dass für diese tieferen Quantenalgorithmen der Akt des Überprüfens, wie gut sie funktionieren, im schlimmsten Fall eine Aufgabe ist, die sich fundamental dem Zugriff klassischer Computer entziehen könnte, selbst wenn wir eine perfekte Quantenmaschine hätten, um den Tanz auszuführen.

Die Schatzsuche wird kompliziert

Lassen Sie uns den Zaubertrick aufschlüsseln. Der QAOA-Algorithmus ist darauf ausgelegt, das „MaxCut“-Problem zu lösen. Stellen Sie sich eine Gruppe von Freunden auf einer Party vor, und Sie möchten sie in zwei Teams aufteilen (Team Rot und Team Blau), um ein Spiel zu spielen. Das Ziel ist es, die Teams so anzuordnen, dass die maximale Anzahl an Freundschaften zwischen den beiden Seiten unterbrochen wird. Dies ist der „MaxCut“. Einige Anordnungen sind besser als andere, und das Finden der absolut besten Anordnung ist ein klassisches Rätsel, das schwieriger wird, je mehr Freunde man hinzufügt.

Der QAOA-Algorithmus versucht, diese beste Anordnung zu finden, indem er eine Quantenmünze wirft. Er beginnt damit, dass jeder in einer Superposition ist (sowohl Rot als auch Blau zur gleichen Zeit) und wendet dann eine Serie von „Twists“ (den Layern) an. Je mehr Twists man hinzufügt, desto anspruchsvoller wird der Tanz. Um zu sehen, ob der Tanz funktioniert, berechnen Wissenschaftler einen „Erwartungswert“. Betrachten Sie dies als einen „Score“, der Ihnen im Durchschnitt sagt, wie viele Freundschaften im Quantentanz unterbrochen werden.

Für einen einzelnen Twist ($p=1$) ist die Berechnung dieses Scores einfach. Man kann ihn auf eine Serviette schreiben. Aber wenn man einen zweiten Twist hinzufügt ($p=2$), wird es seltsam. Frühere Forschung zeigte, dass die Berechnung dieses Scores „NP-schwer“ war, was bedeutet, dass es so schwer war wie das Finden einer einzigen besten Teamanordnung. Aber Hadfields Papier sagt: „Warte, es ist eigentlich schlimmer als das.“

Das Zähl-Monster

Hadfields Hauptentdeckung ist eine deutliche Steigerung unseres Verständnisses der Schwierigkeit. Er beweist, dass das Berechnen des Scores für $p \ge 2$ nicht nur „NP-schwer“ ist (das Finden einer Lösung); es ist #P-schwer.

Um den Unterschied zu verstehen, stellen Sie sich vor, Sie sind ein Detektiv.

• NP-schwer ist, als würde man Sie fragen: „Können Sie einen Verdächtigen finden, der das Verbrechen begangen hat?“ Es ist schwer, aber wenn Sie Glück haben oder sich genug anstrengen, finden Sie vielleicht einen.
• #P-schwer ist, als würde man Sie fragen: „Wie viele Verdächtige haben insgesamt das Verbrechen begangen?“ Sie müssen jeden einzelnen finden und zählen.

In der Welt der Informatik gilt das Zählen im Allgemeinen als viel schwieriger als das bloße Finden eines Einzelnen. Hadfield zeigt, dass für QAOA mit zwei oder mehr Layern die Mathematik, die zur Berechnung des Scores erforderlich ist, Sie dazu zwingt, die Anzahl der perfekten Lösungen zu zählen.

Das magische Gadget

Wie hat er das bewiesen? Hadfield baute ein cleveres „Gadget“, das wie eine Falle ist, die darauf ausgelegt ist, den Computer zu fangen. Er nahm ein Standard-MaxCut-Problem und baute einen riesigen, komplexen Graphen darum herum. Dieser Graph besitzt spezielle „Ankerpunkte“ und „Variable“-Blöcke.

Der Trick liegt im Design. Wenn der Quantencomputer seinen Tanz auf diesem spezifischen Graphen aufführt, wird der endgültige Score (der Erwartungswert) zu einem riesigen mathematischen Ausdruck, der ein „Laurent-Polynom“ genannt wird. Dieser Ausdruck ist wie eine lange Kette von Termen, jeder mit einer anderen Potenz einer Variablen (wie $z^1, z^2, z^3...$).

Hadfield zeigte, dass die höchste Potenz in dieser Kette (der „extreme Koeffizient“) ein Geheimnis birgt. Wenn man diesen Score perfekt berechnen kann, kann man diese höchste Potenz extrahieren. Und hier ist der Clou: Die Größe dieser spezifischen Zahl ist direkt proportional zur Gesamtzahl der perfekten Lösungen des ursprünglichen Problems.

Wenn Sie also den QAOA-Score für diesen Graphen leicht berechnen könnten, wüssten Sie sofort die Antwort auf das „Zähl-Monster“-Problem. Da das Zählen im Allgemeinen als unmöglich für klassische Computer gilt, muss auch die Berechnung des QAOA-Scores für sie unmöglich sein.

Die „Ein-Kante“-Überraschung

Das Papier wird noch überraschender. Man könnte denken: „Okay, die Berechnung des Gesamt-Scores ist schwer, aber vielleicht ist die Berechnung des Scores für nur eine einzige spezifische Freundschaft (eine einzige Kante) einfach?“

Hadfield sagt: Nein. Er beweist, dass selbst wenn man den Quantencomputer nur nach der Korrelation zwischen zwei spezifischen Personen fragt (ein „Zwei-Qubit-Korrelator“ wie $\langle Z_r Z_s \rangle$), das Problem weiterhin #P-schwer bleibt. Die Schwierigkeit liegt nicht nur im großen Ganzen; sie ist in die kleinsten Details des Algorithmus eingebettet.

Was dies für die Zukunft bedeutet

Das Papier zieht eine klare Linie im Sand:

• Tiefe $p=1$: Einfach. Wir können den Score effizient berechnen.
• Tiefe $p \ge 2$: Schwer. Die Berechnung des Scores ist so schwer wie das Zählen aller optimalen Lösungen.

Dies hat enorme Auswirkungen. Viele moderne Algorithmen nutzen QAOA, um die Maschine zu trainieren, indem sie die „Twists“ (Parameter) anpassen, um einen besseren Score zu erzielen. Wenn die Berechnung des Scores so schwer ist, dann könnte das Training dieser Algorithmen auf einem klassischen Computer (um zu sehen, wie die Quantenmaschine arbeitet) für tiefe Schaltkreise unmöglich sein.

Der Autor merkt auch an, dass dies nicht bedeutet, dass Quantencomputer nutzlos sind. In der Tat könnte es bedeuten, dass sie nützlicher sind. Wenn ein klassischer Computer nicht einmal den Score prüfen kann, dann kann vielleicht nur der Quantencomputer dies tun. Das Papier warnt jedoch auch, dass diese „Schwierigkeit“ ein Worst-Case-Szenario ist. Es bedeutet nicht, dass jeder Graph unmöglich zu lösen ist; es bedeutet nur, dass es spezifische, tückische Graphen gibt, bei denen die Mathematik für klassische Computer zusammenbricht.

Das Fazit

Stuart Hadfields Papier ist ein Weckruf für die Quantengemeinschaft. Es sagt uns, dass wir, während wir QAOA leistungsfähiger machen, indem wir mehr Layer hinzufügen, nicht nur das Problem schwieriger zu lösen machen; wir machen das Problem des Überprüfens unserer Arbeit exponentiell schwieriger. Wir sind von einer Welt, in der wir den Quantentanz leicht verifizieren konnten, in eine Welt gewechselt, in der die Verifizierung des Tanzes das Lösen eines Zählrätsels erfordert, das vielleicht das Schwierigste in der Informatik ist. Es ist eine Erinnerung daran, dass in der Quantenwelt die Mathematik immer mysteriöser wird, je tiefer man eintaucht.