Quantum Approximation Complexity of Classical Optimization Problems

Titel: Kwantum-benaderingscomplexiteit van klassieke optimalisatieproblemen
Auteur: Stuart Hadfield

Probleemstelling

Het artikel behandelt het gebrek aan rigoureuze garanties voor de worst-case prestaties van kwantumoptimalisatiealgoritmen. Hoewel veel kwantummethoden (bijv. QAOA, DQI) hoge scores behalen op specifieke instanties of grenzen bieden voor verwachte waarden (gedecodeerde gemiddelden), missen ze vaak uniforme algoritmen die een specifieke benaderingsratio garanderen voor elke input met een begrensde fout. Het werk streeft ernaar om kwantumanalogen van klassieke benaderingscomplexiteitsklassen (APX, PTAS, FPTAS) formeel te definiëren en te bepalen of kwantumcomputatie de klassieke gerandomiseerde algoritmen strikt kan verbeteren in termen van gegarandeerde oplossingskwaliteit of de tijd die nodig is om een gewenste nauwkeurigheid te bereiken.

Methodologie

De auteur breidt het kader van NP-optimalisatieproblemen (NPO) uit om ook foutengelimiteerde kwantumalgoritmen te omvatten.

1. Definitie van Kwantumklassen: Het artikel definieert BQ-APX, BQ-PTAS en BQ-FPTAS. Lidmaatschap van deze klassen vereist een uniform kwantumalgoritme dat op elke input een haalbare klassieke oplossing teruggeeft die de geclaimde benaderingsratio behaalt met een waarschijnlijkheid van ten minste $2/3$. Cruciaal is dat de looptijd alle stappen omvat: parametervariatie, staatvoorbereiding, meting, decodering en herhaling. De score van de oplossing moet klassiek efficiënt berekenbaar zijn.
2. Overdracht van Gedecodeerd Gemiddelde naar Output: Een belangrijke technische tool is Lemma 6 en Corolarium 7, die een relatie vaststellen tussen de verwachte score van een gedecodeerde oplossing en een foutengelimiteerde klassieke outputgarantie. Dit maakt de vertaling mogelijk van op verwachting gebaseerde analyses (gangbaar in de kwantumliteratuur) naar de strikte outputgaranties die vereist zijn voor klassenlidmaatschap.
3. Conditionele Separaties: De auteur construeert specifieke problemen om strikte inclusies tussen kwantum- en klassieke klassen aan te tonen onder standaard complexiteitsveronderstellingen (bijv. $NP \not\subseteq BQP$ en $Factor \notin FBPP$). Deze constructies rusten op "search padding" en cryptografische hardheid.

Belangrijkste Bijdragen en Resultaten

1. Formele Hiërarchie van Kwantum-benaderingsklassen
Het artikel stelt een strikte hiërarchie voor kwantum-benaderingsklassen vast onder de veronderstelling dat $NP \not\subseteq BQP$:
$$BQ\text{-}FPTAS \subsetneq BQ\text{-}PTAS \subsetneq BQ\text{-}APX$$
Deze hiërarchie wordt getuigen door klassieke problemen:

• Max-E3SAT: Heeft een deterministische constante-ratio benadering (in APX) maar geen kwantum PTAS.
• Planar Vertex Cover: Heeft een deterministische PTAS maar geen kwantum FPTAS.
  Deze resultaten tonen aan dat de kwantumklassen van elkaar verschillen, hoewel ze voor deze specifieke problemen nog niet de kwantumklassen van gerandomiseerde klassieke klassen scheiden.

2. Certified Maximum Order (CMO): Een Sterke Kwantum–Klassieke Separatie
Het artikel introduceert het Certified Maximum Order (CMO) probleem, waarbij het doel is om de multiplicatieve orde van een element modulo $N$ te vinden die gecertificeerd wordt door een priemfactorisatie van de orde.

• Kwantumresultaat: Een foutengelimiteerd kwantumalgoritme kan de exacte optimum (de Carmichael-functie $\lambda(N)$) in polynomiale tijd vinden met behulp van factorisatie en periode-vinden. Zo geldt $CMO \in BQ\text{-}FPTAS$.
• Klassieke Barrière: Elk gerandomiseerd polynomiale-tijd algoritme dat zelfs een benadering met een polynomiale factor garandeert voor CMO, zou een gerandomiseerd polynomiale-tijd factorisatie-algoritme impliceren.
• Conclusie: Onder de aanname dat $Factor \notin FBPP$, geldt $CMO \in BQ\text{-}FPTAS \setminus R\text{-}POLY\text{-}APX$. Dit vestigt een conditionele separatie waarbij kwantumalgoritmen exacte oplossingen bieden terwijl gerandomiseerde klassieke algoritmen zelfs geen polynomiale-factor benaderingen kunnen bereiken.

