PureMagic: A Dynamic Scheduler for Lattice Surgery

PureMagic is een dynamische planner voor roosterschirurgie die toegewijde buspatches elimineert door alle ancillapatches te hergebruiken voor zowel routing als stochastische cultivatie van magische toestanden, waardoor aanzienlijke verbeteringen worden bereikt in efficiëntie, hulpbronbenutting en voorbereidingstijd in vergelijking met traditionele statische benaderingen.

De kern

Stel je voor dat je een enorme, ongelooflijk complexe fabriek probeert te runnen. Deze fabriek maakt geen auto's of telefoons; hij maakt quantumcomputers die problemen kunnen oplossen die voor de machines van vandaag onmogelijk zijn. Maar er is een addertje onder het gras: de fabriek is ongelooflijk fragiel. Als één enkele arbeider niest, kan de hele productielijn crashen. Om dit op te lossen, gebruikt de fabriek een "veiligheidsnet"-systeem genaamd foutcorrectie, waarbij veel arbeiders hetzelfde werk doen om nauwkeurigheid te garanderen.

Voor het meest geavanceerde werk heeft de fabriek echter een speciaal, zeldzaam ingrediënt nodig dat een "magische toestand" wordt genoemd. Het maken van dit ingrediënt is lastig.

De Oude Manier: De Toegewijde "Magische Fabriek"

In de traditionele aanpak (gebruikt door eerdere systemen) bouwde de fabriek enorme, permanente gebouwen die uitsluitend waren gewijd aan het maken van deze magische toestanden.

• Het Probleem: Deze gebouwen namen een enorme hoeveelheid ruimte in beslag (logische qubits). Ze waren als gigantische magazijnen die aan de rand van de fabrieksvloer stonden.
• De Bottleneck: Omdat ze op hun plaats waren vastgezet, konden ze niet verplaatsen. Als de hoofdproductielijn een arbeider nodig had om een doos van de ene kant van de fabriek naar de andere te dragen, konden de arbeiders in de magische fabrieken niet helpen; ze zaten vast aan het maken van magie.
• De Wager: Het maken van de magische toestand is als het rollen van een dobbelsteen. Soms duurt het een paar seconden; soms, door pech, duurt het uren. Het oude systeem moest wachten tot de "trage worpen" klaar waren voordat het verder kon, waardoor de hele fabriek stil kwam te liggen.

De Nieuwe Manier: PureMagic (De "Zwitsers Mes"-Arbeiders)

Het paper introduceert PureMagic, een nieuwe manier om de fabriek te runnen die de regels volledig verandert.

1. Geen Toegewijde Fabrieken Meer
In plaats van speciale gebouwen te bouwen voor magische toestanden, zegt PureMagic: "Iedereen is een magiemaker."
Elke enkele arbeider in de fabriek (een "ancilla-patch" genoemd) is getraind om magische toestanden te maken. Ze proberen constant het magische ingrediënt te brouwen.

2. De Dynamische Schakel
Hier is het slimme deel: deze arbeiders zijn ook de bezorgers.

• Scenario A: Een arbeider is druk bezig met het brouwen van magie.
• Scenario B: Plotseling heeft de hoofdproductielijn die arbeider nodig om een doos over de fabriek te dragen (routing).
• De Magische Move: De arbeider stopt direct met brouwen, laat het halfgemaakte magie vallen en draagt de doos. Zodra de doos is bezorgd, beginnen ze direct weer vanaf nul met het brouwen van magie.

Waarom is dit beter?

• De "Lange Staart" Snijden: In het oude systeem, als een poging om magie te maken vastliep in een "pech"-lus (oneindig lang duurde), wachtte de hele fabriek. Bij PureMagic, als een arbeider vastloopt tijdens het brouwen, wordt hij onderbroken door een bezorgklus. Dit snijdt op natuurlijke wijze de "lange staart" van trage pogingen af. De fabriek houdt alleen de "snelle" magiemakers over, waardoor de gemiddelde tijd om magie te krijgen veel korter wordt (4,5 keer sneller, volgens het paper).
• Geen Stilstaande Tijd: In het oude systeem zaten de bezorgers stil terwijl de magische fabrieken werkten, en vice versa. Bij PureMagic doet elke arbeider altijd iets – ofwel magie maken ofwel dingen verplaatsen. Er is geen verspilde ruimte.

3. De "Gewichtslimiet"-Truc
Het paper noemt ook een softwaretruc genaamd een "gewichtslimiet" (aangeduid als $\omega$). Denk hierbij aan een regel voor hoeveel dozen een arbeider tegelijk kan dragen.

