⚛️ quantum physics

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

Dit artikel stelt vast dat het evalueren van exacte of exponentieel precieze QAOA-verwachtingswaarden voor het MaxCut-probleem bij diepte $p \geq 2$ #P-hard is, wat aantoont dat de computationele moeilijkheid overgaat van berekenbaarheid naar het tellen van optimale oplossingen in plaats van louter optimalisatie.

Oorspronkelijke auteurs: Stuart Hadfield

Gepubliceerd 2026-08-13

📖 8 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Stuart Hadfield

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je een wereld voor waarin computers niet alleen getallen kraken, maar dansen met waarschijnlijkheden. Dit is het domein van quantum computing, een veld dat belooft problemen op te lossen die zo verstrengeld en complex zijn dat de supercomputers van vandaag er langer over zouden doen dan de leeftijd van het universum. In het hart van deze dans staat een populaire routine genaamd het Quantum Approximate Optimization Algorithm, of QAOA. Denk aan QAOA als een technologisch hoogstaande schattenjacht. Je hebt een kaart (een probleem) met veel mogelijke paden, en je wilt het pad vinden dat naar het meeste goud leidt (de beste oplossing). De quantumcomputer bereidt een speciale "superpositie"-toestand voor—een magische mix van alle mogelijke paden tegelijk—en probeert vervolgens, door middel van een reeks stappen die "lagen" of "diepte" worden genoemd, de kansen zo te kantelen dat het beste pad het helderst schijnt wanneer je er uiteindelijk naar kijkt.

Om te weten of de schattenjacht goed verloopt, moeten wetenschappers de "verwachtingswaarde" controleren. In gewone mensentaal is dit alsoer een snelle blik werpen op de dans van de quantumcomputer om te zien hoe dicht hij bij het vinden van het goud is, zonder de dans daadwerkelijk te stoppen om elke enkele munt te tellen. Lange tijd wisten onderzoekers dat als de dans slechts één stap had (diepte $p=1$ ), het controleren van deze score eenvoudig was, zoals het lezen van een simpel recept. Maar wat gebeurt er wanneer de dans ingewikkelder wordt, met twee of meer stappen? Een recente studie door Wang en collega's toonde aan dat het controleren van de score voor deze diepere dansen ongelooflijk moeilijk is—zo moeilijk dat het even moeilijk is als het oplossen van de oorspronkelijke schattenjacht zelf. Maar is het net zo moeilijk als het vinden van één goed pad, of is het zelfs nog moeilijker?

Dit artikel, geschreven door Stuart Hadfield, duikt diep in die vraag. De auteur bewijst dat voor QAOA met twee of meer lagen, het controleren van de score niet alleen even moeilijk is als het vinden van een enkele beste oplossing; het is even moeilijk als het tellen van elke enkele beste oplossing die bestaat. In de wereld van de informatica is het vinden van één oplossing een zware uitdaging, maar het tellen van ze allemaal is een monster van een heel andere omvang, vaak beschouwd als nog onmogelijker voor klassieke computers om te verwerken. Hadfield laat zien dat dit "telmonster" verschijnt op het moment dat je een tweede laag aan het algoritme toevoegt. Het artikel suggereert dit niet alleen; het biedt een rigoureus wiskundig bewijs door een specifiek type probleemgrafiek te construeren die elke computer die probeert de QAOA-score te berekenen, dwingt om in essentie het onmogelijke telprobleem op te lossen. Dit betekent dat voor deze diepere quantumalgoritmen het controleren van hoe goed ze het doen, in het slechtste geval, een taak is die fundamenteel buiten het bereik van klassieke computers kan liggen, zelfs als we een perfecte quantummachine hebben om de dans uit te voeren.

De Schattenjacht Wordt Complicater

Laten we de truc ontleden. Het QAOA-algoritme is ontworpen om het "MaxCut"-probleem op te lossen. Stel je een groep vrienden voor op een feestje voor, en je wilt hen verdelen in twee teams (Team Rood en Team Blauw) om een spel te spelen. Het doel is om de teams zo in te delen dat het maximale aantal vriendschappen tussen de twee zijden wordt verbroken. Dit is de "MaxCut". Sommige arrangementen zijn beter dan andere, en het vinden van het absolute beste arrangement is een klassieke puzzel die moeilijker wordt naarmate je meer vrienden toevoegt.

Het QAOA-algoritme probeert dit beste arrangement te vinden door een quantummunt te laten draaien. Het begint met iedereen in een superpositie (zowel Rood als Blauw tegelijkertijd) en past vervolgens een reeks "draaiingen" (de lagen) toe. Hoe meer draaiingen je toevoegt, hoe geavanceerder de dans wordt. Om te zien of de dans werkt, berekenen wetenschappers een "verwachtingswaarde". Denk hierbij aan een "score" die je vertelt hoeveel vriendschappen er gemiddeld worden verbroken in de quantumdans.