3. Discrete-Logarithm Fitting (DLog-Fit): Een Drempel-Separatie
Het artikel definieert DLog-Fit, een probleem waarbij het voorspellen van labels op een sample gebaseerd is op discrete logaritmen.

• Klassieke Baseline: Een deterministisch algoritme bereikt een $1/2$-benadering (het voorspellen van de meerderheidslabel).
• Kwantumvoordeel: Een kwantumalgoritme kan een perfecte fit (exact optimum) vinden.
• Klassieke Barrière: Elke vaste verbetering boven de $1/2$ ratio door een gerandomiseerd klassiek algoritme zou het discrete logaritme probleem in een safe-prime subgroup oplossen.
• Conclusie: Onder de aanname dat safe-prime discrete logaritme niet in $FBPP$ zit, geldt $DLog\text{-}Fit \in R\text{-}APX \cap BQ\text{-}FPTAS \setminus R\text{-}PTAS$. Dit demonstreert een kloof bij de $1/2$ benaderingsdrempel.

4. Algemene Search Padding (Stelling 8)
Het artikel biedt een generieke constructie die aantoont dat elk zoekprobleem met efficiënt verifieerbare getuigen kan worden getransformeerd naar een NPO-probleem met een $1/2$ benaderingsdrempel. Als een kwantumsolver bestaat voor de zoekopdracht maar een gerandomiseerde klassieke solver niet, dan ligt het resulterende optimalisatieprobleem in $BQ\text{-}FPTAS$ maar buiten $R\text{-}PTAS$.

5. Analyse van Bestaande Kwantummethoden
Het artikel past deze definities toe op bestaande algoritmen:

• QAOA: Voor fixed-depth QAOA op 3-reguliere MaxCut, gebruikt het artikel de gedecodeerde-gemiddelde transfer om aan te tonen dat herhaling een foutengelimiteerde outputgarantie kan opleveren (bijv. groter dan $2/3$ van het optimum), waardoor deze specifieke grafenfamilie in $BQ\text{-}APX$ valt.
• Decoded Quantum Interferometry (DQI): Het artikel merkt op dat hoewel DQI verbeterde verwachte scores laat zien op specifieke families (zoals de gevouwen OPI), het vaststellen van een separatie in het expliciete-input model vereist dat bewezen wordt dat gerandomiseerde klassieke algoritmen niet dezelfde ratio kunnen bereiken, wat een openstaand vraagstuk blijft voor onbeperkte problemen.

Betekenis en Claims

Het artikel claimt de eerste rigoureuze definities te hebben geleverd voor foutengelimiteerde kwantum-benaderingsklassen en te hebben bewezen dat, onder expliciete complexiteitsveronderstellingen, kwantumcomputatie de worst-case benaderingsgaranties strikt kan verbeteren ten opzichte van klassieke gerandomiseerde computatie.

• Bescheiden Omvang: De auteur stelt expliciet dat voor veelvoorkomende, onbeperkte problemen zoals MaxCut of MaxSAT, een kwantum–klassieke kloof in worst-case output-ratio's een openstaand probleem blijft. De vastgestelde separaties berusten op specifieke, vaak cryptografische probleemconstructies (CMO, DLog-Fit) of beperkte grafenfamilies.
• Theoretisch Kader: Het werk overbrugt de kloof tussen heuristische kwantumprestaties (vaak gemeten in verwachtingswaarden) en rigoureuze complexiteitstheorie (foutengelimiteerde outputgaranties). Het verheldert dat hoge benchmarkscores alleen geen lidmaatschap van een benaderingsklasse vestigen zonder uniformiteit en looptijdbeperkingen.
• Toekomstige Richting: Het artikel identificeert de zoektocht naar een uniform kwantumalgoritme dat een ratio garandeert die beter is dan de klassieke hardheidsdrempel voor standaardproblemen (zoals onbeperkte MaxCut) als het centrale openstaande probleem in het veld.