A reduction scheme for general-order Ising-like Hamiltonians in quantum heuristic solvers

Technische Samenvatting: Algemene Hamiltonian-reductie voor Higher-Order Ising-achtige Modellen

Probleemstelling
Het Ising-model is een standaard raamwerk voor het coderen van combinatorische optimalisatieproblemen, waarbij het vinden van de grondtoestand overeenkomt met het vinden van de optimale oplossing. Hoewel heuristische solvers (bijv. quantum annealing, simulated bifurcation) geavanceerd zijn, hebben ze vaak moeite met de combinatorische explosie die inherent is aan grootschalige instanties. Een veelvoorkomende preprocessing-strategie is Hamiltonian-reductie, wat tot doel heeft het aantal logische variabelen te verminderen door subsets van spins te identificeren die een vaste relatieve configuratie behouden in alle grondtoestanden.

Bestaande reductietechnieken, zoals FastHare en roof duality, zijn primair ontworés voor tweede-orde (kwadratische) Ising-modellen. Echter, veel praktische optimalisatieproblemen, waaronder verzadigbaarheid (satisfiability) en hogere-orde netwerkmodellen, formuleren zich van nature als hogere-orde Ising-achtige Hamiltonians die interacties met meerdere lichamen bevatten. Huidige methoden kunnen dergelijke hogere-orde termen niet direct verwerken, en hoewel technieken voor orde-reductie bestaan om hogere-orde problemen om te zetten naar kwadratische problemen, introduceren deze vaak hulpvariabelen, wat de probleemomvang vergroot. Er is een gebrek aan gespecialiseerde Hamiltonian-reductieschema's voor algemene orde-interacties.

