Multi-Objective Optimization by Quantum-Annealing-Inspired Algorithms

Dit artikel toont aan dat op GPU gebaseerde, door kwantum-annealing geïnspireerde algoritmen (QAIAs) zowel de meest geavanceerde klassieke heuristieken als eerder onderzochte kwantumprocessors overtreffen bij het oplossen van multi-objectieve MaxCut-problemen door aanzienlijk snellere end-to-end uitvoeringstijden te bereiken wanneer volledige verwerkingskosten in aanmerking worden genomen.

De kern

Stel je voor dat je een enorme, chaotische feest wilt organiseren. Je hebt drie verschillende doelen die vaak botsen: je wilt dat de muziek hard staat, het eten goedkoop is en de gasten blij zijn. Je kunt niet alle drie tegelijk maximaliseren; als je meer uitgeeft aan eten, wordt de muziek misschien zachter. Je doel is niet om één "perfect" feestplan te vinden, maar een lijst met de beste mogelijke afwegingen (een "Pareto-front") te vinden, waarbij je één ding niet kunt verbeteren zonder een ander te schaden.

Dit is wat Multi-Objective Optimization (meervoudige doeloptimalisatie) is: het vinden van de beste balans tussen conflicterende doelen.

Dit artikel gaat over een nieuwe, supersnelle manier om die afwegingen te vinden met behulp van een op kwantumtechniek gebaseerd computerprogramma dat draait op een standaard videokaart (GPU). Hier is de uiteenzetting in eenvoudige termen:

Het Probleem: Het Dilemma van de "Feestplanner"

In het verleden probeerden onderzoekers deze problemen op te lossen met twee hoofdtools:

1. Echte Kwantumcomputers: Deze zijn als magische, mysterieuze zwarte dozen die veel mogelijkheden tegelijk kunnen verkennen. Recente studies toonden aan dat ze goed waren in het vinden van feestplannen, maar ze waren traag om op te zetten en vereisten veel extra werk om de resultaten op te schonen.
2. Klassieke Computers: Dit zijn de standaardcomputers die we elke dag gebruiken. Ze zijn betrouwbaar, maar soms traag in het vinden van de beste afwegingen.

De auteurs van dit artikel merkten op dat de eerdere studies die deze twee tools vergeleken, onbillijk waren. Ze telden alleen hoe lang de "magische doos" nodig had om een ruwe lijst met ideeën te spugen, en negeerden de tijd die het kostte om het probleem op te bouwen, de machine te draaien en de lijst op te schonen om de echte winnaars te vinden.

De Oplossing: De "Op Kwantum Gebaseerde" Snelheidssprinter

De auteurs bouwden een nieuw algoritme genaamd QAIA (Quantum-Annealing-Inspired Algorithm). Denk hierbij niet aan een echte kwantumcomputer, maar aan een zeer slimme simulatie daarvan die draait op een krachtige videokaart (GPU) in een gewone computer.

Om deze simulatie nog beter te maken in het vinden van diverse feestplannen, voegden ze een beetje "Gaussisch Ruis" toe.

• De Analogie: Stel je een groep wandelaars voor die proberen de hoogste pieken te vinden in een mistig berggebied. Een standaardalgoritme is als een wandelaar die vastloopt op de eerste heuvel die hij ziet. De methode van de auteurs voegt een "briesje" toe (de ruis) die de wandelaars zachtjes van hun comfortabele plekken duwt, waardoor ze gedwongen worden om verschillende valleien en pieken te verkennen. Dit zorgt ervoor dat ze een bredere variëteit aan de beste afwegingen vinden, niet slechts één of twee.

De Race: Wie is Snelst?

Het team hield een race tussen hun nieuwe methode, echte kwantumcomputers en de beste klassieke methoden.

1. De Sampling-snelheid (Het vinden van Kandidaten):

   • Het Resultaat: Hun op GPU gebaseerde methode was 100 keer sneller dan de echte kwantumcomputers bij het genereren van ruwe lijsten met potentiële oplossingen.
   • De Metafoor: Als de kwantumcomputer een raceauto is die 10 seconden nodig heeft om de motor te starten en een ronde te rijden, dan is de nieuwe methode een Formule 1-auto die al draait en de ronde in een fractie van een seconde voltooit.

2. De End-to-End-tijd (De Volledige Taak):

   • Dit omvat het opbouwen van het probleem, het draaien van de simulatie en het opschonen van de resultaten.
   • Het Resultaat: Hun methode was nog steeds 10 keer sneller dan de beste klassieke algoritmen en aanzienlijk sneller dan de kwantumcomputers wanneer je alles meetelt.
   • De Metafoor: Zelfs na rekening te houden met de tijd die het kost om de auto in te pakken en naar het circuit te rijden, was de GPU-methode de hele reis veel eerder klaar dan de anderen.

