2.12 A finite set of universal gates

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 here 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 incommensurate43 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.

If you want to be \epsilon-close to the desired angle of rotation, then you may need to repeat the rotation by \alpha roughly 1/\epsilon 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 \epsilon=2\pi/n by using up to n\approx 1/\epsilon applications of P_\alpha. So we can use just one phase gate to approximate the three phase gates in the circuit in Figure 2.2.

There are other ways of implementing irrational rotations of the Bloch sphere. For example, take the Hadamard gate and the T gate. 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. All the gates in the circuit will operate with 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.

For more details on all the above, see Chapter 3.

  1. 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.↩︎