• De oude manier probeerde enorme ladingen (complexe instructies) te dragen om stappen te besparen, maar bleef hier vaak in vastzitten.
• PureMagic gebruikt een regel om instructies op te breken in tiny, enkel-dozes-ladingen. Dit betekent dat de fabriek veel arbeiders tegelijk parallel kan laten werken. Omdat PureMagic zoveel arbeiders beschikbaar heeft (aangezien ze niet vastzitten in magische fabrieken), kan het deze parallelisme veel beter benutten dan het oude systeem.

De Resultaten

De onderzoekers testten dit nieuwe systeem op 29 verschillende "fabrieksontwerpen" (benchmark-circuits). Dit is wat ze vonden:

• Efficiëntie: PureMagic was 40% tot 150% efficiënter dan het oude bus-routing-systeem.
• Ruimte: Het gebruikte 19% tot 80% minder arbeiders (logische qubits) om hetzelfde werk te doen.
• Snelheid: Het verminderde de tijd die nodig was om het magische ingrediënt voor te bereiden met 4,5 keer.
• Vergelijking: In vergelijking met de beste bestaande statische planner (DASCOT), was PureMagic tot 15 keer efficiënter wanneer je de kosten van het maken van de magische toestanden meetelt.

De Conclusie

PureMagic behandelt de fabrieksvloer als een vloeibare, dynamische omgeving in plaats van een stijve roost met vaste rollen. Door elke arbeider direct te laten schakelen tussen "magie maken" en "pakketten bezorgen", elimineert het verspilde ruimte, snijdt het de langzaamste pogingen weg en houdt het de quantumcomputer op pieksnelheid. Het paper beweert dat deze aanpak zo dicht bij de theoretische limiet van perfectie komt dat het bijna onmogelijk is om veel beter te doen zonder de fundamentele fysica van de machine te veranderen.

Technische samenvatting

Technische Samenvatting: PureMagic

Probleemstelling

Fouttolerante kwantumberekening met oppervlakcodes is afhankelijk van magische toestanden om universaliteit te bereiken. Traditionele benaderingen maken gebruik van distillatiefabrieken, grote, statische arrays van logische qubits (121–176 patches per uitvoerpoort) die magische toestanden deterministisch produceren. Dit vereist een statische, perifere plaatsing van middelen, wat een rigide architectuur creëert waarbij "bus"-patches uitsluitend zijn toegewijd aan routing en "magische" patches uitsluitend aan productie.

Een alternatief, kweek van magische toestanden, verkleint de voetafdruk tot een enkele logische qubit, maar introduceert inherente stochasticiteit. De tijd die nodig is om een magische toestand met hoge fideliteit te produceren, volgt een exponentiële verdeling met een "lange staart", wat betekent dat sommige pogingen aanzienlijk langer duren dan het gemiddelde. Statische planners, die uitgaan van deterministische beschikbaarheid van middelen, kunnen zich niet aanpassen aan deze variabiliteit, wat leidt tot stilstanden en inefficiënties. Bovendien dwingt de lange staart van kweektijden statische planners om middelen te overprovisioneren of aanzienlijke vertragingen te accepteren.

Methodologie

De auteurs stellen PureMagic voor, een dynamisch planningskader dat de rol van ancilla-patches in roosterchirurgie fundamenteel heroverweegt.

1. Dual-purpose ancilla-architectuur

PureMagic elimineert het onderscheid tussen toegewijde bus-patches en kwekers van magische toestanden. In plaats daarvan worden alle ancilla-patches behandeld als middelen met een dubbel doel:

• Kweek: Elke niet-data-patch probeert continu een magische toestand te kweken.
• Routing: Wanneer een routingpad nodig is voor een Pauli-product, kan elke patch (inclusief die welke momenteel aan het kweken zijn) onmiddellijk worden herbestemd.
• Onderbreking en herstart: Als een patch nodig is voor routing, wordt de lopende kweek geannuleerd. Zodra de routingtaak voltooid is, wordt de kweek op die patch vanaf nul hervat. Dit mechanisme verkort op natuurlijke wijze de lange staart van de verdeling van kweektijden, omdat langzaam groeiende toestanden worden onderbroken door routingeisen, waardoor alleen de snelste succesvolle pogingen bijdragen aan het schema.

2. Dynamisch planningsalgoritme

De planner opereert binnen het kader van Pauli-gebaseerde berekening (PBC), waarbij Clifford+T-circuits worden getranspileerd naar sequenties van metingen van multi-qubit Pauli-producten.

• Real-time aanpassing: De planner neemt beslissingen binnen één logische cyclus (ongeveer 17 µs voor code-afstand $d=17$). Het behandelt twee bronnen van non-determinisme: stochastische voltooiingstijden voor kweek en de 50% kans op mislukking van T-state-injectie (waarvoor een S-gate-correctie nodig is).
• Heuristische packing: Om het NP-moeilijke Lattice Surgery Scheduling Problem (LSSP) op te lossen, maakt PureMagic gebruik van een greedige Steiner-bos-packing-algoritme. Het prioriteert Pauli-producten op basis van de geschatte boomgrootte (met behulp van Manhattan-afstand) om de meest compacte bewerkingen eerst te plannen.
• Padvinding: Voor single-operator Pauli-producten wordt een efficiënt A*-algoritme gebruikt om paden naar beschikbare magische toestanden te vinden. Voor multi-qubit-producten benadert een kortste-pad-heuristiek de Steiner-boom.

