Routing Algorithms

What a Routing Algorithm Does

When the circuit contains a two-qubit gate on a pair of physical qubits that aren't directly connected in the coupling map, the router has to do something about it. The routing algorithm decides what: typically it inserts SWAP gates that move the involved qubits closer together until they're adjacent, then emits the gate.

Tessera ships three built-in routing algorithms and also accepts custom callables. Select one with the pathfinder parameter on transpile():

# Pass a registry key
transpile(qc, backend="IBM", pathfinder="bfs")
transpile(qc, backend="IBM", pathfinder="a_star")
transpile(qc, backend="IBM", pathfinder="sabre")

# Or pass a custom pairwise callable
def my_pathfinder(start: int, end: int) -> list[int]:
    return [start, end]  # simplistic example

transpile(qc, backend="IBM", pathfinder=my_pathfinder)

Note

The parameter is named pathfinder rather than routing_algorithm for backwards compatibility. It accepted custom callables under this name in v1.0.x, and v1.1 expanded what it accepts rather than introducing a new parameter. The asymmetry with layout_algorithm is intentional.

Pairwise vs. Whole-Circuit Strategies

Routing algorithms in Tessera fall into one of two shapes:

Pairwise: for each non-adjacent two-qubit gate, find a path between the two involved qubits and insert SWAPs along it. Walks the instruction list one gate at a time. BFS and A* are both pairwise and share a common engine.
Whole-circuit: maintain a front layer of executable gates and pick SWAPs based on a heuristic that considers the whole circuit at once, not just the next gate. SABRE is whole-circuit.

The shape matters because the custom-callable contract is only defined for pairwise algorithms. There's no public extension point for whole-circuit strategies in v1.1.

Choosing an Algorithm

Key	Shape	When to use
`"bfs"` (default)	Pairwise	Fastest; produces the shortest pairwise path
`"a_star"`	Pairwise	Matches BFS today on unweighted graphs; architecture-ready for noise-aware weighted edges
`"sabre"`	Whole-circuit	Higher quality on circuits with many non-adjacent two-qubit gates; uses lookahead instead of greedy pairwise paths

BFS

Key: "bfs" (default)

Breadth-first search over the coupling map's directed graph. For each non-adjacent two-qubit gate, BFS finds the shortest path (by hop count) from one endpoint to the other, then inserts SWAPs along all but the last edge of that path to bring the qubits adjacent, and emits the gate at the final pair.

Cheap and deterministic. Matches the v1.0.x default behavior. Good baseline for comparing the other algorithms against.

transpile(qc, backend="IBM", pathfinder="bfs")

A*

Key: "a_star"

A* shortest-path search over the coupling map's directed graph, using the coupling map's hop-distance function as an admissible heuristic. On today's unweighted coupling maps, A* produces the same paths BFS would, so gate counts are identical.

A* exists today as architecture for future noise-aware routing: it's the natural fit for weighted edges where the weight represents two-qubit gate error rate. Once weighted coupling maps land (planned for v1.x), A* will start producing different (and often better) paths than BFS.

transpile(qc, backend="IBM", pathfinder="a_star")

SABRE

Key: "sabre"

SWAP-based BidiREctional heuristic routing. Originally described in Li, Ding, Xie 2019. Rather than finding a path for each gate independently, SABRE maintains a front layer of currently-executable gates and a window of the next several gates, and picks each SWAP by scoring candidates against a heuristic that considers both the immediate front layer and a lookahead of 20 upcoming gates (weighted 0.5).

Often produces fewer total SWAPs than BFS or A* on circuits with many non-adjacent two-qubit gates, because it can pick swaps that help multiple gates instead of just the one in front of it.

transpile(qc, backend="IBM", pathfinder="sabre")

Note

The per-qubit decay term from the original SABRE paper is omitted in this release. It can be added later if benchmarks show it's worth the complexity.

Custom Pairwise Pathfinders

Pass a callable to pathfinder instead of a registered key. The callable must accept two physical qubit indices (start and end) and return a list of physical qubit indices representing the path between them, inclusive of both endpoints:

def my_pathfinder(start: int, end: int) -> list[int]:
    # Return a list of physical qubit indices representing the path
    # from start to end, inclusive of both endpoints.
    ...

transpile(qc, backend="IBM", pathfinder=my_pathfinder)

This is the same interface that pathfinder accepted in v1.0.x. Custom callables are wrapped in the shared pairwise routing engine and get the same SWAP-insertion behavior as BFS and A*, with your pathfinding logic substituted.

For details on the routing pass itself and how it consumes the algorithm, see the Passes Reference.