dSABRE: A SABRE-Style Router for Multi-Core Distributed Quantum Computers

Het artikel introduceert dSABRE, een nieuwe router voor multi-core gedistribueerde quantumcomputers die het EPR-verbruik minimaliseert door prioriteit te geven aan het oplossen van intra-core poorten en het toepassen van een capaciteitsbewuste teleportatie-scoresmechanisme, waardoor aanzienlijke verminderingen in hulpbronverbruik worden bereikt in vergelijking met bestaande state-of-the-art methoden.

De kern

Stel je voor dat je een enorme, hoog-risico dansfeest wilt organiseren, maar de locatie is opgesplitst in verschillende aparte zalen (genaamd kernen). De dansers zijn qubits (quantumbits) en de muziek is een quantumschakeling (een set instructies).

Om het dansen te laten werken, moeten paren dansers soms hand in hand houden en samen draaien. Als ze in dezelfde zaal zitten, kunnen ze eenvoudig naar elkaar toe lopen. Maar als ze in verschillende zalen zitten, kunnen ze niet zomaar door de muren lopen. Ze moeten een speciale, dure en trage "teleportatie"-service gebruiken om van de ene zaal naar de andere te gaan. Deze service verbruikt een beperkte hulpbron genaamd een EPR-paar (denk hierbij aan een kostbaar "magisch ticket").

Het probleem is: Hoe verplaats je de dansers zodat ze samen kunnen dansen, terwijl je zo min mogelijk magische tickets gebruikt?

Dit is het probleem dat DSABRE oplost. Hieronder wordt uitgelegd hoe het artikel dit in eenvoudige termen beschrijft:

1. Het probleem met eerdere methoden

Vóór DSABRE reageerden andere routers (zoals TELESABRE) als verkeersagenten die alleen op problemen reageerden.

• Als een zaal te vol raakte met dansers, wachtten de oude routers tot er een file ontstond.
• Zodra het vastliep, probeerden ze een danser eruit te duwen, maar dit verbrandde vaak extra magische tickets of zorgde ervoor dat het hele feest stilviel (een "deadlock").
• Ze keken ook naar de dansinstructies in een rommelige, willekeurige volgorde, waardoor het moeilijk was te voorspellen wie er als volgende moest verplaatsen.

2. De DSABRE-oplossing: Een slimmer, proactief manager

DSABRE is een nieuwe "router" (een verkeersmanager) die een slimmere strategie gebruikt. Het heeft drie hoofdtrekkers om magische tickets te besparen:

A. De "vijfpunten-scorekaart" (Betere besluitvorming)

Wanneer DSABRE beslist of het een danser naar een nieuwe zaal moet verplaatsen, kijkt het niet alleen naar "hoe dichtbij" de partner is. Het gebruikt een vijf-termen scorekaart:

1. Stageringskosten: Hoeveel stappen moet de danser binnen zijn huidige zaal zetten om bij de deur te komen?
2. Capaciteitsstraf: Dit is de belangrijkste. Als een bestemmingszaal al volgepakt is met dansers, geeft DSABRE er een enorme "slechte score" aan. Het weigert dansers daarheen te sturen, waardoor de zaal geen file wordt.
3. Hop-winst: Het beloont verplaatsingen die de danser dichter bij zijn definitieve bestemmingszaal brengen, zelfs als ze er nog niet zijn.
4. Directe winst: Hoe dichterbij komt deze verplaatsing de danser bij zijn partner nu?
5. Vooruitkijken: Het kijkt een paar stappen de toekomst in om te zien of deze verplaatsing helpt bij aankomende dansen.

Analogie: Stel je voor dat je meubels verplaatst. Oude routers zouden gewoon een bank naar de volgende zaal duwen omdat het "dichtbij" was, zelfs als die zaal al vol zat met dozen. DSABRE controleert eerst of de zaal vol is en zegt: "Nee, die zaal is te druk; laten we de bank in de hal zetten in plaats daarvan."

B. De "proactieve evacuatie" (De file oplossen voordat hij ontstaat)

Dit is DSABRE's geheime wapen.

• Oude manier: Wachten tot een zaal 100% vol is, dan in paniek raken en proberen mensen eruit te verplaatsen.
• DSABRE-methode: Het houdt een "vraaglijst" bij. Als het ziet dat Zaal A op het punt staat te worden overstroomd met dansers voor een aankomende dans, maar Zaal A is al bijna vol, verplaatst het proactief sommige inactieve dansers (die op dat moment niet dansen) uit Zaal A voordat de drukte begint.
• Resultaat: Wanneer de drukte arriveert, is er ruimte. Geen files, geen verspillde magische tickets.

C. De "laag-voor-laag"-kaart (Betere planning)

Wanneer DSABRE vooruitkijkt om te zien welke dansen er komen, scant het de lijst niet willekeurig. Het bouwt een kaart laag voor laag, waarbij de volgorde van de dans wordt gerespecteerd.

