Towards High Performance Quantum Computing (HPQ): Parallelisation of the Hamiltonian Auto Decomposition Optimisation Framework (HADOF)

Dit artikel toont aan dat het paralleliseren van het Hamiltonian Auto Decomposition Optimisation Framework (HADOF) over enkele en meerdere IBM-quantumprocessors de wandkloktijd voor het oplossen van grootschalige combinatorische optimalisatieproblemen, waaronder reële genoomassemblage-instanties, aanzienlijk verkort, terwijl de oplossingskwaliteit behouden blijft en vooruitgang wordt geboekt richting high-performance quantum computing.

De kern

Stel je voor dat je probeert een enorme, ongelooflijk complexe legpuzzel op te lossen. Dit is niet zomaar een puzzel; het is een "Quantumpuzzel" die een reëel wereldprobleem vertegenwoordigt, zoals het bepalen van de juiste volgorde van DNA-strengen om een genoom samen te stellen.

Het probleem is dat de puzzel te groot is voor één persoon (of één enkele quantumcomputer) om in handen te houden. De stukjes zijn te talrijk, en het "ruis" in de kamer (hardwarefouten) maakt het moeilijk om het beeld helder te zien. Als je probeert de hele puzzel op één klein tafeltje te forceren, past hij niet en zul je waarschijnlijk fouten maken.

Dit artikel introduceert een nieuwe strategie genaamd HADOF (Hamiltonian Auto Decomposition Optimisation Framework) om dit op te lossen. Hier is hoe het werkt, met behulp van eenvoudige analogieën:

1. Het Probleem: De "Te-Groot-Om-Het-Houden"-Puzzel

Huidige quantumcomputers zijn als kleine, lawaaierige werkbanken. Ze kunnen slechts een paar puzzelstukjes tegelijk vasthouden. Als je probeert een enorm probleem (zoals een genoom met duizenden DNA-fragmenten) in één keer op zo'n werkbank op te lossen, raakt de computer overweldigd, worden de stukjes door "ruis" door elkaar gehusseld, en faalt de oplossing.

2. De Oplossing: Het Opbreken in "Mini-Puzzels"

In plaats van te proberen de enorme puzzel in één keer op te lossen, fungeert HADOF als een meester-organisator. Het breekt de enorme puzzel op in honderden kleine, hanteerbare "mini-puzzels" (subproblemen).

• De Magische Truc: Het hakt de puzzel niet zomaar willekeurig kapot. Het gebruikt een slim systeem om te kijken naar de stukjes die je al hebt gelegd en gebruikt die informatie om de volgende mini-puzzel op te lossen.
• De Iteratie: Het lost een mini-puzzel op, leert ervan, werkt zijn begrip van het hele beeld bij, en lost vervolgens de volgende op. Het herhaalt dit totdat het hele beeld helder is.

3. De Nieuwe Twist: De "Assemblagelijn" (Parallelisatie)

Voorheen werkte deze methode als een enkele arbeider op een assemblagelijn: mini-puzzel #1 oplossen, dan #2, dan #3. Dit kost veel tijd.

De auteurs van dit artikel hebben het systeem opgewaardeerd om te werken als een drukke fabriek met meerdere assemblagelijnen.

