Technische Samenvatting: Quantum-Informed Surrogate Sampling (QISS) voor Combinatorische Optimalisatie

1. Probleemstelling

Combinatorische optimalisatieproblemen, zoals Maximum Cut (MaxCut) en Maximum Independent Set (MIS), zijn op grote schaal computationeel uitdagend. Hoewel het Quantum Approximate Optimization Algorithm (QAOA) een veelbelovende hybride quantum-klassieke aanpak biedt, wordt de prestatie op nabije hardware beperkt door ruis en coherentiebeperkingen. Deze beperkingen beperken QAOA-implementaties doorgaans tot ondiepe circuits (lage diepte $p$).

Een fundamentele beperking van ondiepe QAOA is lokaliteit: voor ijle grafen (sparse graphs) is de "lichtkegel" van het circuit begrensd door de diepte $p$, niet door de probleemgrootte $N$. Bijgevolg faalt QAOA met een vaste-$p$ vaak in het exploiteren van globale probleemstructuren en erft het beperkingen die vergelijkbaar zijn met lokale klassieke algoritmen. Bovendien is de volledige outputverdeling van een quantumtoestand over het algemeen klassiek onhandelbaar om te samplen, en het quantumapparaat zelf kan niet direct hoogwaardige oplossingen produceren wanneer het beperkt is tot ondiepe dieptes.

Het artikel adresseert de behoefte aan een methode die gebruikmaakt van de specifieke sterktes van nabije quantumapparaten—het efficiënt schatten van laag-orde lokale statistieken—terwijl de generatie van kandidaatsoplossingen wordt gedelegeerd aan schaalbare klassieke post-processing.

2. Methodologie: Quantum-Informed Surrogate Sampling (QISS)

De auteurs stellen Quantum-Informed Surrogate Sampling (QISS) voor, een post-processing framework dat kandidaatsoplossingen genereert uit laag-gewicht quantumcorrelaties zonder een expliciete afhankelijkheid van de combinatorische probleemstructuur tijdens de samplingfase te vereisen.

Kernworkflow

1. Quantum Schatting: Een ondiep QAOA-circuit (diepte $p$) wordt uitgevoerd op een quantumapparaat (of gesimuleerd) om een geselecteerde set laag-gewicht verwachtingswaarden (correlatoren) $\mu_{S_\alpha}$ te schatten:
   $$\mu_{S_\alpha} = \langle \psi_p(\gamma, \beta) | \prod_{i \in S_\alpha} Z_i | \psi_p(\gamma, \beta) \rangle$$
   Het artikel richt zich op gewichten $|S_\alpha| \in \{1, 2\}$. Deze waarden zijn toegankelijk via herhaalde metingen en zijn vatbaar voor foutenmitigatie.

2. Constructie van de Surrogate Verdeling: Een klassieke factorverdeling $P(z)$ wordt geconstrueerd over de oplossingsruimte $\{-1, +1\}^N$ met behulp van deze gemeten correlatoren als parameters:
   $$P(z) \propto \prod_{S_\alpha \in \mathcal{S}} \left( 1 + \mu_{S_\alpha} \chi_{S_\alpha}(z) \right)$$
   waarbij $\chi_{S_\alpha}(z) = \prod_{i \in S_\alpha} z_i$ de pariteitsfunctie is. Deze verdeling is equivalent aan een Gibbs-verdeling van een effectieve Ising-Hamiltoniaan $H'$ met koppelingen $J_{S_\alpha} = -\text{arctanh}(\mu_{S_\alpha})$.

3. Klassieke Sampling: Kandidaatsoplossingen worden getrokken uit $P(z)$ met behulp van Markov-chain Monte Carlo (MCMC). De sampling maakt gebruik van single-site conditionele updates, wat efficiënt is omdat de conditionele waarschijnlijkheid voor een spin-flip alleen afhangt van de lokale factoren die betrokken zijn bij die spin. De normalisatieconstante (partitiefunctie) is nooit vereist.

4. Correlator Selectie: Het artikel maakt onderscheid tussen twee sets correlatoren:

   • Edge Set ($\mathcal{S} = E \cup V$): Alleen directe randen van de probleemgraf. Op lokaal boom-achtige grafen reproduceert dit de QAOA-momenten zonder verbetering.
   • Augmented Set ($\mathcal{S}' = E' \cup V$): Bevat alle paren $(i, j)$ binnen een lichtkegelafstand $d_G(i, j) \le 2p$. Dit creëert een dichte, niet-boom-achtige factorgraf, waardoor de surrogate impliciet hogere-orde correlaties kan vangen en oplossingen kan generen die superieur zijn aan de ruwe QAOA-output.

Belangrijkste Kenmerken

• Training-Vrij: De methode gebruikt vaste, boom-optimale QAOA-hoeken (uit Ref. [61]), wat geen variationele optimalisatie van de surrogate vereist.
• Modulariteit: De samplingstap is onafhankelijk van de kostenfunctie; het vereist alleen de correlatoren.
• Ruisresistentie: De mapping van correlatoren naar koppelingen ($\text{arctanh}$) is vloeiend, wat de surrogate robuust maakt tegen ruis in de gemeten statistieken.

