Generative Quantum Search for Combinatorial Optimization: Learning Shallow Quantum Samplers for Classically Refined Solution Subspaces

Technische Samenvatting: Generatieve Kwantumzoektocht voor Combinatorische Optimalisatie

Probleemstelling
Dit onderzoek onderzoekt of ondiepe kwantumsamplers klassieke samplers kunnen overtreffen in combinatorische optimalisatie door een hogere waarschijnlijkheidsmassa binnen een "klassieke herstelbekken" (classical recovery basin) te plaatsen. De studie past de Generative Quantum Eigensolver + Quantum-Selected Configuration Interaction (GQE+QSCI) architectuur, oorspronkelijk ontwikkeld voor kwantumchemie, aan voor het domein van graafoptimalisatie (specifiek het Maximum Weighted Independent Set, MWIS). De kernhypothese is dat een kwantumsampler een distributie van kandidaatsoluties kan genereren die, wanneer verfijnd door een klassiek herstel- en expansiealgoritme, een hoger succespercentage oplevert dan klassieke samplers.

Methodologie
De auteur stelt het GQO+QSS (Generative Quantum Optimization + Quantum-Selected Search) framework voor, dat een vierfasige pijplijn volgt:

1. Generatief Beleid (Generative Policy): Een machine learning-model (graaf-geconditioneerd beleid) genereert kwantumcircuitprogramma's (bijv. QAOA-parameters).
2. Kwantum Sampling: De circuits worden uitgevoerd op een simulator of QPU (Piast-Q) om bitstrings (kandidaatsoluties) te produceren.
3. Klassiek Herstel (Classical Recovery): Een probleem-specifieke herstelfunctie repareert onhaalbare oplossingen, gevolgd door een lokale expansie (bijv. $r$-flip buurt) om een beperkt zoeksubruimte te creëren.
4. Beperkte Solver (Restricted Solver): Een exacte klassieke solver vindt de optimale oplossing binnen deze beperkte subruimte.

Kern van de Theoretische Formulering
Het artikel formaliseert de vraag naar het "kwantumvoordeel" met behulp van de herstelbekken-massa ($p_r$):
$$p_r(q_\theta, G) = \Pr_{x \sim q_\theta} [x \in A_r(G)]$$
waarbij $A_r(G)$ de verzameling toestanden is die, na herstel en $r$-flip expansie, het globaal optimum bevatten. De succeswaarschijnlijkheid met $B$ shots is $P_{success} = 1 - (1 - p_r)^B$. De studie stelt dat de kritieke metriek niet de grootte van de gesamplede subruimte ten opzichte van de totale ruimte ($|S_Q|/2^n$) is, maar de waarschijnlijkheidsmassa $p_r$ die de sampler in het herstelbekken plaatst.

Experimenteel Protocol

• Datasets: 150 MWIS-instanties waarvan de grondwaarheden zijn gecertificeerd via CBC + brute-force verificatie.
• Baselines: Negen samplers werden vergeleken, inclus$$ief$$ uniform random, greedy, simulated annealing (SA), tabu search, multi-start local search, Metropolis, warm-start QAOA, oracle QAOA (best-of-50 configuraties), en een overeenkomstig geleerd klassiek beleid.
• Restricties: Een vooraf geregistreerd, bevroren protocol met een vast budget van 200 shots per sampler.
• Hardware: Experimenten omvatten simulaties en uitvoering op de Piast-Q trapped-ion processor (20 qubits).

Belangrijkste Resultaten

1. Dominantie van Klassieke Methoden: Tabu search en Simulated Annealing (SA) presteerden significant beter dan alle kwantum en geleerde klassieke samplers bij alle geteste probleemgroottes ($n=16$ tot $n=28$). Tabu search bereikte een herstelbekken-massa ($p_r$) variërend van 0,822 bij $n=16$ tot 0,944 bij $n=18$, met waarden van 0,878 bij $n=20$, 0,943 bij $n=24$, en 0,901 bij $n=28$. SA varieerde van 0,088 tot 0,428 over deze groottes.
2. Onderpresteren van Kwantummethoden: Alle kwantumsamplers (warm-start QAOA, oracle QAOA, en generatieve beleidsmodellen) verloren van zowel SA als Tabu search bij elke probleemgrootte onder het eerlijke, vooraf geregistreerde protocol.
3. Het "Oracle" Artefact: Eerdere positieve resultaten die lieten zien dat QAOA SA overtrof, werden geïdentificeerd als artefacten van per-instantie configuratie-selectie (een "oracle" bovengrens). Wanneer geëvalueerd met willekeurige configuraties (een inzetbare methode), bereikte oracle QAOA een $p_r = 0,014$ bij $n=28$, ver onder de 0,088 van SA.
4. Gelijkwaardigheid van Geleerd Klassiek Beleid: Een geleerd klassiek beleid (140K parameters) behaalde een prestatie die vergelijkbaar is met oracle QAOA ($p_r = 0,005–0,101$ vs. $0,014–0,113$), wat aangeeft dat het kwantumcircuit geen structureel voordeel biedt ten opzichte van een overeenkomstig klassiek model in deze setting.
5. Hardware Robuustheid: Experimenten op Piast-Q toonden 93,4% herstelconsistentie tussen QPU- en simulator-samples, wat de hardware-robuustheid bevestigt maar geen kwantumvoordeel in optimalisatiekwaliteit onthulde.
6. Hersteltransitie: De studie bracht een "hersteltransitie" in kaart waarbij klassiek herstel voldoende is voor $n \le 16$, maar begint te falen voor $n \ge 20$ met 2-flip expansie. Echter, zelfs in dit transitie-regime behielden sterke klassieke baselines (SA, Tabu) een superieure prestatie.

Betekenis en Claims
Dit artikel presenteert zichzelf als een falsificatiestudie. De primaire claim is dat onder strikte, vooraf geregistreerde evaluatie met gematchte geleerde baselines, ondiepe QAOA-afgeleide voorstelverdelingen (proposal distributions) de gematchte klassieke voorstelmodellen niet overtreffen voor het vastleggen van klassieke herstelbekken in MWIS.

• Geen Kwantumvoordeel: De auteur claimt expliciet geen kwantumvoordeel voor de GQO+QSS-architectuur in de geteste regimes.
• Weerlegging van Eerdere Claims: De studie schrijft eerdere positieve resultaten toe aan het "oracle"-effect van het selecteren van de beste configuratie per instantie, wat geen inzetbare methode is.
• Correctie van Metriek: Het artikel betoogt dat de "subspace fraction" ($|S_Q|/2^n$) een tautologische metriek is onder vaste shot-budgetten en dat de herstelbekken-massa ($p_r$) de wetenschappelijk accurate hoeveelheid is om te meten.
• Toekomstige Richting: De auteur suggereert dat voor kwantumsampling waarde moet worden geboden, het consistent meer massa in het herstelbekken moet plaatsen dan sterke klassieke baselines (zoals SA) in regimes waar klassiek herstel faalt ($n \ge 55$), een uitdaging die huidige ondiepe circuits nog niet hebben beantwoord.

De studie concludeert dat hoewel de GQO+QSS-architectuur een geldig framework is voor hybride optimalisatie, huidige ondiepe kwantumsamplers geen structureel voordeel bieden ten opzichte van sterke klassieke stochastische zoekmethoden voor de specifieke taak van MWIS-herstelbekken-capturing.