Quantum Approximation Complexity of Classical Optimization Problems

Titel: Quantenapproximationskomplexität klassischer Optimierungsprobleme
Autor: Stuart Hadfield

Problemstellung

Die Arbeit befasst sich mit dem Mangel an rigorosen Worst-Case-Leistungsgarantien für Quantenoptimierungsalgorithmen. Während viele Quantenmethoden (z. B. QAOA, DQI) hohe Scores für spezifische Instanzen erzielen oder Schranken für Erwartungswerte (dekodierte Mittelwerte) liefern, fehlt es ihnen oft an uniformen Algorithmen, die für jeden Input ein bestimmtes Approximationsverhältnis mit beschränktem Fehler garantieren. Die Arbeit sucht nach einer formalen Definition von Quanten-Analoga zu klassischen Approximationskomplexitätsklassen (APX, PTAS, FPTAS) und untersucht, ob die Quantenberechnung die klassische randomisierte Berechnung in Bezug auf die garantierte Lösungsqualität oder die benötigte Zeit zur Erreichung einer gewünschten Genauigkeit strikt verbessern kann.

Methodik

Der Autor erweitert das Framework von NP-Optimierungsproblemen (NPO) auf umfassende Fehlerschranken für Quantenalgorithmen.

1. Definition von Quantenklassen: Das Paper definiert BQ-APX, BQ-PTAS und BQ-FPTAS. Die Zugehörigkeit zu diesen Klassen erfordert einen uniformen Quantenalgorithmus, der auf jedem Input eine zulässige klassische Lösung liefert, welche das beanspruchte Approximationsverhältnis mit einer Wahrscheinlichkeit von mindestens $2/3$ erreicht. Entscheidend ist, dass die Laufzeit alle Schritte umfasst: Parameterwahl, Zustandspräparation, Messung, Dekodierung und Wiederholung. Der Score der Lösung muss klassisch effizient berechenbar sein.
2. Transfer von dekodiertem Mittelwert zu Output: Ein wichtiges technisches Werkzeug ist Lemma 6 und Korollar 7, die eine Beziehung zwischen dem erwarteten Score einer dekodierten Lösung und einer beschränkt-fehlerhaften klassischen Output-Garantie herstellen. Dies ermöglicht die Übersetzung von erwartungswertbasierten Analysen (die in der Quantenliteratur üblich sind) in die strengen Output-Garantien, die für die Klassenzugehörigkeit erforderlich sind.
3. Bedingte Trennungen: Das Paper konstruiert spezifische Probleme, um strikte Inklusionen zwischen Quanten- und Klassenzugruppen unter Standard-Komplexitätsannahmen (z. B. $NP \not\subseteq BQP$ und $Factor \notin FBPP$) aufzuzeigen. Diese Konstruktionen stützen sich auf „Search Padding“ und kryptographische Härte.

Zentrale Beiträge und Ergebnisse

1. Formale Hierarchie von Quanten-Approximationsklassen
Das Paper etabliert eine strikte Hierarchie für Quanten-Approximationsklassen unter der Annahme, dass $NP \not\subseteq BQP$:
$$BQ\text{-}FPTAS \subsetneq BQ\text{-}PTAS \subsetneq BQ\text{-}APX$$
Diese Hierarchie wird durch klassische Probleme bezeugt:

• Max-E3SAT: Besitzt eine deterministische konstante Approximationsrate (in APX), aber kein Quanten-PTAS.
• Planar Vertex Cover: Besitzt ein deterministisches PTAS, aber kein Quanten-FPTAS.
  Diese Ergebnisse zeigen, dass die Quantenklassen untereinander verschieden sind, obwohl sie für diese spezifischen Probleme noch nicht die Quantenberechnung von den randomisierten klassischen Klassen trennen.

2. Certified Maximum Order (CMO): Eine starke Quanten–Klassik-Trennung
Das Paper führt das Certified Maximum Order (CMO) Problem ein, bei dem das Ziel darin besteht, die multiplikative Ordnung eines Elements modulo $N$ zu finden, die durch eine Primfaktorzerlegung der Ordnung zertifiziert ist.

• Quantenergebnis: Ein Bounded-Error-Quantenalgorithmus kann das exakte Optimum (die Carmichael-Funktion $\lambda(N)$) in Polynomialzeit mittels Faktorisierung und Periodenfindung finden. Somit gilt $CMO \in BQ\text{-}FPTAS$.
• Klassische Barriere: Jeder randomisierte Polynomialzeit-Algorithmus, der selbst ein Approximationsverhältnis der Größenordnung eines Polynoms für CMO garantiert, würde einen randomisierten Polynomialzeit-Faktorisierungsalgorithmus implizieren.
• Fazit: Unter der Annahme, dass $Factor \notin FBPP$, gilt $CMo \in BQ\text{-}FPTAS \setminus R\text{-}POLY\text{-}APX$. Dies etabliert eine bedingte Trennung, bei der Quantenalgorithmen exakte Lösungen liefern, während randomisierte klassische Algorithmen nicht einmal polynomielle Approximationsverhältnisse erreichen können.

