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 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 T gates for accuracy . 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 , 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.
And one to work out. Using , about how many T gates approximate a rotation to ?
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.