• Enkele Arbeider versus Team: In plaats van dat één persoon de mini-puzzels één voor één oplost, gebruikten ze een team van arbeiders (meerdere quantumcomputers, of QPU's) om verschillende mini-puzzels op exact hetzelfde moment op te lossen.
• Het Resultaat: Ze ontdekten dat door het gebruik van een team van vier quantumcomputers, ze de klus 3 tot 4 keer sneller konden klaren dan met slechts één. Zelfs met het gebruik van slechts één computer, maar door het werk parallel te organiseren, werd het 3 keer sneller.

4. De Reële Test: Het Opnieuw Samenstellen van een DNA-"Verhaal"

Om te bewijzen dat dit in de echte wereld werkt, testte het team het op een specifiek biologisch probleem: Genoomassemblage.

• De Analogie: Stel je voor dat je een boek hebt verscheurd in duizenden kleine strookjes papier (DNA-sequenties). Je taak is om ze in de juiste volgorde weer aan elkaar te plakken om het verhaal te kunnen lezen.
• De Test: Ze namen een echte biologische dataset (een virus genaamd $\phi$X174) en probeerden deze opnieuw samen te stellen met hun nieuwe "team van quantumcomputers".
• De Uitkomst:
  • Snelheid: De parallelle aanpak was veel sneller in het behalen van een resultaat.
  • Kwaliteit: Hoewel de lawaaierige quantumcomputers geen perfecte score van 100% haalden (vanwege de hardware-"ruis"), vonden ze toch zeer goede oplossingen. Sterker nog, meer dan 50% van de oplossingen die ze genereerden, was goed genoeg om met standaard nabewerkingsgereedschappen naar het perfecte antwoord te worden gecorrigeerd.
  • Vergelijking: Toen ze probeerden de hele DNA-puzzel op één enkele quantumcomputer op te lossen zonder deze op te breken, slaagde de computer er niet in een goede oplossing te vinden. De "breek-het-op"-methode (HADOF) slaagde waar de "alles-in-één"-methode faalde.

5. Het Grote Plaatje: "High Performance Quantum" (HPQ)

De auteurs noemen deze aanpak High Performance Quantum (HPQ) computing.

• Denk eraan als het verschil tussen een enkele persoon die probeert een berg zand met een lepel te verplaatsen versus een vloot vrachtwagens die samenwerken.
• Het artikel betoogt dat we, om quantumcomputers echt bruikbaar te maken voor grote problemen, niet alleen kunnen wachten tot ze groter en stiller worden. We moeten veranderen hoe we ze gebruiken: door problemen op te breken in kleine stukjes en ze parallel op te lossen over veel machines heen.

Samenvatting van Beweringen

• Snelheid: Het gebruik van meerdere quantumcomputers parallel maakt het oplossen van deze problemen 3–4 keer sneller.
• Schaalbaarheid: Deze methode stelt ons in staat problemen op te lossen (zoals 500 variabelen) die momenteel te groot zijn voor één enkele quantumcomputer om aan te kunnen.
• Nauwkeurigheid: Zelfs met lawaaierige, imperfecte hardware vindt deze methode betere oplossingen dan het proberen om het hele probleem in één keer op te lossen.
• Reële Toepassing: Het heeft dit succesvol gedemonstreerd op een reële taak voor genoomassemblage, wat aantoont dat het niet slechts een theorie is, maar een werkend hulpmiddel.

Kortom, het artikel zegt: "Probeer niet de hele olifant in één hap te eten. Breek het op in kleine stukjes, en laat een team van quantumcomputers ze allemaal tegelijk opeten. Het is sneller, en het werkt beter."

Technische samenvatting

1. Probleemstelling

De praktische toepassing van quantumoptimalisatie voor combinatorische problemen (geformuleerd als Quadratic Unconstrained Binary Optimization, of QUBO) wordt momenteel beperkt door de beperkingen van Noisy Intermediate-Scale Quantum (NISQ)-apparaten. Belangrijke beperkingen zijn:

• Beperkt Aantal Qubits: Huidige hardware kan geen grote QUBO-problemen hosten die honderden variabelen vereisen.
• Hardware-ruis: Ruisaccumulatie in diepe circuits verslechtert de oplossingskwaliteit.
• Schaalbaarheid: Bestaande decompositiemethoden (zoals HADOF) zijn voornamelijk sequentieel en slagen er niet in om de parallelisatie te benutten die beschikbaar is in gedistribueerde quantumarchitecturen of High Performance Computing (HPC)-resources.
• Simulatiegrenzen: Het klassiek simuleren van grote quantumcircuits is rekenkundig duur en geheugenintensief.

Het paper adresseert deze problemen door het Hamiltonian Auto Decomposition Optimisation Framework (HADOF) uit te breiden om parallelle uitvoering te ondersteunen over enkele en meerdere Quantum Processing Units (QPUs), met als doel High Performance Quantum (HPQ) computing te bereiken.

2. Methodologie

Kernkader: HADOF

HADOF decomposeert een globale QUBO-Hamiltoniaan in kleinere, hanteerbare sub-Hamiltonianen die iteratief kunnen worden opgelost.

1. Decompositie: Het globale probleem wordt opgesplitst in subproblemen (subsets van variabelen).
2. Iteratief Oplossen: Elk subprobleem wordt opgelost met een quantumoptimizer (QAOA).
3. Contextintegratie: De verwachte waarden ($E[x_i]$) van variabelen uit opgeloste subproblemen worden gebruikt om de context voor volgende subproblemen te benaderen.
4. Aggregatie: Oplossingen worden samengevoegd om een globale oplossing te vormen.

De Parallelle Uitbreiding

De auteurs introduceren een geparalleliseerde versie van HADOF die op twee belangrijke punten verschilt van de sequentiële baseline:

• Onafhankelijke Generatie: In elke iteratie worden alle sub-Hamiltonianen gelijktijdig gegenereerd met behulp van verwachte waarden uit de vorige iteratie (in plaats van waarden sequentieel bij te werken binnen de huidige iteratie).
• Asynchrone Uitvoering: Subcircuits worden gelijktijdig opgelost. Dit maakt mogelijk:
  • Intra-QPU Parallelisme: Het draaien van meerdere taken op een enkele QPU (benutting van de scheduler).
  • Inter-QPU Parallelisme: Het verdelen van taken over meerdere distincte QPUs (bijv. IBM Kingston, Pittsburgh, Fez, Marrakesh).

Implementatiedetails

• Optimizer: Gebruikt een gedigitaliseerde QAOA-aanpak met Trotterized Annealing Parametrization om klassieke optimalisatielussen voor parameters $\beta$ en $\gamma$ te vermijden.
• Circuitdiepte: Circuits worden laag voor laag opgebouwd (tot 5 lagen). In elke iteratie wordt één laag toegevoegd aan alle subcircuits.
• Subprobleemgrootte: Vastgesteld op 5 qubits ($k=5$) om hoge fideliteit op huidige hardware te behouden.
• Doeltoepassing: Genoomassemblage, gemodelleerd als een Travelling Salesman Problem (TSP) op een overlapgrafiek. Het probleem wordt gecodeerd in een QUBO waarbij het doel is om het Hamiltonpad te vinden.

3. Belangrijkste Bijdragen

1. Eerste Real-Device HADOF-implementatie: De studie verplaatst HADOF van theoretische simulatie naar uitvoering op echte IBM QPUs (Kingston, Pittsburgh, Fez, Marrakesh).
2. Parallelisatiestrategie: Demonstreert een kader voor gelijktijdige uitvoering van gedecomposeerde subproblemen, met aanzienlijke snelheidswinst in wandkloktijd zonder in te leveren op oplossingskwaliteit.
3. HPQ-Paradigma-validatie: Positioneert HADOF als een levensvatbare weg naar High Performance Quantum computing door algoritmische decompositie te integreren met systeemniveau-parallelisme.
4. Real-world Toepassing: Past het kader succesvol toe op een genoomassemblageprobleem (ϕX174 bacteriofaag), waarmee de bruikbaarheid in computationele biologie wordt aangetoond.
5. Benchmarking: Biedt een uitgebreide vergelijking tussen Sequentieel HADOF, Parallel HADOF (Enkele en Multi-QPU), Standaard Full-Circuit QAOA en Klassiek Gesimuleerd Temperen.

4. Belangrijkste Resultaten

Snelheid en Efficiëntie

• Wandkloktijd:
  • Multi-QPU Parallel: Bereikte een 3–4× reductie in wandkloktijd vergeleken met sequentiële uitvoering op echte hardware.
  • Single-QPU Parallel: Bereikte tot een 3× snelheidswinst zelfs op één enkel apparaat door efficiënte taakcoördinatie.
  • Simulatie: Voorspelde >5× snelheidswinst in parallelle simulatiemodi.
• QPU-gebruik: Hoewel de totale QPU-gebruikstijd evenredig blijft met het aantal circuits, wordt de makespan (totale tijd tot oplossing) drastisch verkort, waardoor de aanpak praktisch is voor tijdgevoelige toepassingen.

Nauwkeurigheid en Robuustheid

• T.o.v. Standaard QAOA: HADOF presteert aanzienlijk beter dan full-circuit QAOA op echte hardware.
  • De nauwkeurigheid van standaard QAOA daalde tot bijna nul (bijv. 0,02) voor problemen met 50 variabelen op ruisgevoelige hardware door ruisaccumulatie.
  • HADOF behield >0,80 nauwkeurigheid op echte hardware voor vergelijkbare groottes.
• Ruisresistentie: Decompositie beperkt de circuitdiepte, waardoor de exponentiële verslechtering van nauwkeurigheid die wordt gezien in monolithische circuits wordt voorkomen.
• Genoomassemblage Case Study:
  • Ideale Simulatie: Zowel sequentieel als parallel HADOF bereikte 100% beste nauwkeurigheid (overeenkomend met Gesimuleerd Temperen).
  • Echte Hardware: De beste nauwkeurigheid bleef concurrerend (0,88–0,91), hoewel de frequentie van het vinden van de exacte grondtoestand door ruis naar nul daalde. Echter, >52% van de bemonsterde oplossingen kon worden nageprocesseerd om de juiste sequentie te herstellen met standaard bio-informatica-tools (GFAtools).

Schaalbaarheid

• HADOF slaagde erin QUBO-problemen op te lossen met tot 500 variabelen in simulatie en 300 variabelen op echte hardware met uitsluitend 5-qubit circuits.
• Standaard full-circuit QAOA is beperkt tot ~50 variabelen op dezelfde hardware door connectiviteits- en embedding-beperkingen.

5. Betekenis en Conclusie

Dit onderzoek toont aan dat decompositie en parallelisme niet louter oplossingen zijn voor huidige hardwarebeperkingen, maar fundamentele mogelijkmakers van praktisch quantumvoordeel.

• Schaalbaarheid: HADOF omzeilt de fysieke qubitlimieten van huidige apparaten, waardoor het oplossen van problemen mogelijk is die veel groter zijn dan wat de hardware van nature kan ondersteunen.
• HPQ-Alignement: Het kader sluit aan bij het opkomende High Performance Quantum computing-paradigma, en toont aan dat gedistribueerde quantumarchitecturen aanzienlijke prestatiewinst kunnen leveren.
• Praktische Haalbaarheid: Door de methode succesvol toe te passen op genoomassemblage, bewijst het paper dat quantumoptimalisatie kan worden geïntegreerd in real-world wetenschappelijke pijplijnen, mits ruis wordt beheerd via decompositie- en parallelle uitvoeringsstrategieën.

De auteurs concluderen dat toekomstig werk zich moet richten op adaptieve decompositiestrategieën, foutmitigatietechnieken, en het integreren van HADOF in standaard genoomassemblagepijplijnen met echte sequentiële data.