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

Das Papier stellt dSABRE vor, einen neuartigen Router für multi-Core-verteilte Quantencomputer, der den EPR-Verbrauch minimiert, indem er die Auflösung von Gattern innerhalb eines Kerns priorisiert und einen kapazitätsbewussten Teleportations-Bewertungsmechanismus einsetzt, wodurch im Vergleich zu bestehenden State-of-the-Art-Methoden signifikante Reduktionen des Ressourcenverbrauchs erzielt werden.

Das Wesentliche

Stellen Sie sich vor, Sie versuchen, eine riesige, hochriskante Tanzparty zu organisieren, doch der Veranstaltungsort ist in mehrere separate Räume unterteilt (die sogenannten Kerne). Die Tänzer sind Qubits (Quantenbits), und die Musik ist ein Quantenschaltkreis (eine Reihe von Anweisungen).

Damit der Tanz funktioniert, müssen Paare von Tänzern manchmal Händchen halten und gemeinsam drehen. Wenn sie sich im selben Raum befinden, können sie einfach leicht zueinander hinübergehen. Befinden sie sich jedoch in verschiedenen Räumen, können sie nicht einfach durch die Wände gehen. Sie müssen einen speziellen, teuren und langsamen „Teleportations"-Service nutzen, um von einem Raum in einen anderen zu gelangen. Dieser Service verbraucht eine begrenzte Ressource, die als EPR-Paar bezeichnet wird (denken Sie daran als an ein kostbares „magisches Ticket").

Das Problem lautet: Wie bewegen Sie die Tänzer so, dass sie zusammen tanzen können, wobei Sie die geringstmögliche Anzahl an magischen Tickets verwenden?

Dies ist das Problem, das DSABRE löst. Hier erklärt das Papier es in einfachen Worten:

1. Das Problem mit früheren Methoden

Vor DSABRE waren andere Router (wie TELESABRE) wie Verkehrspolizisten, die nur auf Probleme reagierten.

