2.13 A finite set of universal gates

Approximating unitaries

The Hadamard gate and the phase gates, with adjustable phases, allow us to implement an arbitrary single-qubit unitary exactly. The tacit assumption here is that we have infinitely many phase gates: one gate for each phase. In fact, we can pick just one phase gate, namely any phase gate $P_\alpha$ with the phase $\alpha$ that is incommensurate⁶¹ with $\pi$. It is clear that repeated iteration of $P_\alpha$ can be used to approximate any other phase gate to arbitrary accuracy: indeed, rotate the Bloch sphere by $\alpha$ about the $z$-axis sufficiently many times and you end up as close as you please to any other rotation about the $z$-axis.

That is, there do not exist any $m,n\in\mathbb{Z}$ such that $m\alpha=n\pi$. For example, it suffices to take $\alpha$ to be rational, since $\pi$ is irrational.↩︎

If you want to be $\varepsilon$-close to the desired angle of rotation, then you may need to repeat the rotation by $\alpha$ roughly $1/\varepsilon$ times. Indeed, within $n$ applications (for⁶² $n\alpha\gg 2\pi$) of $P_\alpha$, we expect the accessible angles to be approximately evenly distributed within the range $[0,2\pi]$, i.e. any angle of rotation can be achieved to an accuracy of $\varepsilon=2\pi/n$ by using up to $n\approx 1/\varepsilon$ applications of $P_\alpha$. So we can use just one phase gate to approximate the three phase gates in the circuit in Figure 2.3.

The notation $x\gg y$ is rather imprecise, but it basically means “$x$ is much much larger than $y$, and, in particular, large enough for whatever we are claiming to be true”.↩︎

There are other ways of implementing irrational rotations of the Bloch sphere. For example, take the Hadamard gate and the $T$ gate (also known as the $\pi/8$-phase gate, despite being the phase gate $P_\varphi$ for $\varphi=\pi/4$ as we saw earlier in Section 2.6). You can check that the compositions $THTH$ and $HTHT$ represent rotations by angles which are irrational multiples of $\pi$, about two different axes. We can then compose a sequence of these two rotations to approximate any other rotation of the sphere. This may look very nice in theory, but there are issues with the actual physical implementation of this approach: in reality, all the gates in the circuit will operate with only finite precision, and the phase gates will deviate from implementing the required irrational rotations. It turns out, however, that we can tolerate minor imperfections; the final result will not be that far off.

---

61. That is, there do not exist any $m,n\in\mathbb{Z}$ such that $m\alpha=n\pi$. For example, it suffices to take $\alpha$ to be rational, since $\pi$ is irrational.↩︎

62. The notation $x\gg y$ is rather imprecise, but it basically means “$x$ is much much larger than $y$, and, in particular, large enough for whatever we are claiming to be true”.↩︎