De Haken en Ogen: Kwaliteit versus Hoeveelheid

Hoewel de nieuwe methode ongelooflijk snel was in het produceren van cijfers, merkt het artikel een kleine afweging op:

• Echte Kwantumcomputers waren zeer "efficiënt" in die zin dat ze minder totale gokken nodig hadden om de perfecte lijst met afwegingen te vinden.
• De Nieuwe Methode moest een paar meer gokken (samples) doen om dezelfde lijst te vinden, maar omdat het zo ongelooflijk snel was in het maken van die gokken, won het alsnog de race in zijn geheel.

De Conclusie

Het artikel beweert dat voor het specifieke type probleem dat ze testten (MaxCut met meerdere doelen), een standaardcomputer die deze nieuwe "op kwantum gebaseerde" code draait, momenteel het beste beschikbare hulpmiddel is. Het verslaat zowel de dure, trage echte kwantumcomputers als de traditionele klassieke methoden in snelheid en algehele prestaties.

Ze concluderen dat hoewel echte kwantumcomputers veelbelovend zijn, deze "op kwantum gebaseerde" aanpak op reguliere hardware momenteel de kampioen is voor het oplossen van deze complexe afwegingen.

Technische samenvatting

1. Probleemdefinitie

Het artikel behandelt Multi-Objective Optimization (MOO), specifiek het Multi-Objective MaxCut (MO-MaxCut) probleem.

• Context: In tegenstelling tot single-objective optimalisatie, streeft MOO naar het vinden van een set van Pareto-optimale oplossingen (het Pareto-front), waarbij geen enkel doel kan worden verbeterd zonder een ander doel te verslechteren.
• De Uitdaging: Bestaande studies die quantum-oplossers (Gate-based QAOA en Quantum Annealing) vergelijken met klassieke heuristieken, richten zich vaak uitsluitend op sample-snelheid, en negeren de aanzienlijke overheads van modelconstructie, circuit-compilatie en de computatie-intensieve Pareto-filtering (naschakelverwerking) die nodig is om de niet-gedomineerde set uit ruwe samples te extraheren.
• Doel: Het bieden van een rigoureuze end-to-end vergelijking van quantum- en klassieke oplossers, rekening houdend met de totale runtime (modelleren + sampling + filtering) en het evalueren of huidige quantumhardware een praktisch voordeel biedt ten opzichte van state-of-the-art klassieke "quantum-geïnspireerde" algoritmen.

2. Methodologie

De auteurs stellen een GPU-versnelde Quantum-Annealing-Inspired Algorithm (QAIA) voor en evalueren deze, gebaseerd op Simulated Bifurcation (SB).

A. Wiskundige Formulering

• Hamiltoniaan: Het MO-MaxCut-probleem wordt gemapt naar een Ising-model. Voor $K$ doelen minimaliseert het systeem een vector van Hamiltonianen $H(s) = (H_1, \dots, H_K)$.
• Scalarisatie: Om het multi-objective probleem op te lossen met single-objective oplossers, hanteren de auteurs de Weighted Sum Method. Ze genereren gewichtsvector met een Das–Dennis simplex-lattice design om gescalariseerde Hamiltonianen te creëren: $H_{total}(s; c) = \sum c_k H_k(s)$.
• Pareto-filtering: Ruwe samples worden verwerkt via een klassiek Non-dominated Sorting algoritme om gedomineerde oplossingen te filteren en de uiteindelijke Pareto-front benadering te construeren.

B. Het Voorgestelde Algoritme: Noise-Injected Simulated Bifurcation (NI-SB)

De kernoplosser is een variant van het Simulated Bifurcation-algoritme, dat klassieke Hamiltoniaanse dynamica van niet-lineaire oscillatoren simuleert om lage-energietoestanden te vinden.

• Ballistic (bSB) vs. Discrete (dSB): De auteurs maken gebruik van zowel continue (ballistic) als discrete varianten van SB.
• Gaussian Noise Injection: Om het gebrek aan diversiteit in deterministische SB aan te pakken (wat vaak convergeert naar dezelfde oplossing), introduceren de auteurs Gaussian white noise in de impulsvergelijking:
  $$\dot{y}_i = -[a_0 - a(t)]x_i + c_0 \sum J_{ij}\phi(x_j) + \alpha \eta_i$$
  waarbij $\eta_i \sim \mathcal{N}(0, 1)$. Deze "synthetische thermische ruis" laat trajecten toe om diverse gebieden van de oplossingsruimte te verkennen, wat cruciaal is voor het effectief bestrijken van het Pareto-front.