• Wenn ein Raum mit Tänzern zu voll wurde, warteten die alten Router, bis ein Stau entstand.
• Sobald es gestaut war, versuchten sie, einen Tänzer herauszudrängen, was jedoch oft zusätzliche magische Tickets verbrauchte oder die gesamte Party zum Stillstand brachte (ein „Deadlock").
• Sie betrachteten die Tanzanweisungen auch in einer chaotischen, zufälligen Reihenfolge, was es schwierig machte, vorherzusagen, wer als Nächstes bewegt werden musste.

2. Die DSABRE-Lösung: Ein intelligenterer, proaktiver Manager

DSABRE ist ein neuer „Router" (ein Verkehrsmanager), der eine intelligentere Strategie verwendet. Er verfügt über drei Haupttricks, um magische Tickets zu sparen:

A. Die „Fünf-Punkte-Bewertungskarte" (Bessere Entscheidungsfindung)

Wenn DSABRE entscheidet, ob ein Tänzer in einen neuen Raum bewegt werden soll, betrachtet es nicht nur, „wie nah" der Partner ist. Es verwendet eine fünfteilige Bewertungskarte:

1. Staging-Kosten: Wie viele Schritte muss der Tänzer innerhalb seines aktuellen Raums unternehmen, um zur Tür zu gelangen?
2. Kapazitätsstrafe: Dies ist der große Punkt. Wenn ein Zielraum bereits mit Tänzern vollgepackt ist, verleiht DSABRE ihm eine enorme „schlechte Bewertung". Es weigert sich, Tänzer dorthin zu senden, und verhindert so, dass der Raum zu einem Stau wird.
3. Hop-Gewinn: Es belohnt Bewegungen, die den Tänzer näher an seinen endgültigen Zielraum bringen, auch wenn er noch nicht dort ist.
4. Sofortiger Gewinn: Wie viel näher bringt diese Bewegung den Tänzer jetzt gerade zu seinem Partner?
5. Vorausschau: Es schaut ein paar Schritte in die Zukunft voraus, um zu sehen, ob diese Bewegung bei bevorstehenden Tänzen hilft.

Analogie: Stellen Sie sich vor, Sie bewegen Möbel. Alte Router würden einfach ein Sofa in den nächsten Raum schieben, nur weil es „nah" war, selbst wenn dieser Raum bereits voller Kartons war. DSABRE prüft zuerst, ob der Raum voll ist, und sagt: „Nein, dieser Raum ist zu überfüllt; lassen Sie uns das Sofa stattdessen in den Flur stellen."

B. Die „Proaktive Räumung" (Stau klären, bevor er entsteht)

Dies ist die Geheimwaffe von DSABRE.

• Alte Methode: Warten, bis ein Raum zu 100 % voll ist, dann in Panik versuchen, Leute herauszubewegen.
• DSABRE-Methode: Es führt eine „Nachfrageliste". Wenn es erkennt, dass Raum A für einen bevorstehenden Tanz mit Tänzern überflutet werden wird, Raum A aber bereits fast voll ist, proaktiv einige inaktive Tänzer (die gerade nicht tanzen) aus Raum A heraus, bevor der Ansturm beginnt.
• Ergebnis: Wenn der Ansturm kommt, ist Platz vorhanden. Keine Staus, keine verschwendeten magischen Tickets.

C. Die „Schicht-für-Schicht"-Karte (Bessere Planung)

Wenn DSABRE vorausschauend betrachtet, welche Tänze als Nächstes kommen, scannt es die Liste nicht einfach zufällig. Es baut eine Karte Schicht für Schicht auf und respektiert dabei die Reihenfolge des Tanzes.

• Analogie: Stellen Sie sich vor, Sie lesen ein Rezept. Ein alter Router könnte die Zutaten für das Dessert vor der Suppe lesen. DSABRE liest das Rezept in der korrekten Reihenfolge, stellt sicher, dass es genau weiß, welche Zutaten (Tänzer) als Nächstes benötigt werden, und verschwendet keine Zeit damit, Dinge zu bewegen, die noch nicht benötigt werden.

3. Die Ergebnisse: Eine viel effizientere Party

Die Autoren testeten DSABRE an vielen verschiedenen „Partys" (Quantenschaltkreisen) unterschiedlicher Größen (25, 36 und 64 Tänzer).

• Das Ergebnis: DSABRE verwendete 41 % bis 44 % weniger magische Tickets (EPR-Paare) als die bisher beste Methode (TELESABRE).
• Skalierbarkeit: Als sie es an einer riesigen Party mit bis zu 360 Tänzern testeten, funktionierte DSABRE immer noch perfekt, während die alte Methode oft stecken blieb und aufgab.

Zusammenfassung

Kurz gesagt ist DSABRE eine intelligentere Art, Quantencomputer zu organisieren, die aus vielen miteinander verbundenen kleinen Chips bestehen. Anstatt darauf zu warten, dass Staus entstehen,

1. prüft es die Kapazität, bevor es Tänzer in überfüllte Räume schickt,
2. bewegt inaktive Tänzer frühzeitig heraus, um Platz zu schaffen, und
3. plant die Bewegungen in einer logischen, schrittweisen Reihenfolge.

Dies spart die teuren „magischen Tickets" (EPR-Paare), die benötigt werden, um die Chips zu verbinden, und lässt den Quantencomputer effizienter laufen.

Technische Zusammenfassung

Technische Zusammenfassung: DSABRE – Ein SABRE-artiger Router für Multi-Core-verteilte Quantencomputer

Problemstellung
Der Weg zum fehlertoleranten Quantencomputing erfordert eine Skalierung über einzelne monolithische Chips hinaus hin zu verteilten Quantencomputern (DQCs), bei denen mehrere kleine Quantenprozessoren (QPUs oder „Kerne") über photonische oder Mikrowellenverbindungen miteinander verbunden sind. Die Ausführung von Schaltkreisen auf DQCs umfasst einen Kompilierungspipeline, bestehend aus Qubit-Allokation, Auswahl von Kommunikationsprimitive und Routing/Scheduling. Das dominierende Ziel in diesem Kontext ist die Minimierung des EPR-Verbrauchs (verschränkte Paare), da die EPR-Generierung im Vergleich zu lokalen Gatteroperationen langsam, verrauscht und ratenbegrenzt ist.

Während fortschrittlichste Router wie TELESABRE SABRE-artige Heuristiken nutzen, um Schaltkreise über Kerne hinweg zu routen, behandeln sie Überlastung defensiv. TELESABRE versucht, das Landen in überlasteten Kernen durch Strafen zu verhindern und versucht, aus Deadlocks zu entkommen, indem es Lookahead-Informationen verwirft. Auf dichten oder großen Instanzen führt dieser reaktive Ansatz jedoch häufig zum Verbrennen übermäßiger EPR-Paare oder zum vollständigen Scheitern der Konvergenz. Die Kernherausforderung, die in diesem Papier adressiert wird, ist das Fehlen eines proaktiven Überlastungsmanagements und die Ineffizienz bestehender Lookahead-Mechanismen in inter-kernigen Umgebungen.

Methodik: DSABRE
DSABRE ist ein SABRE-artiger Router, der für Multi-Core-Prozessoren entwickelt wurde. Er arbeitet innerhalb eines festen initialen Layouts (generiert durch Qiskit SabreLayout) und konzentriert sich auf die Routing-Phase: die Ordnung von intra-kernigen SWAPs und inter-kernigen Teleportationen (speziell teledata, das Verschieben logischer Qubits zwischen Kernen). Der Algorithmus führt eine durch Lookahead gesteuerte Schleife mit vier Phasen pro Iteration aus:

1. Drain: Ausführung von 1Q-Gattern und benachbarten intra-kernigen 2Q-Gattern.
2. Partitionierung: Trennung der verbleibenden Gatter der Front-Schicht in intra-kernige ($F_{intra}$) und inter-kernige ($F_{inter}$) Gatter.
3. Bewertung & Anwendung:
   • Wenn $F_{intra}$ nicht leer ist, wird das beste intra-kernige SWAP ausgewählt.
   • Wenn $F_{intra}$ leer ist, werden Kandidaten für inter-kernige Teleportation und Kandidaten für proaktive Überlastungslinderung bewertet, und der Zug mit dem niedrigsten Score wird ausgeführt.
4. Checkpoint/Rollback: Speichern des Zustands bei Fortschritt; falls für eine festgelegte Anzahl von Iterationen kein Fortschritt erzielt wird, wird ein Checkpoint wiederhergestellt und ein erzwungener Fortschritt initiiert, um den Deadlock zu verlassen.

Hauptbeiträge und Mechanismen
Das Papier identifiziert drei spezifische Mechanismen, die die Verbesserung von DSABRE gegenüber dem Stand der Technik vorantreiben:

1. Fünf-Term-Gatter-zentrierter Teleportations-Score:
   Im Gegensatz zur globalen Energieabschätzung von TELESABRE verwendet DSABRE einen lokalen, gatterzentrierten Score ($s$) für inter-kernige Bewegungen. Der Score kombiniert fünf Terme:

   • Staging-Kosten ($d_{prep}$): Intra-kernige SWAPs, die erforderlich sind, um ein Qubit zu einem Kommunikationsport zu bewegen.
   • Kapazitätsstrafe ($c_{cap}$): Ein Term, der das Teleportieren in Kerne mit geringer freier Kapazität explizit bestraft und verhindert, dass der Router überlastete Kerne flutet.
   • Hop-Gewinn ($g_{hop}$): Eine gerichtete Belohnung für Bewegungen, die die inter-kernige Distanz zum Ziel verringern, was kompensiert, wenn der Landeport weit von der optimalen Staging-Position entfernt ist.
   • Front-Schicht-Gewinn ($\Delta_F$): Unmittelbare Verringerung der physischen Distanz für das aktuelle Gatter.
   • Lookahead ($\tilde{\Delta}_E$): Ein abklingend gewichteter Summe zukünftiger Distanzreduktionen.

2. Proaktive Überlastungslinderung:
   DSABRE unterhält einen expliziten Nachfragevektor über die Kerne hinweg. Bevor ein Kern überlastet wird (hohe Nachfrage, geringe Kapazität), generiert der Router proaktiv „Linderung-Kandidaten", um inaktive Qubits von Kernen mit hoher Nachfrage wegzuteleportieren. Diese Bewegungen werden innerhalb derselben Zielfunktion bewertet (mit $\Delta_F=0$) und konkurrieren direkt mit gattergetriebenen Bewegungen. Dies verhindert die „Evictions-Kaskade", die in reaktiven Systemen zu Deadlocks führt.

3. BFS-Schicht-Inter-Kern-Erweiterter Satz:
   Standard-SABRE baut Lookahead-Sets in topologischer Reihenfolge auf, was nicht verwandte Drähte vermischen kann. TELESABRE verwendet BFS-Schichten, gewichtet Gatter jedoch willkürlich. DSABRE konstruiert den inter-kernigen Lookahead-Satz schichtweise unter Verwendung einer Breitensuche (BFS) auf dem DAG. Entscheidend ist, dass innerhalb jeder Schicht Gatter, die einen Draht mit der Front teilen, zuerst ausgegeben werden. Der Lookahead-Abklingfaktor wird basierend auf der BFS-Tiefe angewendet ($\gamma^{dep(g)}$), wodurch sichergestellt wird, dass kurzfristige Nachfolger das Signal dominieren und dass der Satz die DAG-Abhängigkeiten strenger respektiert als die topologische Ordnung.

Experimentelle Ergebnisse
Die Autoren bewerteten DSABRE gegen TELESABRE und pytket-dqc (ein router auf Gatter-Teleportations-Basis) über 18 MQT-Bench-Schaltkreise bei 25, 36 und 64 logischen Qubits unter Verwendung von Grid-of-Grids-Architekturen (B-Grid und H-Grid).

• EPR-Reduktion: DSABRE reduziert den geometrischen Mittelwert des EPR-Verbrauchs um 41–44 % im Vergleich zu TELESABRE und um 16–68 % im Vergleich zu pytket-dqc.
• Skalierbarkeit: Bei einem 64-Qubit-Zufallsschaltkreis scheiterte TELESABRE bei allen Seeds an der Konvergenz, während DSABRE das Routing abschloss. Ein Skalierbarkeitssweep bei Quanten-Fourier-Transformations-(QFT)-Schaltkreisen bis zu 360 Qubits bestätigte, dass DSABRE seinen Vorteil beibehält, wenn sich die Schaltkreisgröße und die Architektur skalieren.
• Ablationsstudien:
  • Das Entfernen der Kapazitätsstrafe erhöhte den geometrischen Mittelwert des EPR um ~59 % (25q) und ~59 % (64q), was sie als kritischste Komponente identifiziert.
  • Das Deaktivieren der proaktiven Überlastungslinderung erhöhte den EPR um 23,4 % im 64q-Suite, wobei dichte Schaltkreise (AE, QFT) eine Steigerung von über 100 % verzeichneten.
  • Das Ersetzen des BFS-Schicht-erweiterten Satzes durch topologische Ordnung erhöhte den EPR um 3–11 %, wobei die Gewinne bei größeren Schaltkreisen zunahmen.
• Kostensensitivität: Wenn die relative Kosten der Teleportation ($c_{tele}$) steigen (Simulation von Hardware mit photonischen Verbindungen), vergrößert sich die Leistungslücke zwischen DSABRE und TELESABRE, wobei DSABRE bei hohen Kostenverhältnissen bis zu ~39 % mehr EPRs einspart.

Bedeutung und Behauptungen
Das Papier behauptet, dass verteiltes Routing weniger von komplexen pro-Kandidaten-Bewertungsformeln profitiert und mehr davon, dass Lookahead-Signale und architektonische Kapazitätsbeschränkungen in denselben Bewertungsschritt eingehen. Durch die Integration proaktiver Überlastungslinderung und eines kapazitätsbewussten Scores vermeidet DSABRE die Deadlocks und den übermäßigen EPR-Verbrauch, die defensive, reaktive Router plagen.

Die Autoren positionieren DSABRE als komplementär zu statischen Allokationsmethoden (wie Hypergraph-Partitionierung) und zeitbewussten Schedulern. Sie stellen fest, dass DSABRE derzeit nur teledata (Zustandsteleportation) verwendet, aber als robuste Routing-Engine konzipiert ist, die in zukünftiger Arbeit mit anderen Primitive oder Burst-Ausführungspässen kombiniert werden kann. Die Ergebnisse deuten darauf hin, dass explizites Kapazitätsmanagement eine notwendige Komponente für die Skalierung verteilter Quantenkompilierung ist.