Number theory meets compilation: rings, grids and T-count.
Compiling a rotation into Clifford+T sounds like an engineering chore. It is really number theory: the gates live in the ring Z[21,i], exact synthesis is a Euclid-like descent, and optimal approximation is a lattice problem followed by a Diophantine equation.
What you’ll learn
Characterize the exactly synthesizable single-qubit unitaries by the ring Z[21,i], and prove that Rz(θ) is exact only for θ∈4πZ.
Run the denominator-exponent descent that produces T-optimal circuits, and relate it to the Matsumoto–Amano normal form.
Derive the counting lower bound of about 3log2(1/ε)T gates, and explain how Ross–Selinger's grid-problem algorithm attains it.
Survey ancilla, measurement and randomized techniques that go beyond ancilla-free unitary synthesis.
The ring behind Clifford+T
Let ω=eiπ/4. Every entry of H, S=diag(1,i) and the T gateT=diag(1,ω) lies in the ring
D[ω]=Z[21,i]={2ka+bω+cω2+dω3:a,b,c,d∈Z,k≥0},
so the matrix of every Clifford+T circuit does too (note that 2=ω−ω3 and i=ω2). Remarkably, the converse holds.
Check your understanding
Which of these single-qubit gates can a Clifford+T circuit implement exactly (up to global phase)?
Rz(π/8)
T=diag(1,eiπ/8)
Rx(π/4)
Ry(π/3)
Show the answer
C.Rx(π/4)
Rx(π/4)=HRz(π/4)H∝HTH. The others are impossible: Rz(π/8) and T∝Rz(π/8) fail the θ∈4πZ test, and Ry(π/3) has the entry ratio cos6π/sin6π=3∈/Q(ω), which no global phase can fix.
Exact synthesis by descent
How do you find the circuit? Measure the complexity of U by the smallest denominator exponent of ∣u00∣2, a number in Z[21]:
sde(x)=min{k≥0:2kx∈Z[2]}.
Then peel off one syllable at a time, like Euclid's algorithm.
Greedy: at each step try the four values of j; exactly one works.
U=T−j0HT−j1H⋯T−js−1HUs,sde(∣(Us)00∣2)<4
Invert the steps (H−1=H) and look up Us. Odd powers of T cost one T gate each; even powers are Clifford (T2=S).
T-count(U)=sde(∣u00∣2)+O(1)
The result can be rewritten in the unique Matsumoto–Amano normal form(T∣ϵ)(HT∣SHT)∗C, with ϵ the empty word and C a Clifford. It is T-optimal, every syllable contains exactly one T, and the number of syllables equals the sde up to an additive constant.
Example.HT has ∣u00∣2=21, so sde=2. Exact arithmetic shows that each further HT or SHT syllable raises the sde by exactly one, while the least k with 2kU integral grows only half as fast. Hence T-count ≈sde≈2k, a relation the approximation algorithm will exploit.
How many T gates must approximation cost?
DerivationCounting operators by T-count
#{U:T-count(U)=t}=Θ(2t)
Normal forms: two choices (HT or SHT) per T gate, times a finite set of Cliffords and phases.
#{U:T-count(U)≤t}=Θ(2t)≳!ε−3
An ε-net of SU(2) modulo phase, a 3-dimensional manifold, needs Θ(ε−3) points.
t≥3log2(1/ε)−O(1)for all but a small fraction of targets
The 3 is the dimension of SU(2).
For z-rotations alone, a volume heuristic gives the same constant: about 2tε2 of the operators lie within ε of the one-dimensional circle of z-rotations, and about 1/ε of them are needed to cover it, so again 2t≳ε−3.
Predict before you look
The best ancilla-free methods use about 3log2(1/ε)T gates. About how many T gates does a generic Rz(θ) need at accuracy ε=10−10?
Show the answer
100 T gates
log2(1010)=10log210≈33.2, so 3×33.2≈100, plus a small O(loglog(1/ε)) term. A generic SU(2) gate built from three Euler rotations costs roughly three times as much.
Ross–Selinger: a grid problem and a norm equation
Ross and Selinger approximate Rz(θ) by an exactly synthesizable matrix of the form
U=(ut−tˉuˉ),u=2kα,t=2kβ,α,β∈Z[ω],
up to a phase ωℓ on the second column, which we suppress. Unitarity is the single condition ∣u∣2+∣t∣2=1.
DerivationFrom operator norm to a thin sliver
U−Rz(θ)=(u−zt−tˉuˉ−zˉ),z=e−iθ/2
This has the quaternion form (ab−bˉaˉ), which is ∣a∣2+∣b∣2 times a unitary.
∥U−Rz(θ)∥2=∣u−z∣2+∣t∣2=2−2Re(zˉu)
Using ∣u∣2+∣t∣2=1.
∥U−Rz(θ)∥≤ε⟺u∈Rε:={u∈D:Re(zˉu)≥1−2ε2}
D is the closed unit disk. Rε is a thin circular segment near z: height ε2/2, width ≈2ε, area ≈32ε3.
tˉt=1−uˉu⟺βˉβ=2k−αˉα=:ξ∈Z[2]
The second column must complete the first: a norm equation for β.
ξ≥0 and ξ∙≥0⟺u∈D and u∙∈D
Here ∙ is the automorphism 2↦−2 fixing i (so ω∙=−ω). Both βˉβ and its conjugate β∙β∙ are ≥0, so these conditions are necessary.
The algorithm, for increasing k:
Grid problem. Enumerate α∈Z[ω] with α/2k∈Rε and (α/2k)∙∈D. Via α↦(α,α∙) this is lattice-point enumeration in a product of two convex sets in R4, one extremely thin and one round; grid operators that straighten the thin set make it efficient.
Norm equation. For each candidate, try to solve βˉβ=ξ. This is easy when ξ is easy to factor (for instance, prime); other candidates are skipped. With a factoring oracle, none need be skipped.
Exact synthesis. Feed the resulting U to the descent.
DerivationWhy the T-count comes out near 3 log₂(1/ε)
Embedded by two non-conjugate embeddings, Z[ω] is a lattice of covolume 4 (its Minkowski embedding); dividing by 2k shrinks all four real coordinates by 2−k/2.
#(Λk∩(Rε×D))≈4⋅4−k32ε3⋅π=6π4kε3
Volume over covolume, heuristically.
6π4kε3≳1⟺k≳23log2(1/ε)
Candidates appear once k≈23log2(1/ε). A few more increments of k supply candidates with an easy norm equation: the source of the O(loglog(1/ε)) term.
T-count≈sde(∣u∣2)≈2k≈3log2(1/ε)
∣u∣2=αˉα/2k typically has sde=2k. This matches the counting lower bound.
Large savings in arithmetic; no efficient exact algorithm is known in general
Think first Mixing turns coherent synthesis errors of size ε into a channel error of order ε2. For a target channel error δ, what typical T-count do you then need?
Accuracy ε≈δ per sampled circuit suffices, so about 3log2(1/δ)=1.5log2(1/δ)T gates: roughly half. You compile several circuits, but each run executes only one of them.
Key takeaways
Clifford+T matrices are exactly the unitaries over D[ω]=Z[21,i] (one ancilla for n qubits); Rz(θ) is exact only for θ∈4πZ.
Exact synthesis is a descent: one HTj step lowers the smallest denominator exponent by one, so the optimal T-count is sde(∣u00∣2)+O(1).
Counting forces about 3log2(1/ε)T gates; Ross–Selinger attain it by solving a grid problem and a norm equation.
Ancillas with measurement (repeat-until-success) and random mixing go further; optimal multi-qubit synthesis remains open.
Check yourself
In the interactive lesson these are scored with your confidence, and what you miss comes back for review.
Question 1
The matrix 21(1ii1) is
exactly Clifford+T; in fact it is a Clifford gate
exactly Clifford+T, with T-count 1
not exactly synthesizable, since i/2∈/D[ω]
synthesizable only with an ancilla
Show the answer
A. exactly Clifford+T; in fact it is a Clifford gate
Its entries lie in D[ω], so an exact circuit exists. In fact it is Rx(−π/2)∝HS†H, with T-count 0.
Question 2
During exact synthesis you find sde(∣u00∣2)=40. Roughly what T-count will the optimal circuit have?
About 5
About 40
About 240
About 40
Show the answer
B. About 40
Each HT or SHT syllable changes the sde by one and contains one T, so the T-count equals the sde up to a small additive constant.
Question 3
Where does the constant 3 in the T-count 3log2(1/ε) come from?
From the three Euler angles of a single-qubit unitary
From the three Pauli matrices
From the dimension of SU(2): an ε-net needs ∼ε−3 points, while T-count t yields only ∼2t operators
From the order of T, which is 8=23
Show the answer
C. From the dimension of SU(2): an ε-net needs ∼ε−3 points, while T-count t yields only ∼2t operators
2t≳ε−3 gives t≳3log2(1/ε), and Ross–Selinger's grid algorithm attains it for typical z-rotations.
Question 4
In Ross–Selinger's algorithm, why must the conjugate u∙ also lie in the unit disk?
So that the circuit needs no ancillas
To make the T-count even
Because Rz(θ) is diagonal
Because ξ=2k−αˉα must be doubly positive (ξ≥0 and ξ∙≥0) for βˉβ=ξ to be solvable
Show the answer
D. Because ξ=2k−αˉα must be doubly positive (ξ≥0 and ξ∙≥0) for βˉβ=ξ to be solvable
βˉβ and its ∙-conjugate are both squared moduli, hence ≥0. A solution therefore needs ξ≥0 (that is, u∈D) and ξ∙≥0 (that is, u∙∈D).
Further reading
V. Kliuchnikov, D. Maslov & M. Mosca, "Fast and efficient exact synthesis of single-qubit unitaries generated by Clifford and T gates", Quantum Inf. Comput. 13, 607 (2013), arXiv:1206.5236.
B. Giles & P. Selinger, "Exact synthesis of multiqubit Clifford+T circuits", Phys. Rev. A 87, 032332 (2013).
K. Matsumoto & K. Amano, "Representation of quantum circuits with Clifford and π/8 gates" (2008), arXiv:0806.3834.
N. J. Ross & P. Selinger, "Optimal ancilla-free Clifford+T approximation of z-rotations", Quantum Inf. Comput. 16, 901 (2016), arXiv:1403.2975.
E. T. Campbell, "Shorter gate sequences for quantum computing by mixing unitaries", Phys. Rev. A 95, 042306 (2017).