Compilation: Routing & Optimization
Mapping logical circuits onto constrained hardware.
Your circuit assumes any qubit can talk to any other; the chip disagrees. Finding the cheapest way to reconcile the two is NP-hard, so every production compiler is a stack of heuristics and exact local rewrites. This lesson proves the hardness, dissects the SABRE heuristic, and builds the rewrite rules up to the ZX-calculus.
What you’ll learn
- Formalize layout and routing on a coupling graph, and prove that minimizing SWAPs is NP-hard by reduction from Hamiltonian path.
- Derive simple lower bounds on routing cost and the depth overhead on 2D grids.
- Describe SABRE: front layer, look-ahead cost with decay, and bidirectional layout search.
- Prove the commutation rules behind peephole and commutation-based passes, and state the three-CNOT bound for two-qubit unitaries.
- Explain ZX-diagrams, spider fusion and graph-theoretic simplification, and why circuit extraction is the hard step.
Layout and routing, formally
Other formulations are hard too. Siraichi et al. (2018) formalized the problem as qubit allocation and analyzed its complexity, and even routing a single fixed permutation with the fewest SWAPs, the token swapping problem, is NP-hard on general graphs (Miltzow et al., 2016). Two simple quantitative facts frame what heuristics can hope for:
- A SWAP moves at most one of two given logical qubits one step closer to the other (swapping the two with each other leaves their distance at 1), so a gate on a pair at distance needs at least SWAPs beforehand.
- On an grid every permutation can be routed in at most layers of parallel SWAPs (Alon, Chung & Graham, 1994). Route each layer of a depth- circuit this way and you get depth on qubits, with no cleverness at all.
Two logical qubits sit at distance 5 on the coupling graph. At least how many SWAPs must precede a gate between them?
Show the answer
4 SWAPs
Each SWAP reduces their distance by at most one, and they must reach distance 1: SWAPs, i.e. 12 CNOTs of overhead for one gate. Real heuristics try to make each SWAP serve several upcoming gates at once.
SABRE: SWAP-based bidirectional search
Li, Ding & Xie (2019) introduced SABRE, which (as of the mid-2020s) underlies the default layout and routing passes of Qiskit's transpiler, after a fast check for a perfect zero-SWAP layout. It works on the circuit's dependency DAG:
SABRE_ROUTE(dag, G, π):
D ← all-pairs shortest-path distances on G # once
F ← front layer: gates with no unexecuted predecessors
while F ≠ ∅:
execute every gate of F that is 1-qubit or sits on an edge of G under π
if anything executed: update F, reset decay, continue
E ← extended set: the next ~20 two-qubit gates after F # look-ahead
for each SWAP s on an edge of G touching a qubit of F:
π' ← π composed with s
H(s) ← max(δ[s.a], δ[s.b]) · ( mean_{g∈F} D[π'(g)] + W · mean_{g∈E} D[π'(g)] )
apply the SWAP with smallest H; π ← π composed with s
δ[s.a] += 0.001; δ[s.b] += 0.001 # decay
return routed circuit, final layout πSimplified. is the distance between the physical positions of gate 's qubits; (e.g. 0.5) weights the future below the present.
Three ideas make it work:
- Front-layer greedy search. Only SWAPs touching the front layer are candidates, so each decision costs cheap evaluations instead of a search over permutations.
- Look-ahead with decay. The extended set steers SWAPs toward gates that come next, and the decay factor penalizes reusing the same qubits, which trades SWAP count for parallelism (lower depth).
- Bidirectional layout. Route the circuit forward from a random layout, use the final layout as the initial layout for the reversed circuit, route backward, and repeat. Since the reversed circuit has the same interactions, each pass ends where the next one wants to start; a few round trips from many random seeds give far better initial layouts than random or greedy placement.
Think first Suppose you drop the extended set and score SWAPs on the front layer alone. What goes wrong?
The search becomes myopic. Two SWAPs that tie on can differ hugely for the next gates, and a SWAP that helps now can push apart qubits needed immediately afterwards, causing SWAP ping-pong. The look-ahead term (with , so current gates still dominate) breaks such ties in favor of the future.
Peephole and commutation-based optimization
After routing, optimization passes shrink the circuit with exact local rewrites: cancel adjacent inverses (, ), merge rotations about the same axis (), and resynthesize every maximal run of one-qubit gates as a single Euler decomposition. Their power comes from commutation: gates that are not adjacent may become adjacent after legal reorderings.
Write the CNOT with control and target as
commutes with both projectors, and commutes with both and . Hence any on the control and any on the target slide through a CNOT:
Conjugation propagates Paulis across the CNOT: spreads from target to control, from control to target.
Exponentiating the first identity gives the -rotation gadget every compiler uses (for QAOA cost layers, Trotter steps, and more):
A commutation-aware pass builds the DAG modulo these relations: in , the rotation slides out and the two CNOTs cancel. Circuits over admit a global version of this idea. They act as with invertible over and a phase polynomial, a weighted sum of parities of , and resynthesizing the pair from scratch can remove many CNOTs and gates at once (Amy, Maslov & Mosca, 2014).
Which rewrite is invalid?
Show the answer
C.
on the target does not commute with the CNOT: conjugation maps , so sliding across the target produces the entangling rotation . The other three are exact identities.
ZX-calculus optimization
The ZX-calculus replaces circuits by graphs of spiders, with rewrite rules that see through gate boundaries.
The key rules: spider fusion (connected spiders of the same color merge and their phases add, generalizing rotation merging to any number of legs), color change (Hadamards swap Z and X), and π-copy and bialgebra, which encode how Paulis and CNOTs propagate. The calculus is complete for stabilizer diagrams (Backens, 2014) and, with suitable rule sets, for Clifford+T and for all qubit linear maps (results from 2018 on): two diagrams denote the same linear map iff the rules rewrite one into the other.
Duncan, Kissinger, Perdrix & van de Wetering (2020) turned this into an optimizer:
- Convert the circuit to a graph-like diagram: only Z-spiders, connected by Hadamard edges.
- Remove interior Clifford spiders (phases that are multiples of ) with local complementation and pivoting, graph operations that delete vertices while complementing edges among their neighbors.
- What remains are boundary spiders and non-Clifford phase gadgets. Phase teleportation fuses non-Clifford phases that the original circuit kept apart and writes the fused phases back into the original circuit, cutting -count without disturbing anything else (Kissinger & van de Wetering, 2020).
- Extract a circuit, guided by a flow condition (gflow) that the rewrites preserve.
Key takeaways
- A zero-SWAP layout is a subgraph embedding, so minimizing SWAPs is NP-hard, even on grid-like chips.
- A pair at distance needs at least SWAPs; grids route any permutation in depth.
- SABRE chooses SWAPs greedily on the front layer with look-ahead and decay, and refines layouts with forward–backward passes.
- Exact rewrites (cancellation, rotation merging, commutation through CNOTs, KAK resynthesis with at most three CNOTs) do the optimizing.
- The ZX-calculus generalizes rewriting: spider fusion and graph simplification cut -count, and circuit extraction is the hard step.
Check yourself
In the interactive lesson these are scored with your confidence, and what you miss comes back for review.
In the NP-hardness proof, why does a circuit whose interaction graph is a path through all logical qubits encode Hamiltonian path in a coupling graph with vertices?
- Because SWAP gates are themselves NP-hard to implement
- Because a zero-SWAP execution needs a layout that puts consecutive logical qubits on adjacent physical qubits, which is exactly a Hamiltonian path in
- Because every circuit's interaction graph is a path
- Because routing requires simulating the circuit
Show the answer
B. Because a zero-SWAP execution needs a layout that puts consecutive logical qubits on adjacent physical qubits, which is exactly a Hamiltonian path in
With zero SWAPs the layout is fixed, so each CNOT must sit on an edge: the images form a path visiting every vertex of once.
What does SABRE's reverse traversal accomplish?
- It undoes the inserted SWAPs to restore the original layout
- It verifies the routed circuit by running it backwards
- It finds a good initial layout: the final layout from routing the reversed circuit seeds the forward pass
- It halves the depth of the circuit
Show the answer
C. It finds a good initial layout: the final layout from routing the reversed circuit seeds the forward pass
A layout that works well at the end of the reversed circuit is one that works well at the start of the original. Alternating forward and backward passes from random seeds refines the initial placement before the final routing.
The gadget (control on qubit 1, target on qubit 2) equals which operator?
Show the answer
D.
Conjugating by the CNOT gives ; exponentiate. This is how interactions are compiled to CNOT hardware.
A compiler resynthesizes a generic two-qubit block. In the worst case, how many CNOTs does it need?
- 1
- 2
- 3
- 4
Show the answer
C. 3
The KAK decomposition puts all entangling content into , which three CNOTs (with one-qubit gates) always implement; SWAP shows three are sometimes necessary.
Further reading
- G. Li, Y. Ding & Y. Xie, "Tackling the qubit mapping problem for NISQ-era quantum devices", ASPLOS (2019).
- M. Y. Siraichi, V. F. dos Santos, S. Collange & F. M. Q. Pereira, "Qubit allocation", CGO (2018).
- F. Vatan & C. Williams, "Optimal quantum circuits for general two-qubit gates", Phys. Rev. A 69, 032315 (2004).
- R. Duncan, A. Kissinger, S. Perdrix & J. van de Wetering, "Graph-theoretic simplification of quantum circuits with the ZX-calculus", Quantum 4, 279 (2020).
- B. Coecke & A. Kissinger, Picturing Quantum Processes (Cambridge, 2017).