• Analogie: Stel je voor dat je een recept leest. Een oude router zou misschien de ingrediënten voor het dessert lezen voordat die voor de soep. DSABRE leest het recept in de juiste volgorde, zodat het precies weet welke ingrediënten (dansers) als volgende nodig zijn, zodat het geen tijd verspilt aan het verplaatsen van dingen die nog niet nodig zijn.

3. De resultaten: Een veel efficiënter feest

De auteurs testten DSABRE op vele verschillende "feesten" (quantumschakelingen) van verschillende groottes (25, 36 en 64 dansers).

• Het resultaat: DSABRE gebruikte 41% tot 44% minder magische tickets (EPR-paren) dan de vorige beste methode (TELESABRE).
• Schaalbaarheid: Toen ze het testten op een enorm feest met tot wel 360 dansers, werkte DSABRE nog steeds perfect, terwijl de oude methode vaak vastliep en opgaf.

Samenvatting

Kortom, DSABRE is een slimmere manier om quantumcomputers te organiseren die bestaan uit vele kleine chips die met elkaar verbonden zijn. In plaats van te wachten tot files ontstaan, doet het het volgende:

1. Controleert de capaciteit voordat het dansers naar volle zalen stuurt.
2. Verplaatst inactieve dansers vroeg om ruimte te maken.
3. Plant de verplaatsingen in een logische, stap-voor-stap volgorde.

Dit bespaart de dure "magische tickets" (EPR-paren) die nodig zijn om de chips te verbinden, waardoor de quantumcomputer efficiënter draait.

Technische samenvatting

Technische Samenvatting: DSABRE – Een SABRE-stijl Router voor Multi-Core Gedistribueerde Quantumcomputers

Probleemstelling
Het pad naar fouttolerante quantumcomputing vereist schaling buiten enkele monolithische chips naar Gedistribueerde Quantumcomputers (DQCs), waarbij meerdere kleine Quantum Processing Units (QPUs of "kernen") via fotonische of microgolfverbindingen met elkaar zijn verbonden. Het uitvoeren van circuits op DQCs omvat een compilatiepijplijn bestaande uit qubittoewijzing, selectie van communicatieprimitieven en routing/planning. Het dominante doel in deze context is het minimaliseren van EPR-verbruik (verstrengelde paren), aangezien EPR-generatie traag, ruisgevoelig en snelheidsbeperkt is in vergelijking met lokale poorthandelingen.

Hoewel state-of-the-art routers zoals TELESABRE SABRE-stijl heuristieken gebruiken om circuits over kernen te routeren, behandelen ze congestie defensief. TELESABRE ontmoedigt het landen in verzadigde kernen via straffen en probeert zich te herstellen van deadlocks door lookahead-informatie te laten vallen. Echter, op dichte of grote instanties, verbrandt deze reactieve aanpak vaak excessieve EPR-paren of faalt hij volledig om te convergeren. De kernuitdaging die door dit artikel wordt aangepakt, is het gebrek aan proactief congestiemanagement en de inefficiëntie van bestaande lookahead-mechanismen in inter-kernomgevingen.

Methodologie: DSABRE
DSABRE is een SABRE-stijl router ontworpen voor multi-core processors. Het werkt binnen een vaste initiële lay-out (gegenereerd door Qiskit SabreLayout) en richt zich op de routingfase: het ordenen van intra-kern SWAPs en inter-kern teleportaties (specifiek teledata, het verplaatsen van logische qubits tussen kernen). Het algoritme voert een door lookahead gedreven lus uit met vier fasen per iteratie:

1. Drain: Voer 1Q-poorten en aangrenzende intra-kern 2Q-poorten uit.
2. Partition: Scheid de resterende poorten van de voorste laag in intra-kern ($F_{intra}$) en inter-kern ($F_{inter}$).
3. Score & Apply:
   • Als $F_{intra}$ niet-leeg is, selecteer de beste intra-kern SWAP.
   • Als $F_{intra}$ leeg is, scoor inter-kern teleportatiekandidaten en proactieve congestieverlichtingskandidaten, en pas de beweging met de laagste score toe.
4. Checkpoint/Rollback: Sla de staat op bij vooruitgang; als het voor een vastgesteld aantal iteraties vastloopt, herstel een checkpoint en forceer vooruitgang om de deadlock te ontsnappen.

Belangrijkste Bijdragen en Mechanismen
Het artikel identificeert drie specifieke mechanismen die de verbetering van DSABRE ten opzichte van de state of the art drijven:

