142
Part Three · D · Error correction and fault tolerance

Compilation: gate synthesis, routing, optimization

An algorithm on paper uses any gate between any qubits. A real chip offers a few native gates, each qubit wired to only a few neighbours, and, after error correction, a steep price for every T gate. The compiler translates one into the other, and a good compiler can cut the cost several times over. The same algorithm can cost ten times more on the wrong chip layout.

On the plate: a circuit routed onto three chip layouts.

T-count and synthesis

In fault-tolerant machines, Clifford gates are cheap and T gates expensive (Chapter 140), so the cost of a circuit is its T-count, and its time is the T-depth. A Toffoli gate needs 7 T gates in the standard decomposition. An arbitrary rotation Rz(θ)R_z(\theta) must be approximated from Clifford and T gates; Solovay–Kitaev (Chapter 100) gives polylogarithmic length, but Neil Ross and Peter Selinger’s 2016 gridsynth algorithm is optimal, using about 3log⁡2(1/ε)3\log_2(1/\varepsilon) T gates for accuracy ε\varepsilon. For accuracy 10^-10, see the count. Established

Routing

A CNOT between qubits that are not connected requires SWAPs (three CNOTs each) to bring them together. Choose a chip: , , , and a circuit of 30 random two-qubit gates on 9 qubits, then . The plate routes greedily, moving one qubit along a shortest path until the pair is adjacent. Optimal routing is NP-hard; Gushu Li, Yufei Ding and Yuan Xie’s 2019 SABRE heuristic, now standard in IBM’s Qiskit, routes forwards and backwards to pick a good starting layout and looks ahead at upcoming gates. IBM’s chips use a sparse “heavy-hex” lattice to reduce crosstalk, at a routing cost. Established

Optimization: peepholes, ZX, Pauli-based computation

Local peephole rules cancel adjacent inverse gates and merge rotations. The ZX-calculus (Chapter 109) goes further: rewrite the whole circuit as a graph of spiders, simplify with a few rules, and extract a circuit again. Aleks Kissinger and John van de Wetering showed in 2020 that this reduces T-counts substantially on standard benchmarks. At the fault-tolerant level, Daniel Litinski’s Pauli-based computation commutes all Clifford gates to the end, leaving a sequence of multi-qubit Pauli rotations by π/8\pi/8, each consuming one magic state; the Cliffords disappear into the final measurements. Much of the drop in factoring estimates (Chapter 143) came from such compilation advances rather than better hardware. Established

What you now have

T-count and T-depth, the Toffoli’s 7 T gates, optimal single-qubit synthesis with gridsynth, routing with SWAPs and SABRE, peephole and ZX-based optimization, and Pauli-based computation.

· · ·

Three questions to carry with you.

Why is T-count the main cost?tap
Each T gate consumes a distilled or cultivated magic state; Cliffords are nearly free.
What does a SWAP cost?tap
Three CNOTs.
How does gridsynth’s T-count scale?tap
About 3 log₂(1/ε), which is optimal.

And one to work out. Using 3log⁡2(1/ε)3\log_2(1/\varepsilon), about how many T gates approximate a rotation to ε=10−10\varepsilon = 10^{-10}?

T ≈

Sources: N. J. Ross and P. Selinger, Quantum Inf. Comput. 16, 901 (2016). G. Li, Y. Ding and Y. Xie, Proc. ASPLOS 2019, 1001. A. Kissinger and J. van de Wetering, Phys. Rev. A 102, 022406 (2020). D. Litinski, Quantum 3, 128 (2019). M. Amy, D. Maslov, M. Mosca and M. Roetteler, IEEE Trans. CAD 32, 818 (2013) (T-depth of Toffoli). Checked by the plate: greedy shortest-path routing on each topology.

Next · Chapter 143
Resource estimation: from algorithm to physical qubits

"How many qubits to break RSA?" fell from 20 million (2019) to under 1 million (2025). Here is exactly where the savings came from.

Turn the page