Unfair Sampling of Quantum Annealing in Weighted Graph Bipartitioning Problems

Titel: Onbillijk Sampling van Quantum Annealing in Gewogen Graaf Bipartitieproblemen

Auteurs: Shunta Ide en Shu Tanaka (Keio Universiteit, Japan)

1. Het Probleem

Quantum Annealing (QA) is een veelbelovende aanpak voor het oplossen van combinatorische optimalisatieproblemen. In ideale, gesloten systemen garandeert het adiabatische theorema dat het systeem in de grondtoestand blijft bij voldoende trage evolutie. Echter, in de praktijk vertoont QA een fenomeen genaamd onbillijk sampling (unfair sampling).

• Definitie: Wanneer een probleem meerdere ontaarde grondtoestanden (degenerate ground states) heeft, worden deze niet met gelijke waarschijnlijkheid gesampled, zelfs niet bij zeer lange annealing-tijden.
• Gevolgen: Dit is problematisch voor toepassingen die diversiteit in oplossingen vereisen, zoals het beoordelen van oplossingsdiversiteit of het tellen van combinaties (combinatorial counting).
• Specifieke Uitdaging: Voor beperkte combinatorische optimalisatieproblemen (constrained problems), zoals het bipartitieprobleem, wordt de beperking vaak opgelost via de strafmethode (penalty method). Hierbij wordt een strafterm toegevoegd aan de Hamiltoniaan met een straffactor ($\mu$). Het is onbekend hoe deze straffactor de onbillijkheid van het sampling beïnvloedt.

2. Methodologie

De auteurs onderzoeken dit probleem aan de hand van het Gewogen Graaf Bipartitieprobleem (Weighted Graph Bipartitioning - GBP). Dit is een representatief beperkt probleem waarbij de hoekpunten van een graaf in twee gelijke subsets moeten worden verdeeld om de som van de gewichten van de snijlijnen te minimaliseren.

• Hamiltoniaan Opstelling:
  • Het doel is geëncodeerd als $H_{obj}$.
  • De beperking (gelijke grootte van subsets) wordt toegevoegd via een strafterm $H_{const}$.
  • De totale probleem-Hamiltoniaan is: $H_p = H_{obj} + \mu H_{const}$.
  • De straffactor wordt ontbonden als $\mu = \mu_{opt} + \mu_+$, waarbij $\mu_{opt}$ de minimale straffactor is voor haalbaarheid en $\mu_+$ de extra straf is.
• Simulaties:
  • Numerieke simulaties werden uitgevoerd door de tijdsafhankelijke Schrödinger-vergelijking op te lossen met QuTiP.
  • Er werd gebruik gemaakt van een schaalanalyse op willekeurig gegenereerde instanties met $N$ spins (waarbij $N \in \{4, 6, 8, 10, 12\}$).
• Experimenten op Hardware:
  • Experimenten werden uitgevoerd op het D-Wave Advantage2 System 1.13.
  • Technieken zoals Parallel Annealing (gebruik van meerdere embeddings) en Spin Reversal Transformation (SRT) werden toegepast om systematische fouten te minimaliseren en de kans op de grondtoestand te maximaliseren.
• Meting van Billijkheid:
  • De Shannon-entropie ($S$) van de genormaliseerde grondtoestandsverdeling wordt gebruikt als maatstaf.
  • Maximale entropie ($S = \log_2 D$, waarbij $D$ het aantal ontaarde toestanden is) duidt op perfect billijk sampling. Lagere waarden duiden op bias.

3. Belangrijkste Bijdragen en Resultaten

A. Analyse van een Enkele Instantie (Simulatie)

• Observatie: Zelfs bij lange annealing-tijden is de verdeling van de grondtoestanden niet uniform voor lage straffactoren.
• Effect van $\mu_+$:
  • Bij korte annealing-tijden ($T \lesssim 10^3$) leidt het verhogen van de straffactor tot verbeterde sampling-billijkheid, maar ten koste van de totale waarschijnlijkheid om de grondtoestand te vinden ($P_{GS}$ daalt). Er is dus een trade-off.
  • Bij lange annealing-tijden (quasi-adiabatisch regime, $T \approx 10^4$) blijft $P_{GS}$ dicht bij 1, terwijl het verhogen van de straffactor de entropie verhoogt. Hierdoor wordt de trade-off opgeheven en verbetert de billijkheid zonder verlies van succeskans.

B. Experimenten op D-Wave Hardware

• De experimenten bevestigden dat onbillijk sampling ook optreedt op echte hardware, hoewel de mate van bias lager is dan in de simulatie (waarschijnlijk door thermische relaxatie en ruis).
• De trend is kwalitatief hetzelfde: het verhogen van de straffactor vermindert de sampling-bias, maar verlaagt de grondtoestandskans bij hoge waarden van $\mu$.

C. Schaalanalyse (Scaling Analysis)

• Er werd een analyse uitgevoerd op 100 willekeurige instanties voor elke systeemgrootte tot $N=12$.
• Resultaat: De trend dat een hogere straffactor leidt tot meer billijkheid, is niet universeel geldend voor alle instanties.
• Statistiek: Voor de grootste onderzochte systeemgrootte ($N=12$) vertoont meer dan 70% van de instanties een monotoon toenemende entropie (verbeterde billijkheid) naarmate de straffactor toeneemt.
• Tabel I toont dat het percentage instanties met monotoon toenemende entropie daalt van 100% bij $N=4$ naar ongeveer 74% bij $N=12$.

4. Betekenis en Conclusie

• Nieuwe Rol van Straffactoren: Traditioneel wordt de straffactor in beperkte optimalisatieproblemen alleen afgesteld om haalbaarheid te garanderen. Dit paper toont aan dat de straffactor ook fungeert als een controleparameter voor sampling-billijkheid.
• Praktische Implicatie: Voor toepassingen die diversiteit vereisen, kan het verhogen van de straffactor een effectieve strategie zijn, mits rekening wordt gehouden met de mogelijke daling in de totale kans op een succesvolle oplossing (vooral bij kortere annealing-tijden).
• Theoretische Lekkernij: De resultaten onderstrepen de noodzaak van een dieper theoretisch begrip van onbillijk sampling, mogelijk via ontaarde perturbatietheorie, vooral binnen het kader van beperkte problemen.
• Toekomstperspectief: De auteurs wijzen op de noodzaak om dit onderzoek uit te breiden naar andere beperkte problemen en om te kijken naar "structure-aware drivers" (zoals de XY-mixer) die beperkingen inherent respecteren, wat de sampling-bias mogelijk verder kan beïnvloeden.

Samenvattend: Dit werk levert het eerste systematische bewijs dat de straffactor in quantum annealing voor beperkte problemen een directe invloed heeft op de eerlijkheid van het sampling van ontaarde grondtoestanden, wat nieuwe kansen biedt voor het optimaliseren van QA voor diversiteitsgerichte taken.