• Hardware-implementatie: Het algoritme is geïmplementeerd op GPUs (NVIDIA RTX 4090), waarbij gebruik wordt gemaakt van enorme parallelisatie om duizenden kandidaat-oplossingen gelijktijdig te verwerken met half-precision (float16) rekenkunde.

3. Belangrijkste Bijdragen

1. End-to-End Benchmarking: Het artikel verschuift de evaluatiemetric van "sampling time" naar totale end-to-end runtime, waarbij expliciet modelconstructie en Pareto-filtering overheads worden opgenomen, die vaak worden weggelaten in claims van quantum-voordeel.
2. Sterke Klassieke Baseline: De auteurs stellen vast dat GPU-versnelde QAIA dient als een formidabele klassieke baseline, die zowel quantumhardware als traditionele klassieke heuristieken overtreft.
3. Noise-Injected SB: De introductie van Gaussische ruis aan SB verbetert de sample-diversiteit voor MOO aanzienlijk, waardoor het algoritme de volledige Pareto-set kan herstellen met minder totale samples in vergelijking met QAOA.
4. Uitgebreide Vergelijking: De studie vergelijkt de voorgestelde methode met:
   • Quantum: D-Wave Advantage/Advantage2 (QA) en IBM Fez (QAOA).
   • Klassieke Heuristieken: DCM, DPA-a, MOEA/D, NSGA-II, NSGA-III en RVEA.

4. Resultaten

De experimenten werden uitgevoerd op MO-MaxCut-instanties met variërende aantallen variabelen ($n$) en doelen ($K=3, 4$).

• Sampling Snelheid:

  • QAIA is ongeveer twee ordes van grootte sneller in het sample-en van kandidaat-oplossingen dan eerder onderzochte quantumprocessors (QA en QAOA).
  • QAIA bereikt het optimale Hypervolume plateau in $10^{-2}$ tot $10^{-1}$ seconden, terwijl QA-systemen seconden tot minuten nodig hebben.

• Sample-efficiëntie & Kwaliteit:

  • QAIA vs. QAOA: QAIA herstelt de volledige Pareto-set met ~10$\times$ minder kandidaten dan QAOA.
  • QAIA vs. QA: Hoewel QA gemiddeld minder samples nodig heeft om de Pareto-set te vinden, compenseert QAIA dit met een veruit superieure sampling-snelheid.

• End-to-End Prestaties:

  • T.o.v. Quantum: QAIA is ~1 orde van grootte sneller dan QA en ~4 ordes van grootte sneller dan QAOA in totale runtime (inclusief filtering).
  • T.o.v. Klassieke Heuristieken: Op dichte 3-doel-instanties tot $n=200$, overtreft QAIA MOEA/D, NSGA-II, NSGA-III en RVEA in zowel runtime als oplossingskwaliteit (Hypervolume).
    • Voorbeeld: Voor $n=200$ bereikte QAIA 99% van het optimale Hypervolume in <1 seconde, terwijl klassieke heuristieken **9–11 seconden** nodig hadden en lagere Hypervolume-ratio's bereikten (60–93%).

• Schaalbaarheid:

  • De methode slaagde erin $n=200$ (volledige graaf) te verwerken, wat de huidige embeddinglimieten van D-Wave's Pegasus- en Zephyr-topologieën (ongeveer 180–193 knopen) overstijgt.

5. Betekenis en Conclusie

• Herdefiniëren van Quantum-voordeel: Het artikel betoogt dat voor huidige MO-MaxCut-benchmarks, GPU-versnelde quantum-geïnspireerde oplossers momenteel een sterkere end-to-end baseline bieden dan beschikbare quantumhardware. Het "quantum-voordeel" in sampling-snelheid wordt geneutraliseerd door de overheads van quantum-executie en de superieure parallelisatie van moderne GPUs.
• Praktische Nut: De resultaten suggereren dat voor praktische multi-objective optimalisatietaken, klassieke Ising-oplossers (specifiek NI-SB) momenteel het meest efficiënte hulpmiddel zijn, met snelle convergentie en hoge oplossingskwaliteit.
• Toekomstige Richtingen: De auteurs benadrukken de noodzaak van metrics die sampling-snelheid scheiden van sample-kwaliteit (bijv. nondominated yield, Pareto-set recall). Ze suggereren ook deze methoden te testen op bredere MOO-problemen buiten MaxCut en andere QAIA-varianten te onderzoeken (bijv. thermal-assisted SB).

Kortom, dit werk toont aan dat hoewel quantumhardware verbetert, klassieke quantum-geïnspireerde algoritmen die op GPUs draaien momenteel het landschap voor multi-objective optimalisatie domineren in termen van totale tijd tot oplossing en schaalbaarheid.