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

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.

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).

• One can get an even stronger result using Kliuchnikov, Maslov, and Mosca proven in Giles Selinger. – AHusain Mar 26 '18 at 0:10

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)}$.

• CCNOT+H is universal in a different sense, though: It is computationally universal, but it cannot realize any gate. – Norbert Schuch May 8 '18 at 22:30
• @NorbertSchuch: Is the only problem with CCNOT+H, the fact that it can't realize 2-qubit gates? Isn't that also a problem with the Deutsch gate? If a gate set can simulate any quantum computation with arbitrary $\epsilon>0$, then surely it can simulate any quantum gate with arbitrary $\epsilon>0$? – user1271772 May 8 '18 at 23:37
• Nope. It can't realize any gate with complex (=non-real) coefficients, for obvious reasons. It is computationally universal, i.e. it can run any q. computation, but it does not do so by one-to-one implementing said gates, but some equivalent realization. So if you want to realize unitaries (which seems to be the point of the question), it is not a universal gate set. – Norbert Schuch May 10 '18 at 6:39
• @NorbertSchuch: An example of a quantum computation is simulating a complex unitary. So if CCNOT+H can do any q. computation, can it not get arbitrarily close to simulating any unitary? – user1271772 May 10 '18 at 8:05
• Both CCNOT and H have only real entries. There is NO WAY you will get ANY gate with complex entries. --- More generally, there are (at least) 3 notions of "simulation": Get any unitary, get the measurement statistics of a quantum computer, or solve a BQP problem. CCNOT+H is universal in the 2nd (and 3rd) sense, but not in the first one. – Norbert Schuch May 10 '18 at 13:55