Der Quantennäherungsoptimierungsalgorithmus (QAOA) bei hoher Tiefe für MaxCut auf großen Girth-regulären Graphen und das Sherrington-Kirkpatrick-Modell

Der Quantennäherungsoptimierungsalgorithmus (QAOA) findet annähernde Lösungen für kombinatorische Optimierungsprobleme. Seine Leistung verbessert sich monoton mit seiner Tiefe p. Wir wenden den QAOA auf MaxCut auf großen Girth D-regulären Graphen an. Wir geben eine iterative Formel zur Bewertung der Leistung für jedes D bei jeder Tiefe p. Bei Betrachtung zufälliger D-regulärer Graphen, bei optimalen Parametern und wenn D gegen unendlich geht, stellen wir fest, dass der QAOA für p=11 alle klassischen Algorithmen (die den Autoren bekannt sind), die frei von unbewiesenen Vermutungen sind, übertrifft. Während die iterative Formel für diese D-regulären Graphen abgeleitet wird, indem man einen einzelnen Baum-Untergraphen betrachtet, beweisen wir, dass sie auch die ensemble-averagierte Leistung des QAOA auf dem Sherrington-Kirkpatrick (SK)-Modell definiert auf dem vollständigen Graphen gibt. Wir verallgemeinern unsere Formel auch auf Max-q-XORSAT auf großen Girth-regulären Hypergraphen. Unser Iterationsverfahren ist ein kompaktes Verfahren, aber seine rechnerische Komplexität wächst mit O (p² 4ᵖ). Diese Iteration ist effizienter als das vorherige Verfahren zur Analyse der QAOA-Leistung auf dem SK-Modell, und wir können numerisch bis zu p=20 gehen. Ermutigt durch unsere Ergebnisse machen wir die optimistische Vermutung, dass der QAOA, wenn p gegen unendlich geht, den Parisi-Wert erreichen wird. Wir analysieren die Leistung des Quantenalgorithmus, aber man muss ihn auf einem Quantencomputer ausführen, um eine Zeichenkette mit der garantierten Leistung zu produzieren.