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

The paper introduces dSABRE, a novel router for multi-core distributed quantum computers that minimizes EPR consumption by prioritizing intra-core gate resolution and employing a capacity-aware teleportation scoring mechanism, achieving significant reductions in resource usage compared to existing state-of-the-art methods.

The Gist

Imagine you are trying to organize a massive, high-stakes dance party, but the venue is split into several separate rooms (called cores). The dancers are qubits (quantum bits), and the music is a quantum circuit (a set of instructions).

To make the dance work, pairs of dancers sometimes need to hold hands and spin together. If they are in the same room, they can just walk over to each other easily. But if they are in different rooms, they can't just walk through the walls. They have to use a special, expensive, and slow "teleportation" service to move from one room to another. This service consumes a limited resource called an EPR pair (think of it as a precious "magic ticket").

The problem is: How do you move the dancers around so they can dance together while using the fewest possible magic tickets?

This is the problem DSABRE solves. Here is how the paper explains it in simple terms:

1. The Problem with Previous Methods

Before DSABRE, other routers (like TELESABRE) were like traffic cops who only reacted to problems.

• If a room got too crowded with dancers, the old routers would wait until a traffic jam happened.
• Once jammed, they would try to force a dancer out, but this often burned extra magic tickets or caused the whole party to stall (a "deadlock").
• They also looked at the dance instructions in a messy, random order, which made it hard to predict who needed to move next.

2. The DSABRE Solution: A Smarter, Proactive Manager

DSABRE is a new "router" (a traffic manager) that uses a smarter strategy. It has three main tricks to save magic tickets:

A. The "Five-Point Scorecard" (Better Decision Making)

When DSABRE decides whether to move a dancer to a new room, it doesn't just look at "how close" the partner is. It uses a five-term scorecard:

1. Staging Cost: How many steps does the dancer need to take inside their current room to get to the door?
2. Capacity Penalty: This is the big one. If a destination room is already packed with dancers, DSABRE gives it a huge "bad score." It refuses to send dancers there, preventing the room from becoming a traffic jam.
3. Hop Gain: It rewards moves that get the dancer closer to their final destination room, even if they aren't there yet.
4. Immediate Gain: How much closer does this move get the dancer to their partner right now?
5. Lookahead: It peeks a few steps into the future to see if this move helps with upcoming dances.

Analogy: Imagine you are moving furniture. Old routers would just push a sofa into the next room because it was "close," even if that room was already full of boxes. DSABRE checks if the room is full first and says, "No, that room is too crowded; let's put the sofa in the hallway instead."

B. The "Proactive Evacuation" (Clearing the Jam Before It Happens)

This is DSABRE's secret weapon.

• Old way: Wait until a room is 100% full, then panic and try to move people out.
• DSABRE way: It keeps a "demand list." If it sees that Room A is about to get flooded with dancers for an upcoming dance, but Room A is already nearly full, it proactively moves some idle dancers (those not dancing right now) out of Room A before the rush starts.
• Result: When the rush arrives, there is space. No traffic jams, no wasted magic tickets.

C. The "Layer-by-Layer" Map (Better Planning)

When DSABRE looks ahead to see what dances are coming up, it doesn't just scan the list randomly. It builds a map layer by layer, respecting the order of the dance.

• Analogy: Imagine reading a recipe. An old router might read the ingredients for the dessert before the soup. DSABRE reads the recipe in the correct order, ensuring it knows exactly which ingredients (dancers) are needed next, so it doesn't waste time moving things that aren't needed yet.

3. The Results: A Much More Efficient Party

The authors tested DSABRE on many different "parties" (quantum circuits) of various sizes (25, 36, and 64 dancers).

• The Outcome: DSABRE used 41% to 44% fewer magic tickets (EPR pairs) than the previous best method (TELESABRE).
• Scalability: When they tested it on a huge party with up to 360 dancers, DSABRE still worked perfectly, while the old method often got stuck and gave up.

Summary

In short, DSABRE is a smarter way to organize quantum computers that are made of many small chips connected together. Instead of waiting for traffic jams to happen, it:

1. Checks capacity before sending dancers to crowded rooms.
2. Moves idle dancers out early to make space.
3. Plans the moves in a logical, step-by-step order.

This saves the expensive "magic tickets" (EPR pairs) needed to connect the chips, making the quantum computer run more efficiently.

Technical Summary

Technical Summary: DSABRE – A SABRE-Style Router for Multi-Core Distributed Quantum Computers

Problem Statement
The path to fault-tolerant quantum computing requires scaling beyond single monolithic chips to Distributed Quantum Computers (DQCs), where multiple small Quantum Processing Units (QPUs or "cores") are interconnected via photonic or microwave links. Executing circuits on DQCs involves a compilation pipeline comprising qubit allocation, communication-primitive selection, and routing/scheduling. The dominant objective in this context is minimizing EPR consumption (entangled pairs), as EPR generation is slow, noisy, and rate-limited compared to local gate operations.