Methodologie
De auteurs stellen GeneralHare (GH) voor, een raamwerk dat de theorie van niet-scheidbare groepen (NG's) generaliseert naar willekeurige-orde Ising-achtige modellen. De kernmethodologie bestaat uit drie hoofdcomponenten:

1. Gegeneraliseerde Niet-Scheidbare Groepen (gNG's):
   Het artikel breidt de definitie van NG's (waarbij alle spins in een groep in alle grondtoestanden dezelfde tekenwaarde delen) uit naar gNG's. Een gNG is een subset van spins die een specifieke relatieve configuratie behoudt (bijv. $\sigma_a = -\sigma_b = \sigma_c$) in alle grondtoestanden, of de globale inverse daarvan. Dit maakt het mogelijk om spins te fuseren met complexe interne correlaties, niet alleen identieke exemplaren.

2. Berekenbare Criteria voor Identificatie:
   Het berekenen van de exacte niet-scheidbaarheidsindex (de energieafstand tussen scheidende en niet-scheidende configuraties) is NP-hard. Om het algoritme hanteerbaar te maken, leiden de auteurs gemakkelijk berekenbare ondergrenzen ($\hat{\nu}_H(X)$) af voor de niet-scheidbaarheidsindex.

   • De methode deelt de Hamiltonian op per interactieorde ($m$).
   • Het maakt gebruik van een schatting van de ondergrens die de minimalisatie over alle mogelijke spinconfiguraties vermijdt, maar in plaats daarvan specifieke bisecties van de kandidaatgroep $X$ overweegt.
   • Als de ondergrens $\hat{\nu}_H(X) > 0$, wordt de groep geïdentificeerd als een niet-scheidbare groep. Als $\hat{\nu}_H(X) = 0$, wordt deze behandeld als een "zwak" niet-scheidbare groep.

3. Het GeneralHare Algoritme:
   Het schema werkt iteratief in rondes totdat er geen verdere reducties meer mogelijk zijn:

   • Node Fixatie: Voordat groepen worden geïdentificeerd, worden knopen met lineaire termen (biases) die hun lokale interacties domineren, gefixeerd naar specifieke waarden ($\pm 1$), wat hen effectief verwijdert en de orde van incidentele hyperedges vermindert.
   • Identificatie: Het algoritme scant hyperedges (tot een groottebeperking $\xi$) om gNG's en zwakke gNG's te detecteren met behulp van de afgeleide ondergrens-criteria.
   • Vergroting: Gebruikmakend van de "closure under union"-eigenschap, worden overlappende gNG's samengevoegd tot grotere groepen.
   • Compressie: Geïdentificeerde groepen worden samengevoegd tot enkele knopen. Dit omvat het flippen van spins om relatieve configuraties uit te lijnen, het samenvoegen van knopen en het aggregeren van gewichten van parallelle hyperedges. Additieve constanten die voortvloeien uit dit proces worden bijgehouden om de grondtoestand-correspondentie te bewaren.
   • Optimalisatie: Om de snelheid te verbeteren, beperkt het algoritme de zoekopdrachten tot bijgewerkte buurten en past het simultane samenvoeging toe van onafhankelijke zwakke gNG's.

Belangrijkste Resultaten
De auteurs hebben GeneralHare getest op synthetische hypergrafen (Erdős-Rényi en Scale-Free) en publieke hogere-orde netwerkdatasets (bijv. contactnetwerken, e-mailnetwerken).

• Reductieprestaties:
  • Op synthetische data bereikt GeneralHare significante reductieratio's (tot wel ~50% op ijle scale-free hypergrafen).
  • De reductie-efficiëntie neemt af naarmate de grafiekdichtheid (gemiddelde graad) toeneemt en naarmate de interactieorde stijgt (vierde-orde grafieken vertoonden ongeveer de helft van de reductieratio van derde-orde grafieken).
  • Op real-world datasets varieerden de reductieratio's van 2,1% tot 67,4%, waarbij 5 van de 7 instanties meer dan 20% overschreden.
• Vergelijking met FastHare (Tweede-Orde Geval):
  • Wanneer toegepast op tweede-orde Ising-modellen, presteert GeneralHare beter dan het standaard FastHare algoritme in termen van reductieratio, omdat het meer niet-scheidbare groepen identificeert dankzij de gegeneraliseerde criteria.
  • GeneralHare brengt een hogere computationele runtime met zich mee op zeer kleine grafieken, maar schaalt efficiënt en vertoont een kruispunt (wordt sneller of vergelijkbaar) bij ongeveer 5.000 knopen.
• Integratie met Orde-Reductie:
  • Het artikel evalueert een pipeline die GeneralHare combineert met orde-reductie (kwadratisering) en downstream solvers.
  • Resultaten wijzen erop dat het toepassen van GeneralHare vóór kwadratisering (specifiek met de conservatieve demonstrator GH_minimal) resulteert in een lagere uiteindelijke variabele-overhead vergeleken met het toepassen van FastHare na kwadratisering.
  • De meest effectieve strategie die is geïdentificeerd, is een gecombineerde pipeline: GeneralHare $\to$ Kwadratisering $\to$ FastHare.

Betekenis en Claims
Het artikel claimt dat GeneralHare een fundament legt voor Hamiltonian-reductie in hogere-orde Ising-achtige optimalisatieproblemen. De primaire bijdragen zijn:

1. Theoretische Uitbreiding: Het slaagt erin de niet-scheidbaarheids-theorie te generaliseren van tweede-orde naar willekeurige-orde modellen, waarmee het een gebrek aan dergelijke technieken voor hogere-orde interacties aanpakt.
2. Praktische Efficiëntie: Het biedt een preprocessing-tool die de logische omvang van problemen vermindert, wat potentieel de prestaties van downstream heuristische solvers (zowel klassiek als quantum-inspired) kan verbeteren door de zoekruimte te verkleinen.
3. Preservering van Grondtoestanden: De methode garandeert dat de grondtoestanden van de gereduceerde Hamiltonian overeenkomen met de grondtoestanden van het oorspronkelijke probleem via een expliciete reconstructiekaart.

De auteurs merken op dat hoewel de methode over het algemeen toepasbaar is, de effectiviteit kan variëren afhankelijk van de probleemstructuur (bijv. homogene graadverdelingen in 3-SAT problemen kunnen lagere reductieratio's opleveren). Zij suggereren dat toekomstig werk zich zou kunnen richten op het combineren van deze aanpak met gespecialiseerde solvers zoals SAT-solvers voor specifieke probleemklassen.