Voor een enkele draaiing ( $p=1$ ) is het berekenen van deze score eenvoudig. Je kunt het op een servetje opschrijven. Maar wanneer je een tweede draaiing toevoegt ( $p=2$ ), worden de dingen vreemd. Vorig onderzoek toonde aan dat het berekenen van deze score "NP-hard" was, wat betekent dat het even moeilijk is als het vinden van de enkele beste teamindeling. Maar Hadfield's artikel zegt: "Wacht, het is eigenlijk erger dan dat."

Het Telmonster

Hadfields belangrijkste ontdekking is een scherpe upgrade in ons begrip van de moeilijkheidsgraad. Hij bewijst dat het berekenen van de score voor $p \ge 2$ niet alleen "NP-hard" is (het vinden van één oplossing); het is #P-hard.

Om het verschil te begrijpen, stel je voor dat je een detective bent.

NP-hard is alsof je gevraagd wordt: "Kun je één verdachte vinden die het misdrijf heeft gepleegd?" Het is moeilijk, maar als je geluk hebt of hard genoeg probeert, kun je er misschien één vinden.
#P-hard is alsof je gevraagd wordt: "Hoeveel verdachten hebben in totaal het misdrijf gepleegd?" Je moet elke enkele verdachte vinden en tellen.

In de wereld van de informatica wordt aannomen dat tellen over het algemeen veel moeilijker is dan alleen het vinden van één. Hadfield laat zien dat voor QAOA met twee of meer lagen, de wiskunde die nodig is om de score te berekenen, je dwingt om het aantal perfecte oplossingen te tellen.

Het Magische Hulpmiddel

Hoe heeft hij dit bewezen? Hadfield bouwde een slim "gadget", wat een soort val is die ontworpen is om de computer te vangen. Hij nam een standaard MaxCut-probleem en bouwde een enorme, complexe graaf eromheen. Deze graaf heeft speciale "ankerpunten" en "variabele" blokken.

De truc zit in het ontwerp. Wanneer de quantumcomputer zijn dans uitvoert op deze specifie speciale graaf, verandert de uiteindelijke score (de verwachtingswaarde) in een enorme wiskundige expressie genaamd een "Laurent-polynoom". Deze expressie is als een lange reeks termen, elk met een verschillende macht van een variabele (zoals $z^1, z^2, z^3...$ ).

Hadfield toonde aan dat de hoogste macht in deze reeks (de "extreme coëfficiënt") een geheim bevat. Als je de score perfect kunt berekenen, kun je deze hoogste macht extraheren. En hier komt de crux: de grootte van dat specifieke getal is direct evenredig aan het totaal aantal perfecte oplossingen van het oorspronkelijke probleem.

Dus, als je de QAOA-score voor deze graaf gemakkelijk zou kunnen berekenen, zou je onmiddellijk het antwoord weten op het "telmonster"-probleem. Omdat tellen naar algemeen wordt beschouwd als onmogelijk voor klassieke computers om efficiënt te doen, moet het berekenen van de QAOA-score ook onmogelijk zijn voor hen.

De "Eén Rand" Verrassing

Het artikel wordt nog verrassender. Je zou kunnen denken: "Oké, het berekenen van de totale score is moeilijk, maar misschien is het berekenen van de score voor slechts één specifieke vriendschap (één rand) wel makkelijk?"

Hadfield zegt van niet. Hij bewijst dat zelfs als je de quantumcomputer alleen vraagt om de correlatie tussen twee specifieke mensen te vertellen (een "twee-qubit correlator" zoals $\langle Z_r Z_s \rangle$ ), het probleem #P-hard blijft. De moeilijkheid zit niet alleen in het grote plaatje; het zit verankerd in de kleinste details van het algoritme.

Wat Dit Betekent voor de Toekomst

Het artikel trekt een duidelijke lijn in het zand:

Diepte $p=1$ : Makkelijk. We kunnen de score efficiënt berekenen.
Diepte $p \ge 2$ : Moeilijk. Het berekenen van de score is even moeilijk als het tellen van alle optimale oplossingen.

Dit heeft enorme implicaties. Veel moderne algoritmen gebruiken QAOA om de machine te trainen, waarbij de "draaiingen" (parameters) worden aangepast om een betere score te krijgen. Als het berekenen van de score zo moeilijk is, dan kan het trainen van deze algoritmen op een klassieke computer (om te zien hoe de quantummachine het doet) onmogelijk zijn voor diepe circuits.

