A Parameter Setting Heuristic for the Quantum Alternating Operator Ansatz

Technische Samenvatting: Een Heuristiek voor Parameterinstelling voor de Quantum Alternating Operator Ansatz

Probleemstelling
De Quantum Alternating Operator Ansatz (QAOA) is een prominente geparametriseerde kwantumalgoritme voor het oplossen van combinatorische optimalisatieproblemen. Het efficiënt vinden van hoogwaardige parameters ($\vec{\gamma}, \vec{\beta}$) blijft echter een aanzienlijke praktische uitdaging. Het proces van parameterinstelling omvat doorgaans een variationele kwantum-klassieke lus waarbij een klassieke optimizer parameters bijwerkt op basis van de verwachtingswaarde van een kostenfunctie, geëvalueerd op kwanthardware of via een dure klassieke simulatie. Dit proces kampt met problemen zoals barren plateaus, talrijke lokale optima en de exponentiële schaling van de benodigde middelen voor exacte klassieke evaluatie van verwachtingswaarden naarmate het aantal qubits ($n$) of de circuitdiepte ($p$) toeneemt. Bovendien bemoeilijken huidige noisy intermediate-scale quantum (NISQ) apparaten deze uitdagingen door ruis en fouten door eindige bemonstering.

Methodologie
De auteurs stellen een "Homogene Heuristiek voor Parameterinstelling" voor, een klassieke strategie die ontworpen is om de kostbare kwantum of klassieke evaluatie van de verwachtingswaarde van de kostenfunctie te vervangen door een efficiënt klassiek model. De kern van deze aanpak berust op het concept van Perfecte Homogeniteit.