3. Discrete-Logarithm Fitting (DLog-Fit): Eine Schwellenwert-Trennung
Das Paper definiert DLog-Fit, ein Problem zur Vorhersage von Labels auf einer Stichprobe basierend auf diskreten Logarithmen.

• Klassische Baseline: Ein deterministischer Algorithmus erreicht eine $1/2$-Approximation (Vorhersage des Mehrheitslabels).
• Quantenvorteil: Ein Quantenalgorithmus kann eine perfekte Anpassung (exaktes Optimum) finden.
• Klassische Barriere: Jede feste Verbesserung über das $1/2$-Verhältnis durch einen randomisierten klassischen Algorithmus würde das Problem des diskreten Logarithmus in einer Safe-Prime-Untergruppe lösen.
• Fazit: Unter der Annahme, dass das diskrete Logarithmus-Problem in Safe-Prime-Untergruppen nicht in $FBPP$ liegt, gilt $DLog\text{-}Fit \in R\text{-}APX \cap BQ\text{-}FPTAS \setminus R\text{-}PTAS$. Dies demonstriert eine Lücke am $1/2$-Approximationsschwellenwert.

4. Generelles Search Padding (Theorem 8)
Das Paper liefert eine generische Konstruktion, die zeigt, dass jedes Suchproblem mit effizient verifizierbaren Zeugen in ein NPO-Problem mit einem $1/2$-Approximationsschwellenwert transformiert werden kann. Wenn ein Quantenlöser für die Suche existiert, ein randomisierter klassischer Löser jedoch nicht, liegt das resultierende Optimierungsproblem in $BQ\text{-}FPTAS$, aber außerhalb von $R\text{-}PTAS$.

5. Analyse bestehender Quantenmethoden
Das Paper wendet diese Definitionen auf bestehende Algorithmen an:

• QAOA: Für Fixed-Depth QAOA auf 3-regulären MaxCut-Graphen nutzt das Paper den Transfer des dekodierten Mittelwerts, um zu zeigen, dass Wiederholung eine Bounded-Error-Output-Garantie liefern kann (z. B. über $2/3$ des Optimums), was diese spezifische Graphfamilie in $BQ\text{-}APX$ einordnet.
• Decoded Quantum Interferometry (DQI): Das Paper stellt fest, dass DQI zwar verbesserte erwartete Scores für spezifische Familien (wie gefaltete OPI) zeigt, der Nachweis einer Trennung im expliziten-Input-Zeitmodell jedoch die Beweisführung erfordert, dass randomisierte klassische Algorithmen nicht dasselbe Verhältnis erreichen können – dies bleibt eine offene Herausforderung für uneingeschränkte Probleme.

Bedeutung und Ansprüche

Das Paper beansprucht, die ersten rigorosen Definitionen für Bounded-Error-Quantenapproximationsklassen geliefert zu haben und zu beweisen, dass die Quantenberechnung unter expliziten Komplexitätsannahmen die Worst-Case-Approximationsgarantien gegenüber der randomisierten klassischen Berechnung strikt verbessern kann.

• Moderer Umfang: Der Autor stellt explizit fest, dass für gängige, uneingeschränkte Probleme wie MaxCut oder MaxSAT eine Quanten–Klassik-Lücke in den Worst-Case-Output-Verhältnissen weiterhin offen ist. Die etablierten Trennungen beruhen auf spezifischen, oft kryptographischen Problemkonstruktionen (CMO, DLog-Fit) oder eingeschränkten Graphfamilien.
• Theoretischer Rahmen: Die Arbeit schließt die Lücke zwischen heuristischer Quantenleistung (oft gemessen an Erwartungswerten) und rigoroser Komplexitätstheorie (Bounded-Error-Output-Garantien). Sie klärt, dass hohe Benchmark-Scores allein keine Zugehörigkeit zu einer Approximationsklasse begründen, ohne Uniformität und Laufzeitbeschränkungen zu berücksichtigen.
• Zukünftige Richtung: Das Paper identifiziert die Suche nach einem uniformen Quantenalgorithmus, der ein Verhältnis garantiert, das besser als der klassische Härte-Schwellenwert für Standardprobleme (wie uneingeschränktes MaxCut) ist, als die zentrale offene Frage des Feldes.