De auteur merkt ook op dat dit niet betekent dat quantumcomputers nutteloos zijn. Sterker nog, het kan betekenen dat ze nuttiger zijn. Als een klassieke computer zelfs de score niet eens kan controleren, dan is het misschien wel zo dat de quantumcomputer de enige is die dat kan. De paper waarschuwt echter ook dat deze "hardheid" een worst-case scenario is. Het betekent niet dat elke graaf onmogelijk op te lossen is; het betekent alleen dat er specifieke, lastige grafen zijn waar de wiskunde voor klassieke computers vastloopt.

De Kern van het Verhaal

Stuart Hadfields artikel is een waarschuwing voor de quantumcommunity. Het vertelt ons dat naarmate we QAOA krachtiger maken door meer lagen toe te voegen, we niet alleen het probleem moeilijker maken om op te lossen; we maken het probleem van het controleren van ons werk exponentieel moeilijker. We zijn bewogen van een wereld waarin we de quantumdans gemakkelijk konden verifiëren naar een wereld waarin het verifiëren van de dans het oplossen van een telpuzzel vereist die misschien wel het moeilijkste is in de informatica. Het is een herinnering aan het feit dat in de quantumwereld, hoe dieper je gaat, hoe mysterieuzer de wiskunde wordt.

Technische Samenvatting: Het evalueren van QAOA-verwachtingswaarden is #P-hard

Probleemstelling
Het artikel behandelt de computationele complexiteit van het evalueren van verwachtingswaarden voor het Quantum Approximate Optimization Algorithm (QAOA) toegepast op het MaxCut-probleem. Hoewel het evalueren van de kostenverwachtingswaarde $F_p(G; \gamma, \beta) = \langle \psi_p | C_G | \psi_p \rangle$ efficiënt berekenbaar is voor diepte $p=1$ op willekeurige grafen, heeft recent werk vastgesteld dat exacte evaluatie NP-hard wordt voor elke vaste diepte $p \ge 2$ . De centrale vraag die hier wordt onderzocht, is of de hardheid voor $p \ge 2$ beperkt is tot optimalisatie (het vinden van een oplossing) of zich uitstrekt tot tellen (het bepalen van het aantal optimale oplossingen). Specifiek vraagt de auteur zich af of het berekenen van deze verwachtingswaarden #P-hard is, een complexiteitsklasse die algemeen wordt beschouwd als moeilijker dan NP, wat overeenkomt met de moeilijkheid van het tellen van het aantal oplossingen van een constraint satisfaction-probleem.

Methodologie
De auteur verfijnt het mechanisme voor het bewijs van hardheid geïntroduceerd door Wang et al. [5], dat Laurent-polynomen gebruikte om de maximale cut-waarde te herstellen uit de grootste exponent. De aanpak van de auteur omvat de volgende stappen:

Grafenconstructie (Balanced Counting Gadget): In plaats van de asymmetrische gadgets gebruikt in eerder werk, construeert de auteur een specifieke graaf $G(H)$ vanuit een invoer-graaf $H$ . Deze constructie maakt gebruik van:
- Variabele Gadgets: Voor elke knoop in $H$ wordt een gebalanceerde volledige bipartiete graaf $K_{L,L}$ gecreëerd, waarbij $L = O(n)$ .
- Synchrone Edges: Randen die de corresponderende knopen in de $K_{L,L}$ -gadgets van aangrenzende knopen in $H$ verbinden om de oorspronkelijke grafenstructuur te behouden.
- Anker-knopen: Twee universele knopen, $r$ en $s$ , die verbonden zijn met elke knoop in de variabele gadgets en met elkaar.
  Dit zorgt ervoor dat de graaf $G(H)$ een diameter heeft van 2 en dat de maximale cuts strikt beperkt zijn: de $K_{L,L}$ -gadgets moeten volledig worden gesneden, en de ankers moeten aan tegenovergestelde zijden liggen.
