Simple Algorithm
Quantum Computing · Rydberg State · 32 min

Exact & Approximate Clifford+T Synthesis

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[12,i]\mathbb{Z}[\tfrac{1}{\sqrt2},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[12,i]\mathbb{Z}[\tfrac{1}{\sqrt2},i], and prove that Rz(θ)R_z(\theta) is exact only for θ∈π4Z\theta\in\frac\pi4\mathbb{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 3log⁡2(1/ε)3\log_2(1/\varepsilon) TT 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\omega = e^{i\pi/4}. Every entry of HH, S=diag⁡(1,i)S=\diag(1,i) and the T gate T=diag⁡(1,ω)T=\diag(1,\omega) lies in the ring

D[ω]=Z[12,i]={a+bω+cω2+dω32 k:a,b,c,d∈Z, k≥0},\mathbb{D}[\omega] = \mathbb{Z}\big[\tfrac{1}{\sqrt2},i\big] = \Big\{\frac{a+b\omega+c\omega^2+d\omega^3}{\sqrt2^{\,k}} : a,b,c,d\in\mathbb{Z},\ k\ge0\Big\},

so the matrix of every Clifford+T circuit does too (note that 2=ω−ω3\sqrt2=\omega-\omega^3 and i=ω2i=\omega^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)?

  1. Rz(π/8)R_z(\pi/8)
  2. T=diag⁡(1,eiπ/8)\sqrt{T} = \diag(1,e^{i\pi/8})
  3. Rx(π/4)R_x(\pi/4)
  4. Ry(π/3)R_y(\pi/3)
Show the answer

C. Rx(π/4)R_x(\pi/4)

Rx(π/4)=H Rz(π/4) H∝HTHR_x(\pi/4) = H\,R_z(\pi/4)\,H\propto HTH. The others are impossible: Rz(π/8)R_z(\pi/8) and T∝Rz(π/8)\sqrt T\propto R_z(\pi/8) fail the θ∈π4Z\theta\in\frac\pi4\mathbb{Z} test, and Ry(π/3)R_y(\pi/3) has the entry ratio cos⁡π6/sin⁡π6=3∉Q(ω)\cos\frac\pi6/\sin\frac\pi6=\sqrt3\notin\mathbb{Q}(\omega), which no global phase can fix.

Exact synthesis by descent

How do you find the circuit? Measure the complexity of UU by the smallest denominator exponent of ∣u00∣2\abs{u_{00}}^2, a number in Z[12]\mathbb{Z}[\tfrac{1}{\sqrt2}]:

sde⁡(x)=min⁡{k≥0:2 k x∈Z[2]}.\operatorname{sde}(x) = \min\{k\ge0 : \sqrt2^{\,k}\,x\in\mathbb{Z}[\sqrt2]\}.

Then peel off one syllable at a time, like Euclid's algorithm.

DerivationThe descent in action
  1. U0=U,Ur+1=HTjrUr,sde⁡(∣(Ur+1)00∣2)=sde⁡(∣(Ur)00∣2)−1U_0 = U,\qquad U_{r+1} = HT^{j_r}U_r,\qquad \operatorname{sde}\big(\abs{(U_{r+1})_{00}}^2\big) = \operatorname{sde}\big(\abs{(U_r)_{00}}^2\big)-1

    Greedy: at each step try the four values of jj; exactly one works.

  2. U=T−j0H T−j1H⋯T−js−1H  Us,sde⁡(∣(Us)00∣2)<4U = T^{-j_0}H\,T^{-j_1}H\cdots T^{-j_{s-1}}H\;U_s,\qquad \operatorname{sde}\big(\abs{(U_s)_{00}}^2\big)<4

    Invert the steps (H−1=HH^{-1}=H) and look up UsU_s. Odd powers of TT cost one TT gate each; even powers are Clifford (T2=ST^2=S).

  3. T-count(U)=sde⁡(∣u00∣2)+O(1)\text{T-count}(U) = \operatorname{sde}\big(\abs{u_{00}}^2\big)+\order{1}

    The result can be rewritten in the unique Matsumoto–Amano normal form (T ∣ ϵ) (HT ∣ SHT)∗ C(T\,|\,\epsilon)\,(HT\,|\,SHT)^{*}\,\mathcal{C}, with ϵ\epsilon the empty word and C\mathcal{C} a Clifford. It is T-optimal, every syllable contains exactly one TT, and the number of syllables equals the sde up to an additive constant.

  4. Example. HTHT has ∣u00∣2=12\abs{u_{00}}^2 = \tfrac12, so sde⁡=2\operatorname{sde}=2. Exact arithmetic shows that each further HTHT or SHTSHT syllable raises the sde by exactly one, while the least kk with 2 kU\sqrt2^{\,k}U integral grows only half as fast. Hence T-count ≈sde⁡≈2k\approx\operatorname{sde}\approx2k, a relation the approximation algorithm will exploit.

How many T gates must approximation cost?

DerivationCounting operators by T-count
  1. #{U:T-count(U)=t}=Θ(2t)\#\{U : \text{T-count}(U) = t\} = \Theta(2^t)

    Normal forms: two choices (HTHT or SHTSHT) per TT gate, times a finite set of Cliffords and phases.

  2. #{U:T-count(U)≤t}=Θ(2t) ≳! ε−3\#\{U : \text{T-count}(U)\le t\} = \Theta(2^t)\ \overset{!}{\gtrsim}\ \varepsilon^{-3}

    An ε\varepsilon-net of SU(2)SU(2) modulo phase, a 3-dimensional manifold, needs Θ(ε−3)\Theta(\varepsilon^{-3}) points.

  3. t ≥ 3log⁡2(1/ε)−O(1)for all but a small fraction of targetst\ \ge\ 3\log_2(1/\varepsilon)-\order{1}\qquad\text{for all but a small fraction of targets}

    The 33 is the dimension of SU(2)SU(2).

  4. For zz-rotations alone, a volume heuristic gives the same constant: about 2tε22^t\varepsilon^2 of the operators lie within ε\varepsilon of the one-dimensional circle of zz-rotations, and about 1/ε1/\varepsilon of them are needed to cover it, so again 2t≳ε−32^t\gtrsim\varepsilon^{-3}.

Predict before you look

The best ancilla-free methods use about 3log⁡2(1/ε)3\log_2(1/\varepsilon) TT gates. About how many TT gates does a generic Rz(θ)R_z(\theta) need at accuracy ε=10−10\varepsilon = 10^{-10}?

Show the answer

100 T gates

log⁡2(1010)=10log⁡210≈33.2\log_2(10^{10}) = 10\log_2 10\approx33.2, so 3×33.2≈1003\times33.2\approx100, plus a small O(log⁡log⁡(1/ε))\order{\log\log(1/\varepsilon)} term. A generic SU(2)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(θ)R_z(\theta) by an exactly synthesizable matrix of the form

U=(u−tˉtuˉ),u=α2 k,t=β2 k,α,β∈Z[ω],U = \begin{pmatrix}u & -\bar t\\ t & \bar u\end{pmatrix},\qquad u = \frac{\alpha}{\sqrt2^{\,k}},\quad t = \frac{\beta}{\sqrt2^{\,k}},\quad \alpha,\beta\in\mathbb{Z}[\omega],

up to a phase ωℓ\omega^\ell on the second column, which we suppress. Unitarity is the single condition ∣u∣2+∣t∣2=1\abs{u}^2+\abs{t}^2 = 1.

DerivationFrom operator norm to a thin sliver
  1. U−Rz(θ)=(u−z−tˉtuˉ−zˉ),z=e−iθ/2U - R_z(\theta) = \begin{pmatrix}u-z & -\bar t\\ t & \bar u-\bar z\end{pmatrix},\qquad z = e^{-i\theta/2}

    This has the quaternion form (a−bˉbaˉ)\begin{pmatrix}a&-\bar b\\ b&\bar a\end{pmatrix}, which is ∣a∣2+∣b∣2\sqrt{\abs a^2+\abs b^2} times a unitary.

  2. ∥U−Rz(θ)∥2=∣u−z∣2+∣t∣2=2−2 Re(zˉ u)\norm{U-R_z(\theta)}^2 = \abs{u-z}^2+\abs{t}^2 = 2-2\,\mathrm{Re}(\bar z\,u)

    Using ∣u∣2+∣t∣2=1\abs{u}^2+\abs{t}^2=1.

  3. ∥U−Rz(θ)∥≤ε  ⟺  u∈Rε:={u∈D:Re(zˉ u)≥1−ε22}\norm{U-R_z(\theta)}\le\varepsilon\iff u\in\mathcal{R}_\varepsilon := \big\{u\in\mathcal{D} : \mathrm{Re}(\bar z\,u)\ge1-\tfrac{\varepsilon^2}{2}\big\}

    D\mathcal{D} is the closed unit disk. Rε\mathcal{R}_\varepsilon is a thin circular segment near zz: height ε2/2\varepsilon^2/2, width ≈2ε\approx2\varepsilon, area ≈23ε3\approx\tfrac23\varepsilon^3.

  4. tˉ t=1−uˉ u  ⟺  βˉβ=2k−αˉα=:ξ∈Z[2]\bar t\,t = 1-\bar u\,u\iff\bar\beta\beta = 2^k-\bar\alpha\alpha =: \xi\in\mathbb{Z}[\sqrt2]

    The second column must complete the first: a norm equation for β\beta.

  5. ξ≥0  and  ξ∙≥0  ⟺  u∈D  and  u∙∈D\xi\ge0\ \text{ and }\ \xi^\bullet\ge0\iff u\in\mathcal{D}\ \text{ and }\ u^\bullet\in\mathcal{D}

    Here ∙\bullet is the automorphism 2↦−2\sqrt2\mapsto-\sqrt2 fixing ii (so ω∙=−ω\omega^\bullet=-\omega). Both βˉβ\bar\beta\beta and its conjugate β∙‾β∙\overline{\beta^\bullet}\beta^\bullet are ≥0\ge0, so these conditions are necessary.

The algorithm, for increasing kk:

  1. Grid problem. Enumerate α∈Z[ω]\alpha\in\mathbb{Z}[\omega] with α/2 k∈Rε\alpha/\sqrt2^{\,k}\in\mathcal{R}_\varepsilon and (α/2 k)∙∈D(\alpha/\sqrt2^{\,k})^\bullet\in\mathcal{D}. Via α↦(α,α∙)\alpha\mapsto(\alpha,\alpha^\bullet) this is lattice-point enumeration in a product of two convex sets in R4\R^4, one extremely thin and one round; grid operators that straighten the thin set make it efficient.
  2. Norm equation. For each candidate, try to solve βˉβ=ξ\bar\beta\beta = \xi. This is easy when ξ\xi is easy to factor (for instance, prime); other candidates are skipped. With a factoring oracle, none need be skipped.
  3. Exact synthesis. Feed the resulting UU to the descent.
DerivationWhy the T-count comes out near 3 log₂(1/ε)
  1. Λk={(α2k, (α2k)∙):α∈Z[ω]}⊂C2≅R4,covol⁡(Λk)=4⋅4−k\Lambda_k = \Big\{\big(\tfrac{\alpha}{\sqrt2^{k}},\,\big(\tfrac{\alpha}{\sqrt2^{k}}\big)^{\bullet}\big) : \alpha\in\mathbb{Z}[\omega]\Big\}\subset\C^2\cong\R^4,\qquad\operatorname{covol}(\Lambda_k) = 4\cdot4^{-k}

    Embedded by two non-conjugate embeddings, Z[ω]\mathbb{Z}[\omega] is a lattice of covolume 44 (its Minkowski embedding); dividing by 2 k\sqrt2^{\,k} shrinks all four real coordinates by 2−k/22^{-k/2}.

  2. #(Λk∩(Rε×D))≈23ε3⋅π4⋅4−k=π6 4kε3\#\big(\Lambda_k\cap(\mathcal{R}_\varepsilon\times\mathcal{D})\big)\approx\frac{\tfrac23\varepsilon^3\cdot\pi}{4\cdot4^{-k}} = \frac{\pi}{6}\,4^k\varepsilon^3

    Volume over covolume, heuristically.

  3. π6 4kε3≳1  ⟺  k≳32log⁡2(1/ε)\frac{\pi}{6}\,4^k\varepsilon^3\gtrsim1\iff k\gtrsim\tfrac32\log_2(1/\varepsilon)

    Candidates appear once k≈32log⁡2(1/ε)k\approx\tfrac32\log_2(1/\varepsilon). A few more increments of kk supply candidates with an easy norm equation: the source of the O(log⁡log⁡(1/ε))\order{\log\log(1/\varepsilon)} term.

  4. T-count≈sde⁡(∣u∣2)≈2k≈3log⁡2(1/ε)\text{T-count}\approx\operatorname{sde}\big(\abs{u}^2\big)\approx2k\approx3\log_2(1/\varepsilon)

    ∣u∣2=αˉα/2k\abs u^2 = \bar\alpha\alpha/2^k typically has sde⁡=2k\operatorname{sde}=2k. This matches the counting lower bound.

Beyond ancilla-free unitaries

TechniqueIdeaEffect
Euler decompositionU∝RzRxRzU\propto R_z R_x R_z, each rotation synthesized within ε/3\varepsilon/3≈9log⁡2(1/ε)\approx9\log_2(1/\varepsilon) TT gates for a generic UU
Repeat-until-success (Paetznick–Svore 2014; Bocharov–Roetteler–Svore 2015)Ancillas and measurement; on failure apply a known Clifford fix-up and retryLower expected T-count than unitary circuits
Mixing (Campbell 2017; Hastings 2017)Randomly choose among approximations whose coherent errors cancel on averageChannel error O(ε2)\order{\varepsilon^2} from accuracy-ε\varepsilon circuits: roughly half the T-count
Multi-qubit phase-polynomial optimizationRewrite CNOT+TT circuits to minimize odd phase terms (Amy & Mosca 2019)Large savings in arithmetic; no efficient exact algorithm is known in general
Think first Mixing turns coherent synthesis errors of size ε\varepsilon into a channel error of order ε2\varepsilon^2. For a target channel error δ\delta, what typical T-count do you then need?

Accuracy ε≈δ\varepsilon\approx\sqrt\delta per sampled circuit suffices, so about 3log⁡2(1/δ)=1.5log⁡2(1/δ)3\log_2(1/\sqrt\delta) = 1.5\log_2(1/\delta) TT 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[12,i]\mathbb{D}[\omega]=\mathbb{Z}[\tfrac{1}{\sqrt2},i] (one ancilla for nn qubits); Rz(θ)R_z(\theta) is exact only for θ∈π4Z\theta\in\frac\pi4\mathbb{Z}.
  • Exact synthesis is a descent: one HTjHT^j step lowers the smallest denominator exponent by one, so the optimal T-count is sde⁡(∣u00∣2)+O(1)\operatorname{sde}(\abs{u_{00}}^2)+\order{1}.
  • Counting forces about 3log⁡2(1/ε)3\log_2(1/\varepsilon) TT 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 12(1ii1)\tfrac{1}{\sqrt2}\begin{pmatrix}1 & i\\ i & 1\end{pmatrix} is

  1. exactly Clifford+T; in fact it is a Clifford gate
  2. exactly Clifford+T, with T-count 1
  3. not exactly synthesizable, since i/2∉D[ω]i/\sqrt2\notin\mathbb{D}[\omega]
  4. synthesizable only with an ancilla
Show the answer

A. exactly Clifford+T; in fact it is a Clifford gate

Its entries lie in D[ω]\mathbb{D}[\omega], so an exact circuit exists. In fact it is Rx(−π/2)∝HS†HR_x(-\pi/2)\propto HS^\dagger H, with T-count 0.

Question 2

During exact synthesis you find sde⁡(∣u00∣2)=40\operatorname{sde}(\abs{u_{00}}^2) = 40. Roughly what T-count will the optimal circuit have?

  1. About 5
  2. About 40
  3. About 2402^{40}
  4. About 40\sqrt{40}
Show the answer

B. About 40

Each HTHT or SHTSHT syllable changes the sde by one and contains one TT, so the T-count equals the sde up to a small additive constant.

Question 3

Where does the constant 33 in the T-count 3log⁡2(1/ε)3\log_2(1/\varepsilon) come from?

  1. From the three Euler angles of a single-qubit unitary
  2. From the three Pauli matrices
  3. From the dimension of SU(2)SU(2): an ε\varepsilon-net needs ∼ε−3\sim\varepsilon^{-3} points, while T-count tt yields only ∼2t\sim2^t operators
  4. From the order of TT, which is 8=238=2^3
Show the answer

C. From the dimension of SU(2)SU(2): an ε\varepsilon-net needs ∼ε−3\sim\varepsilon^{-3} points, while T-count tt yields only ∼2t\sim2^t operators

2t≳ε−32^t\gtrsim\varepsilon^{-3} gives t≳3log⁡2(1/ε)t\gtrsim3\log_2(1/\varepsilon), and Ross–Selinger's grid algorithm attains it for typical zz-rotations.

Question 4

In Ross–Selinger's algorithm, why must the conjugate u∙u^\bullet also lie in the unit disk?

  1. So that the circuit needs no ancillas
  2. To make the T-count even
  3. Because Rz(θ)R_z(\theta) is diagonal
  4. Because ξ=2k−αˉα\xi = 2^k-\bar\alpha\alpha must be doubly positive (ξ≥0\xi\ge0 and ξ∙≥0\xi^\bullet\ge0) for βˉβ=ξ\bar\beta\beta=\xi to be solvable
Show the answer

D. Because ξ=2k−αˉα\xi = 2^k-\bar\alpha\alpha must be doubly positive (ξ≥0\xi\ge0 and ξ∙≥0\xi^\bullet\ge0) for βˉβ=ξ\bar\beta\beta=\xi to be solvable

βˉβ\bar\beta\beta and its ∙\bullet-conjugate are both squared moduli, hence ≥0\ge0. A solution therefore needs ξ≥0\xi\ge0 (that is, u∈Du\in\mathcal{D}) and ξ∙≥0\xi^\bullet\ge0 (that is, u∙∈Du^\bullet\in\mathcal{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).