1. Vijf-termen Poortgerichte Teleportatiescore:
   In tegenstelling tot TELESABRE's globale energie-schatting, gebruikt DSABRE een lokale, poortgerichte score ($s$) voor inter-kern bewegingen. De score combineert vijf termen:

   • Staging Cost ($d_{prep}$): Intra-kern SWAPs vereist om een qubit naar een communicatiepoort te verplaatsen.
   • Capaciteitsstraf ($c_{cap}$): Een term die teleportatie naar kernen met lage vrije capaciteit expliciet straft, waardoor de router wordt voorkomen dat hij verzadigde kernen overstroomt.
   • Hop Gain ($g_{hop}$): Een directionele beloning voor bewegingen die de inter-kern afstand tot het doel verminderen, wat compenseert wanneer de landingspoort ver van de optimale stagingpositie ligt.
   • Front-Layer Gain ($\Delta_F$): Directe vermindering van de fysieke afstand voor de huidige poort.
   • Lookahead ($\tilde{\Delta}_E$): Een vervalkrachtig gewogen som van toekomstige afstandsreducties.

2. Proactieve Congestieverlichting:
   DSABRE onderhoudt een expliciete vraagvector over kernen. Voordat een kern verzadigd raakt (hoge vraag, lage capaciteit), genereert de router proactief "verlichtingskandidaten" om inactieve qubits weg te teleporteren van kernen met hoge vraag. Deze bewegingen worden gescoord binnen dezelfde doelfunctie (met $\Delta_F=0$) en concurreren direct met poortgedreven bewegingen. Dit voorkomt de "evictie-cascade" die leidt tot deadlock in reactieve systemen.

3. BFS-Laag Inter-Kern Uitgebreide Set:
   Standaard SABRE bouwt lookahead-sets in topologische volgorde op, wat ongerelateerde draden kan mengen. TELESABRE gebruikt BFS-lagen maar weegt poorten willekeurig. DSABRE construeert de inter-kern lookahead-set laag voor laag met behulp van Breadth-First Search (BFS) op de DAG. Cruciaal worden binnen elke laag poorten die een draad delen met de voorste laag eerst uitgegeven. De lookahead-verval wordt toegepast op basis van de BFS-diepte ($\gamma^{dep(g)}$), waardoor wordt gegarandeerd dat op korte termijn opvolgers het signaal domineren en dat de set de DAG-afhankelijkheden strikter respecteert dan topologische ordening.

Experimentele Resultaten
De auteurs evalueerden DSABRE tegen TELESABRE en pytket-dqc (een op poortteleportatie gebaseerde router) over 18 MQT-Bench circuits bij 25, 36 en 64 logische qubits, met behulp van grid-of-grids-architecturen (B-grid en H-grid).

• EPR-reductie: DSABRE verlaagt het geometrisch gemiddelde EPR-verbruik met 41–44% ten opzichte van TELESABRE en met 16–68% ten opzichte van pytket-dqc.
• Schalbaarheid: Op een 64-qubit Random circuit faalde TELESABRE om te convergeren op alle zaden, terwijl DSABRE de routing voltooide. Een schaalbaarheidssweep op Quantum Fourier Transform (QFT)-circuits tot 360 qubits bevestigde dat DSABRE zijn voordeel behoudt naarmate de circuitgrootte en architectuur schalen.
• Ablatiestudies:
  • Het verwijderen van de capaciteitsstraf verhoogde het geometrisch gemiddelde EPR met ~59% (25q) en ~59% (64q), wat het identificeert als het meest kritieke component.
  • Het uitschakelen van proactieve congestieverlichting verhoogde EPR met 23,4% op de 64q-suite, waarbij dichte circuits (AE, QFT) een toename van meer dan 100% zagen.
  • Het vervangen van de BFS-laag uitgebreide set door topologische ordening verhoogde EPR met 3–11%, waarbij de winsten groeiden voor grotere circuits.
• Kostengevoeligheid: Naarmate de relatieve kosten van teleportatie ($c_{tele}$) toenemen (simulatie van fotonische-link hardware), verbreedt de prestatiekloof tussen DSABRE en TELESABRE zich, waarbij DSABRE tot ~39% meer EPR's bespaart bij hoge kostenverhoudingen.

Betekenis en Claims
Het artikel beweert dat gedistribueerde routing minder profiteert van complexe per-kandidaat scoreformules en meer van het waarborgen dat lookahead-signalen en architecturale capaciteitsbeperkingen dezelfde scorestap ingaan. Door proactieve congestieverlichting en een capaciteitsbewuste score te integreren, vermijdt DSABRE de deadlocks en excessieve EPR-consumptie die defensieve, reactieve routers teisteren.

De auteurs positioneren DSABRE als complementair aan statische toewijzingsmethoden (zoals hypergraafpartitionering) en tijdbewuste planners. Zij merken op dat hoewel DSABRE momenteel alleen teledata (state teleportatie) gebruikt, het is ontworpen als een robuuste routingengine die in toekomstig werk kan worden gecombineerd met andere primitieven of burst-executiepasses. De resultaten suggereren dat expliciet capaciteitsmanagement een noodzakelijk component is voor het schalen van gedistribueerde quantumcompilatie.