1. Perfecte Homogeniteit: Dit wordt gedefinieerd als een staatseigenschap waarbij alle bitstrings $x$ die dezelfde kostenwaarde $c(x)$ delen, identieke kwantumamplitudes bezitten. Hoewel deze eigenschap exact alleen geldt voor specifieke symmetrische problemen of in het limiet van kleine parameters, suggereren empirische observaties een hoge overlap tussen QAOA-staten en perfect homogene staten in diverse settings.
2. Klassieke Homogene Proxy: De auteurs construeren een klassiek model, de "Klassieke Homogene Proxy" genoemd, die door aanname Perfecte Homogeniteit afdwingt. In deze proxy wordt de staat niet beschreven door $2^n$ amplitudes, maar door een verzameling amplitudes $Q(c)$ voor elke unieke kostenwaarde $c$.
   • De evolutie wordt gemodelleerd vanuit een "sum-of-paths" perspectief. De auteurs vervangen het exacte aantal bitstrings bij een specifieke Hamming-afstand met een specifieke kostenwaarde $c(x)$ door een analytisch afgeleide distributie $N(c'; d, c)$ die alleen afhankelijk is van de kostenklassen.
   • Dit maakt de recursieve berekening van amplitudes $Q_\ell(c)$ mogelijk voor elke laag $\ell$ met behulp van Eq. (5), wat polysnomiaal schaalt met de probleemgrootte $n$ en het aantal unieke kostenwaarden $|C|$, mits $|C|$ polynomiaal groeit met $n$.
3. De Heuristische Lus: De parameterinstellingsprocedure (Algoritme 3) gebruikt deze proxy als de innerlijke subroutine. Een klassieke optimizer zoekt naar parameters $(\vec{\gamma}, \vec{\beta})$ die de "homogene parameter objectieve functie" minimaliseren (een schatting van de verwachtingswaarde van de kosten afgeleid van de proxy). Zodra optimale parameters voor de proxy zijn gevonden, worden deze direct toegepast op het werkelijke QAOA-circuit.

De paper demonstreert hoe de benodigde distributies ($N(c'; d, c)$ en kostenwaarschijnlijkheden $P(c')$) te berekenen voor specifieke klassen van Constraint Satisfaction Problems (CSPs) met willekeurig getrokken clausules, waaronder random $k$-SAT, MaxCut op Erdős-Rényi grafen, en Max-$k$-XOR.

Belangrijkste Bijdragen

• Definitie van Perfecte Homogeniteit en de Proxy: De auteurs formaliseren de voorwaarde van Perfecte Homogeniteit en definiëren een Klassieke Homogene Proxy die zowel staatbeschrijvingen als verwachtingswaarden efficiënt oplevert.
• Polynomiale Schaling: De voorgestelde methode maakt de klassieke berekening van proxy-parameters mogelijk in tijd die polynomiaal schaalt met zowel het aantal variabelen $n$ als de diepte $p$, waardoor de exponentiële groei van middelen geassocieerd met exacte statevector-simulatie wordt vermeden.
• Generalisatie naar CSP-klassen: De paper biedt expliciete afleidingen voor de proxy-distributies voor vier klassen van random CSP's, waarbij wordt aangetoond dat de proxy een hele klasse van problemen kan beschrijven in plaats van een enkele instantie.
• Heuristisch Framework: De auteurs introduceren een volledige workflow (Algoritme 3) die deze proxy integreert in standaard parameteroptimalisatie-lussen, waarbij de flexibiliteit in de keuze van parameter-update-schema's behouden blijft.

Resultaten
De auteurs hebben de heuristiek numeriek geëvalueerd op MaxCut-problemen over ongegewogen Erdős-Rényi random grafen ($G(n, p_e)$):

• Lage Diepte ($p \leq 3$): Voor grafen met $n=20$ vond de heuristiek parameters die benaderingsratio's opleverden die vergelijkbaar zijn met die verkregen via de "parameter transfer" strategie (het overdragen van globaal geoptimaliseerde parameters van kleinere instanties). Het verschil in prestaties was niet statistisch significant, hoewel de heuristiek in sommige gevallen een iets hogere gemiddelde prestatie vertoonde.
• Hoge Diepte ($p \leq 20$): Voor dieptes tot $p=20$ identificeerde de heuristiek succesvol parameters die monotoon stijgende benaderingsratio's opleverden naarmate de diepte toenam. In contrast hiermee faalde een strategie die gebruikmaakt van parameter transfer met identieke klassieke middelen om te convergeren.
• Proxy-nauwkeurigheid: Numerieke analyse toonde aan dat de proxy grote overlappingen behoudt met volledige statevector-simulaties, met name voor lineaire ramp-parameter schema's en in regimes waar de parameter $\gamma$ klein is. De analytische distributies die in de proxy worden gebruikt, bleken sterk te correleren met empirische gemiddelden over random graaf-instanties.

Betekenis en Claims
De paper claimt dat de Homogene Heuristiek een praktisch pad biedt voor parameterinstelling in regimes die momenteel ontoegankelijk zijn voor NISQ-apparaten vanwege ruis en voor klassieke methoden vanwege exponentiële schaling. Door de dure evaluatie van de verwachtingswaarde te vervangen door een polynomiale klassieke proxy, maakt de methode de exploratie van diepere QAOA-circuits (bijv. $p=20$) mogelijk waar eerdere strategieën falen om te convergeren.

De auteurs benadrukken dat hoewel de heuristiek niet garandeert dat er voor elke specifieke instantie optimale parameters worden gevonden, het een robuuste, klasse-brede strategie biedt die competitief presteert met gevestigde methoden bij lage dieptes en deze overtreft bij hogere dieptes. Het werk suggereert dat de aanname van Perfecte Homogeniteit, hoewel niet universeel exact, dient als een voldoende nauwkeurige benadering voor het sturen van parameteroptimalisatie in veel combinatorische optimalisatie-settings, met name die met random constraints. De auteurs concluderen door toekomstige richtingen te schetsen, zoals het integreren van instantie-specifieke informatie in de proxy en het uitbreiden van de aanpak naar andere variationele kwantumalgoritmen zoals de Variational Quantum Eigensolver (VQE).