What is the mathematical justification for the "universality" of the universal set of quantum gates (CNOT, H, Z, X and π/8)?

Question

In this answer I mentioned that the CNOT, H, X, Z and $\pi/8$ gates form a universal set of gates, which given in sufficient number of gates can get arbitrarily close to replicating any unitary quantum gate (I came to know about this fact from Professor Umesh Vazirani's EdX lectures). But, is there any mathematical justification for this? There should be! I tried searching for relevant papers but couldn't find much.

Answer 1

The answer you mention references Michael Nielsen and Isaac Chuang's book, Quantum Computation and Quantum Information (Cambridge University Press), which does contain a proof of the universality of these gates. (In my 2000 edition, this can be found on p. 194.) The key insight is that the $T$ gate (or $\pi/8$ gate), together with the $H$ gate, generates two different rotations on the Bloch sphere with angles that are irrational multiples of $2\pi$. This allows combinations of $T$ and $H$ gates to densely fill the surface of the Bloch sphere and thereby approximate any one-qubit unitary operator.

That this can be done efficiently is shown by the Solovay-Kitaev theorem. Here, "efficiently" means polynomial in $\log(1/\epsilon)$, where $\epsilon$ is the desired accuracy. This is also proven in Nielsen and Chuang's book (Appendix 3 in the 2000 edition). An explicit construction can be found in https://arxiv.org/abs/quant-ph/0505030.

Combining CNOT gates allows one to approximate arbitrary multi-qubit unitaries, as shown by Barenco et al. in Phys. Rev. A 52 3457 (1995). (A preprint of this paper can be found at https://arxiv.org/abs/quant-ph/9503016.) This is also discussed in Nielsen and Chuang (p. 191 in the 2000 edition).

Answer 2

You do not even need $Z$ and $X$.
$\rm{CNOT}$, $H$, and $T=\pi/8$ are enough.

1. $H$ and $T$ are enough to make any possible unitary transformation on one qubit.
   
2. Adding $\rm{CNOT}$, you can synthesize a general unitary transformation to within any error $\epsilon>0$ using only $\mathcal{O}(\log^2(1/\epsilon))$ gates.

If you wish for the error to be $\epsilon=0$ and you are only willing to add the phase gate $\pi/2$, it is still possible, if and only if the elements of the unitary you want to make are of the form: $\frac{a+ib}{2^n} + \frac{c+id}{2^{n+1/2}}$, where all variables are integers. Remarkably, at most 1 auxiliary qubit is required for this exact synthesis.

Another universal gate set is $\{{\rm{CCNOT}},H\}$, and in fact there's a single gate that's uniersal: the 3-qubit Deutsch gate ${D(\theta)}$.