Laurent-polynoom Analyse: De kostenverwachtingswaarde (of een specifieke twee-qubit correlator $\langle Z_r Z_s \rangle$ ) wordt uitgedrukt als een Laurent-polynoom in een fasevariabele $z = e^{i\phi}$ . De auteur analyseert de coëfficiënten van dit polynoom.
- Zij identificeren een "extreme coëfficiënt" die overeenkomt met de hoogste graad exponent $D^*$ .
- Door middel van een "reduced path sum"-analyse bewijst de auteur dat de coëfficiënt $a_{D^*}$ niet nul is en direct evenredig is aan het aantal maximale cuts van de oorspronkelijke graaf $H$ , aangeduid als $|\# \text{MC}(H)|$ .
- Specifiek geldt $a_{D^*} = \kappa \cdot |\# \text{MC}(H)|$ , waarbij $\kappa$ een bekende niet-nul algebraïsche factor is die afhankelijk is van de mixer-hoeken en de grootte van de graaf.
Reductie via Interpolatie: De auteur demonstreert dat men, door de QAOA-verwachtingswaarde-oracle te bevragen bij polynomiaal veel verschillende fasewaarden (eenheden van de eenheid), de inverse discrete Fourier-transformatie kan gebruiken om de Laurent-coëfficiënten exact te herstellen. Aangezien de extreme coëfficiënt het aantal maximale cuts codeert, stelt een oracle die in staat is tot exacte evaluatie (of evaluatie met exponentiële precisie) de mogelijkheid om dit aantal te herstellen, waarmee een deterministische polynomial-time Turing-reductie wordt vastgesteld van het #P-harde probleem van het tellen van maximale cuts naar het probleem van het evalueren van QAOA-verwachtingswaarden.

Belangrijkste Bijdragen en Resultaten

Complexiteitsdichotomie: Het artikel stelt een scherpe complexiteitsovergang vast voor QAOA-verwachtingswaarden op ongegewogen eenvoudige grafen:
- $p=1$ : Het probleem zit in FP (polynomial-time berekenbaar).
- $p \ge 2$ : Het probleem is #P-hard onder deterministische polynomial-time Turing-reducties.
Tellen versus Optimalisatie: In tegenstelling tot het eerdere NP-hardheidresultaat dat de waarde van de maximale cut herstelde, toont dit werk aan dat het evalueren van de verwachtingswaarde het mogelijk maakt om het aantal maximale cuts te herstellen. Dit verhoogt de hardheid van optimalisatie naar tellen.
Beperkte Hardheid: De #P-hardheid blijft bestaan, zelfs onder aanzienlijke beperkingen:
- Het is van toepassing op de evaluatie van een enkele aangewezen twee-qubit correlator $\langle Z_r Z_s \rangle$ in plaats van de globale kostenfunctie.
- Het geldt voor een sterk beperkte set algoritmeparameters (vaste mixer-hoeken $\beta_1 = \arctan(1/2)$ , $\beta_2 = \pi/4$ , en gekoppelde kosten-hoeken $\gamma_1 = \gamma_2 = \phi$ ).
- Het is van toepassing op grafen met een diameter van 2 (hoewel deze grafen een hoge graad hebben).
Afgeleiden en Hessians: De auteur breidt deze resultaten uit om aan te tonen dat het berekenen van exacte gradiënten en Hessians van de QAOA-kostenfunctie met betrekking tot de parameters ook #P-hard is.
Exponentiële Precisie: De hardheid strekt zich uit tot het benaderen van de verwachtingswaarde met een exponentieel kleine additieve fout ( $2^{-\alpha N}$ ), aangezien deze precisie voldoende is om de extreme coëfficiënt te onderscheiden en het gehele getal van de count te herstellen via afronding.

Betekenis en Claims
Het artikel beweert een "schone exacte complexiteitsclassificatie" te bieden voor QAOA-verwachtingswaarden. De primaire betekenis ligt in het aantonen dat de overgang van $p=1$ naar $p=2$ niet slechts een verschuiving is van tractabiliteit naar optimalisatie-hardheid (NP-hard), maar een verschuiving naar tellen-hardheid (#P-hard).

De auteur benadrukt dat hun resultaten worst-case uitspraken zijn met betrekking tot specifieate families van hoog-graad grafen en niet impliceren dat het evalueren van QAOA hard is voor alle grafen of typische instanties. Zij merken op dat de hardheid berust op exacte of exponentieel precieze evaluatie; zij beweren niet dat er sprake is van hardheid voor constante of polynomiaal kleine additieve fout-regimes, die relevanter zijn voor de huidige noisy intermediate-scale quantum (NISQ) apparaten.

Verder onderscheidt het papier de bevindingen van quantum supremacy-resultaten gerelateerd aan sampling. Terwijl sampling uit QAOA-outputs bij $p=1$ al klassiek hard is onder bepaalde condities, toont dit werk aan dat het evalueren van de verwachtingswaarde bij $p=2$ voldoende is om #P-harde telproblemen op te lossen. De auteur concludeert dat hun resultaten impliceren dat als men de QAOA-verwachtingswaarden efficiënt tot exponentiële precisie zou kunnen evalueren, de polynomiale hiërarchie zou instorten naar het laagste niveau ($P=PH$). Dit heeft implicaties voor hybride algoritmen die vertrouwen op klassieke verwerking van quantum-verwachtingswaarden, wat suggereert dat dergelijke benaderingen in het slechtste geval fundamentele computationele barrières kunnen ervaren indien een hoge precisie vereist is.