While state-of-the-art routers like TELESABRE utilize SABRE-style heuristics to route circuits across cores, they handle congestion defensively. TELESABRE discourages landing in saturated cores via penalties and attempts to recover from deadlocks by dropping lookahead information. However, on dense or large instances, this reactive approach often burns excessive EPR pairs or fails to converge entirely. The core challenge addressed by this paper is the lack of proactive congestion management and the inefficiency of existing lookahead mechanisms in inter-core settings.

Methodology: DSABRE
DSABRE is a SABRE-style router designed for multi-core processors. It operates within a fixed initial layout (generated by Qiskit SabreLayout) and focuses on the routing stage: ordering intra-core SWAPs and inter-core teleportations (specifically teledata, moving logical qubits between cores). The algorithm runs a lookahead-driven loop with four phases per iteration:

1. Drain: Execute 1Q gates and adjacent intra-core 2Q gates.
2. Partition: Separate the remaining front-layer gates into intra-core ($F_{intra}$) and inter-core ($F_{inter}$).
3. Score & Apply:
   • If $F_{intra}$ is non-empty, select the best intra-core SWAP.
   • If $F_{intra}$ is empty, score inter-core teleportation candidates and proactive congestion relief candidates, applying the lowest-scoring move.
4. Checkpoint/Rollback: Save state upon progress; if stalled for a set number of iterations, restore a checkpoint and force progress to escape deadlock.

Key Contributions and Mechanisms
The paper identifies three specific mechanisms that drive DSABRE's improvement over the state of the art:

1. Five-Term Gate-Centric Teleportation Score:
   Unlike TELESABRE's global energy estimation, DSABRE uses a local, gate-centric score ($s$) for inter-core moves. The score combines five terms:

   • Staging Cost ($d_{prep}$): Intra-core SWAPs required to move a qubit to a communication port.
   • Capacity Penalty ($c_{cap}$): A term that explicitly penalizes teleporting into cores with low free capacity, preventing the router from flooding saturated cores.
   • Hop Gain ($g_{hop}$): A directional reward for moves that reduce the inter-core distance to the target, compensating when the landing port is far from the optimal staging position.
   • Front-Layer Gain ($\Delta_F$): Immediate reduction in physical distance for the current gate.
   • Lookahead ($\tilde{\Delta}_E$): A decay-weighted sum of future distance reductions.

2. Proactive Congestion Relief:
   DSABRE maintains an explicit demand vector over cores. Before a core becomes saturated (high demand, low capacity), the router proactively generates "relief candidates" to teleport idle qubits away from high-demand cores. These moves are scored within the same objective function (with $\Delta_F=0$) and compete directly with gate-driven moves. This prevents the "eviction cascade" that leads to deadlock in reactive systems.

3. BFS-Layer Inter-Core Extended Set:
   Standard SABRE builds lookahead sets in topological order, which can mix unrelated wires. TELESABRE uses BFS layers but weights gates arbitrarily. DSABRE constructs the inter-core lookahead set layer-by-layer using Breadth-First Search (BFS) on the DAG. Crucially, within each layer, gates sharing a wire with the front are emitted first. The lookahead decay is applied based on the BFS depth ($\gamma^{dep(g)}$), ensuring that near-term successors dominate the signal and that the set respects DAG dependencies more strictly than topological ordering.

Experimental Results
The authors evaluated DSABRE against TELESABRE and pytket-dqc (a gate-teleportation-based router) across 18 MQT-Bench circuits at 25, 36, and 64 logical qubits, using grid-of-grids architectures (B-grid and H-grid).

• EPR Reduction: DSABRE reduces the geometric-mean EPR consumption by 41–44% compared to TELESABRE and by 16–68% compared to pytket-dqc.
• Scalability: On a 64-qubit Random circuit, TELESABRE failed to converge on all seeds, while DSABRE completed the routing. A scalability sweep on Quantum Fourier Transform (QFT) circuits up to 360 qubits confirmed that DSABRE maintains its advantage as circuit size and architecture scale.
• Ablation Studies:
  • Removing the capacity penalty increased geometric-mean EPR by ~59% (25q) and ~59% (64q), identifying it as the most critical component.
  • Disabling proactive congestion relief increased EPR by 23.4% on the 64q suite, with dense circuits (AE, QFT) seeing over a 100% increase.
  • Replacing the BFS-layer extended set with topological ordering increased EPR by 3–11%, with gains growing for larger circuits.
• Cost Sensitivity: As the relative cost of teleportation ($c_{tele}$) increases (simulating photonic-link hardware), the performance gap between DSABRE and TELESABRE widens, with DSABRE saving up to ~39% more EPRs at high cost ratios.

Significance and Claims
The paper claims that distributed routing benefits less from complex per-candidate scoring formulas and more from ensuring that lookahead signals and architectural capacity constraints enter the same scoring step. By integrating proactive congestion relief and a capacity-aware score, DSABRE avoids the deadlocks and excessive EPR consumption that plague defensive, reactive routers.

The authors position DSABRE as complementary to static allocation methods (like hypergraph partitioning) and time-aware schedulers. They note that while DSABRE currently uses only teledata (state teleportation), it is designed to be a robust routing engine that can be combined with other primitives or burst-execution passes in future work. The results suggest that explicit capacity management is a necessary component for scaling distributed quantum compilation.