Approximating Rotations with Clifford+T

A universal gate set lets us approximate any unitary, but it does not hand us a recipe. Gate synthesis is the algorithmic problem of turning a target rotation into a concrete word over Clifford+$T$. This lesson covers the principle and works a case that comes out exactly, so you can see the machinery before precision and cost enter.

The target: single-qubit rotations

Up to global phase, every single-qubit unitary is a product of rotations about two axes, e.g.

where $R_z(\theta) = e^{-i\theta Z/2} = \mathrm{diag}(e^{-i\theta/2}, e^{i\theta/2})$ and similarly for $R_x$. So synthesizing arbitrary single-qubit gates reduces to synthesizing $z$-rotations; $x$-rotations follow by conjugation with Hadamards, since $H Z H = X$ implies

Exactly-synthesizable angles

The $T$ gate is a $z$-rotation: up to a global phase,

Therefore any rotation by an integer multiple of $\pi/4$ is realizable exactly with $S$, $T$, and $Z$ (and $H$ for the $x$-axis):

The exercise builds one such case on the $x$-axis: $R_x(\pi/4) = H\, T\, H$.

Generic angles: approximation

Most useful angles are not multiples of $\pi/4$ (think of the rotations in quantum phase estimation or chemistry simulation). For these the Clifford+$T$ set cannot hit the target exactly — it is a finite set, so it only reaches a discrete (but dense) collection of rotations. We must settle for an approximation within some operator-norm error $\varepsilon$:

Two results govern the cost:

• Solovay–Kitaev theorem. Any single-qubit unitary can be approximated to error $\varepsilon$ using $O\!\left(\log^{c}(1/\varepsilon)\right)$ gates with $c \approx 3.97$, found by a recursive algorithm. This established that the gate count grows only polylogarithmically in $1/\varepsilon$.

• Optimal $z$-rotation synthesis (Ross–Selinger). For the practically important case of $z$-rotations, number-theoretic algorithms achieve the asymptotically optimal $T$-count

  $$T\text{-count} \approx 3\log_2(1/\varepsilon) + O(\log\log(1/\varepsilon)) ,$$

  and are what modern compilers actually use.

The synthesis workflow

1. Decompose the target unitary into $z$- and $x$-rotations (Euler angles).
2. Turn each $x$-rotation into a Hadamard-conjugated $z$-rotation.
3. For each $z$-rotation, either emit an exact $S/T/Z$ word (if the angle is a multiple of $\pi/4$) or call an $\varepsilon$-approximate synthesizer (Ross–Selinger / Solovay–Kitaev).
4. Concatenate, and optionally optimize the resulting word to reduce $T$-count.

Try it

Synthesize $R_x(\pi/4)$ exactly as the Clifford+$T$ word $H\,T\,H$. The grader compares the resulting unitary (up to global phase) against $R_x(\pi/4)$.

Sign in on the full site to ask questions and join the discussion.