3. Belangrijkste Bijdragen en Resultaten

A. MaxCut op 3-Reguliere Grafen

• Prestaties vs. Vanilla QAOA: Wanneer de augmented correlator set (alle paren binnen afstand $2p$) wordt gebruikt, presteert QISS aanzienlijk beter dan vanilla QAOA. Specifiek bereikt QISS, gebruikmakend van correlatoren van een diepte $p=3$ of $p=4$ QAOA-circuit, gemiddelde cut-fracties die de vanilla QAOA overtreffen bij een diepte $p=17$ (de grootste diepte waarvoor boom-optimale hoeken bekend zijn).
• Warm-Start Integratie: De methode werd gecombineerd met Regularized Warm-Start QAOA (RWS-QAOA). Zelfs bij ondiepe dieptes ($p=1, 2$) verbeterde de QISS post-processing de kwaliteit van de RWS-QAOA oplossingen, waardoor de benaderingsratio dicht bij de optimale grens kwam.
• Hardware Validatie: Experimenten werden uitgevoerd op de 54-qubit IQM Emerald QPU. De resultaten toonden aan dat QISS zeer ruisresistent is. De benaderingsratio's verkregen uit ruwe, ruisgevoelige QPU-correlatoren waren bijna ononderscheidbaar van de ratio's verkregen uit ruisloze simulaties. De ruis van het apparaat werd effectief "weggewassen" door de post-processing, waardoor foutenmitigatie grotendeels irrelevant werd voor de uiteindelijke oplossingskwaliteit in dit regime.
• Schaalbaarheid: De methode behield prestaties tot $N=140$ (beperkt door het aantal beschikbare qubits na variabele bevriezing), waarbij de benaderingsratio's stabiel bleven en ruim boven de standaard SDP-garanties lagen.

B. Maximum Independent Set (MIS)

• Constraint Afhandeling: In tegen tegenstelling tot MaxCut is MIS een geconstrueerd probleem. QISS-samples kunnen conflicten bevatten (aangrenzende knopen die beide zijn geselecteerd). De auteurs introduceerden een eenvoudige post-processing pruning-routine om conflicten op te lossen en geldige knopen gulzig toe te voegen.
• Prestaties: Voor MIS resulteerde het gebruik van enkel edge-correlatoren in prestaties die slechter waren dan vanilla QAOA vanwege het gebrek aan $Z_2$-symmetrie en overlappende factoren. Echter, het gebruik van de augmented set van correlatoren in combinatie met de pruning-routine stelde QISS in staat om standalone QAOA te overtreffen en te concurreren met state-of-the-art klassieke heuristieken (bijv. linear-prioritized search en quantum-enhanced greedy algoritmen).

C. Vergelijking met Klassieke Solvers

QISS werd vergeleken met Simulated Annealing (SA) en de Burer–Monteiro (BM) rank-twee relaxatie van de Goemans–Williamson SDP.

• QISS gecombineerd met RWS-QAOA produceerde resultaten die concurrerend waren met de BM-solver.
• In tegenstelling tot klassieke samplers waarvan de prestaties afnemen naarmate het systeem groter wordt onder een vaste tijdbudget, maakt QISS gebruik van de lokaliteit van QAOA-correlaties, die stabiel blijven met $N$.

4. Betekenis en Claims

Het artikel claimt dat QISS een nieuw regime vestigt voor nabije optimalisatie waarbij ondiepe quantumcircuits niet dienen als directe samplers, maar als generatoren van informatieve statistieken voor schaalbare klassieke sampling.

• Taakverdeling: Het quantumapparaat wordt benut voor zijn vermogen om efficiënt laag-orde, lokale observabelen te schatten (die robuust zijn tegen ruis en onafhankelijk van de systeemgrootte in de kosten per sample), terwijl de klassieke computer de complexe taak afhandelt om deze statistieken te synthetiseren tot globale oplossingen.
• Ruisresistentie: Een cruciale bevinding is dat de surrogate verdeling zo robuust is dat zij bijna optimale oplossingen kan herstellen uit ruwe, ongemitigeerde hardware-data. Dit suggereert dat voor bepaalde optimalisatietaken de overhead van complexe foutenmitigatie onnodig kan zijn als er een robuuste post-processing laag zoals QISS wordt toegepast.
• Schaalbaarheid: De aanpak vermijdt de exponentiële schaling van klassieke contractie voor diepe circuits door te vertrouwen op ondiepe circuits en klassieke MCMC, wat een pad biedt om grotere problemen op te lossen dan directe quantum-sampling zou toelaten op de huidige hardware.

De auteurs concluderen dat hoewel QISS steunt op de specifieke structuur van de gemeten correlaties, het een praktische, training-vrije en hardware-efficiënte route biedt om de optimalisatieprestaties op nabije quantumapparaten te verbeteren.