3. Transpilation met gewichtslimiet ($\omega$)

De auteurs introduceren een transpilation-extensie met het Tableau-algoritme en een gewichtslimiet $\omega$.

• $\omega = 1$ (Lightweight-PBC): Beperkt Pauli-producten tot single operators. Dit verhoogt het totale poortenaantal lichtjes (2–6%), maar vermindert de circuitsdiepte drastisch (tot 26×) door parallelisme te maximaliseren.
• $\omega = \infty$ (Heavyweight-PBC): De standaardbenadering waarbij alle Clifford-poorten worden doorgeschoven, wat resulteert in minder poorten maar hogere-gewicht Pauli-producten en minder parallelisme.
  PureMagic is specifiek ontworpen om het hoge parallelisme van de $\omega = 1$-instelling te benutten, aangezien het toegenomen aantal beschikbare kweek-patches meer gelijktijdige routingverzoeken kan bedienen.

Belangrijkste bijdragen

1. PureMagic-architectuur: Een lay-outontwerp dat toegewijde bus-patches elimineert, waardoor elke ancilla-patch interwisselbaar kan dienen als kweker en als routing-middel.
2. Dynamische planner: Een real-time planner die zich aanpast aan stochastische kweektijden en mislukkingen van T-state-injectie, met gebruikmaking van een greedige Steiner-bos-packing-aanpak.
3. Simulatiekader: Een simulator op het niveau van logische qubits die probabilistische kweek- en injectiefouten modelleert om de prestaties van het planningsproces te evalueren.
4. Gewicht-beperkte transpilation: Een extensie van het Tableau-algoritme dat het aantal poorten inruilt voor circuitsparallelisme, waardoor de werklast wordt geoptimaliseerd voor de PureMagic-architectuur.

Experimentele resultaten

Het kader werd geëvalueerd op 29 benchmarkcircuits uit de Benchpress-suite, waarbij de uitvoering werd gesimuleerd op een abstract oppervlakcodemodel ($d=17$).

• Efficiëntiewinst: In vergelijking met een traditionele bus-routinglay-out bereikt PureMagic een verbetering in efficiëntie van 40% tot 150% (inverse van de ruimtetijd-volume). De winst is het meest uitgesproken bij gebruik van de lightweight-transpilation-instelling ($\omega = 1$).
• Middelenreductie: PureMagic gebruikt 19% tot 80% minder logische qubits dan bus-routinglay-outs, omdat het geen vaste omtrek van toegewijde fabrieken voor magische toestanden vereist.
• Kweektijd: De gemiddelde voorbereidingstijd voor magische toestanden wordt met 4,5× gereduceerd (van gemiddeld 26 cycli naar 5,8 cycli) als gevolg van de verkorting van de lange staart van de kweekverdeling.
• Vergelijking met statische planners: In vergelijking met DASCOT (een state-of-the-art statische planner die uitgaat van onmiddellijke beschikbaarheid van magische toestanden) is PureMagic tot 15× efficiënter wanneer de kosten van voorbereiding van magische toestanden (kweektijd of oppervlak van distillatiefabriek) worden meegerekend.
• Theoretische grenzen: De geplande volumes van PureMagic liggen tussen de conservatieve en optimistische theoretische ondergrenzen van FLASQ, wat aantoont dat de dynamische dual-purpose-strategie de ideale "vloeibare" ancilla-middelen nauw benadert.

Betekenis en claims

Het artikel betoogt dat de scheiding tussen routing en productie van magische toestanden een artefact is van de hoge overhead van distillatiefabrieken. Door kweek en dynamische planning te adopteren, wordt het ideaal van "vloeibare ancilla's" haalbaar—waarbij elke beschikbare bron elke functie kan vervullen.

De auteurs beweren dat PureMagic aantoont dat dynamische planning essentieel is voor efficiënte fouttolerante kwantumberekening, met name bij het gebruik van middenefficiënte methoden zoals kweek. Zij suggereren dat toekomstige vergelijkingen van Quantum Error Correction Codes (QECC's) verder moeten gaan dan statische poort-niveau-metrics en de overhead van dynamische planning en middelenbeheer moeten omvatten. Het werk impliceert dat naarmate algoritmes hogere-fideliteit magische toestanden vereisen (wat langere kwerktijden met zich meebrengt), de voordelen van PureMagic' vermogen om kweek te amortiseren over een groot aantal patches nog significantere worden.