Simple Algorithm
Quantum Computing · Rydberg State · 28 min

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 O(n)O(\sqrt n) 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 dd needs at least d−1d-1 SWAPs beforehand.
  • On an m×mm\times m grid every permutation can be routed in at most 3m3m layers of parallel SWAPs (Alon, Chung & Graham, 1994). Route each layer of a depth-DD circuit this way and you get depth O(Dn)O(D\sqrt n) on n=m2n=m^2 qubits, with no cleverness at all.
Predict before you look

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: 5−1=45-1=4 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:

text
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. D[π′(g)]D[\pi'(g)] is the distance between the physical positions of gate gg's qubits; W<1W<1 (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 O(∣F∣⋅deg⁡G)O(\abs{F}\cdot\deg G) 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 δ\delta 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 EE and score SWAPs on the front layer alone. What goes wrong?

The search becomes myopic. Two SWAPs that tie on FF 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 W<1W<1, 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 (HH=IHH=\id, CX CX=I\text{CX}\,\text{CX}=\id), merge rotations about the same axis (RZ(a)RZ(b)=RZ(a+b)R_Z(a)R_Z(b)=R_Z(a+b)), 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.

DerivationWhat commutes with a CNOT
  1. CX=∣0⟩ ⁣⟨0∣c⊗It+∣1⟩ ⁣⟨1∣c⊗Xt\text{CX}=\dyad{0}_c\otimes\id_t+\dyad{1}_c\otimes X_t

    Write the CNOT with control cc and target tt as

  2. [CX,Zc]=0,[CX,Xt]=0[\text{CX},Z_c]=0,\qquad[\text{CX},X_t]=0

    ZcZ_c commutes with both projectors, and XtX_t commutes with both I\id and XX. Hence any RZR_Z on the control and any RXR_X on the target slide through a CNOT:

  3. CX Zt CX=ZcZt,CX Xc CX=XcXt\text{CX}\,Z_t\,\text{CX}=Z_cZ_t,\qquad \text{CX}\,X_c\,\text{CX}=X_cX_t

    Conjugation propagates Paulis across the CNOT: ZZ spreads from target to control, XX from control to target.

  4. CX (I⊗RZ(θ)) CX=e−iθZcZt/2\text{CX}\,\big(\id\otimes R_Z(\theta)\big)\,\text{CX}=e^{-i\theta Z_cZ_t/2}

    Exponentiating the first identity gives the ZZZZ-rotation gadget every compiler uses (for QAOA cost layers, Trotter steps, and more):

A commutation-aware pass builds the DAG modulo these relations: in CX (RZ(θ)⊗I) CX\text{CX}\,(R_Z(\theta)\otimes\id)\,\text{CX}, the rotation slides out and the two CNOTs cancel. Circuits over {CX,RZ}\{\text{CX},R_Z\} admit a global version of this idea. They act as ∣x⟩↦eif(x)∣Ax⟩\ket x\mapsto e^{if(x)}\ket{Ax} with AA invertible over F2\mathbb F_2 and ff a phase polynomial, a weighted sum of parities of xx, and resynthesizing the pair (f,A)(f,A) from scratch can remove many CNOTs and TT gates at once (Amy, Maslov & Mosca, 2014).

Check your understanding

Which rewrite is invalid?

  1. CXc→t (RZ(θ)⊗I)=(RZ(θ)⊗I) CXc→t\text{CX}_{c\to t}\,(R_Z(\theta)\otimes\id)=(R_Z(\theta)\otimes\id)\,\text{CX}_{c\to t}
  2. CXc→t (I⊗RX(θ))=(I⊗RX(θ)) CXc→t\text{CX}_{c\to t}\,(\id\otimes R_X(\theta))=(\id\otimes R_X(\theta))\,\text{CX}_{c\to t}
  3. CXc→t (I⊗RZ(θ))=(I⊗RZ(θ)) CXc→t\text{CX}_{c\to t}\,(\id\otimes R_Z(\theta))=(\id\otimes R_Z(\theta))\,\text{CX}_{c\to t}
  4. RZ(a) RZ(b)=RZ(a+b)R_Z(a)\,R_Z(b)=R_Z(a+b)
Show the answer

C. CXc→t (I⊗RZ(θ))=(I⊗RZ(θ)) CXc→t\text{CX}_{c\to t}\,(\id\otimes R_Z(\theta))=(\id\otimes R_Z(\theta))\,\text{CX}_{c\to t}

ZZ on the target does not commute with the CNOT: conjugation maps Zt↦ZcZtZ_t\mapsto Z_cZ_t, so sliding RZR_Z across the target produces the entangling rotation e−iθZcZt/2e^{-i\theta Z_cZ_t/2}. 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:

  1. Convert the circuit to a graph-like diagram: only Z-spiders, connected by Hadamard edges.
  2. Remove interior Clifford spiders (phases that are multiples of π/2\pi/2) with local complementation and pivoting, graph operations that delete vertices while complementing edges among their neighbors.
  3. 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 TT-count without disturbing anything else (Kissinger & van de Wetering, 2020).
  4. 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 dd needs at least d−1d-1 SWAPs; grids route any permutation in O(n)O(\sqrt n) 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 TT-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.

Question 1

In the NP-hardness proof, why does a circuit whose interaction graph is a path through all mm logical qubits encode Hamiltonian path in a coupling graph with mm vertices?

  1. Because SWAP gates are themselves NP-hard to implement
  2. Because a zero-SWAP execution needs a layout that puts consecutive logical qubits on adjacent physical qubits, which is exactly a Hamiltonian path in GG
  3. Because every circuit's interaction graph is a path
  4. 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 GG

With zero SWAPs the layout is fixed, so each CNOT (qi,qi+1)(q_i,q_{i+1}) must sit on an edge: the images π(q1),…,π(qm)\pi(q_1),\dots,\pi(q_m) form a path visiting every vertex of GG once.

Question 2

What does SABRE's reverse traversal accomplish?

  1. It undoes the inserted SWAPs to restore the original layout
  2. It verifies the routed circuit by running it backwards
  3. It finds a good initial layout: the final layout from routing the reversed circuit seeds the forward pass
  4. 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.

Question 3

The gadget CX (I⊗RZ(θ)) CX\text{CX}\,(\id\otimes R_Z(\theta))\,\text{CX} (control on qubit 1, target on qubit 2) equals which operator?

  1. I⊗RZ(θ)\id\otimes R_Z(\theta)
  2. RZ(θ)⊗RZ(θ)R_Z(\theta)\otimes R_Z(\theta)
  3. e−iθX⊗X/2e^{-i\theta X\otimes X/2}
  4. e−iθZ⊗Z/2e^{-i\theta Z\otimes Z/2}
Show the answer

D. e−iθZ⊗Z/2e^{-i\theta Z\otimes Z/2}

Conjugating ZtZ_t by the CNOT gives ZcZtZ_cZ_t; exponentiate. This is how ZZZZ interactions are compiled to CNOT hardware.

Question 4

A compiler resynthesizes a generic two-qubit block. In the worst case, how many CNOTs does it need?

  1. 1
  2. 2
  3. 3
  4. 4
Show the answer

C. 3

The KAK decomposition puts all entangling content into ei(aXX+bYY+cZZ)e^{i(aXX+bYY+cZZ)}, 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).