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.
$\begingroup$
$\endgroup$
0
user1271772 No more free time
14.2k2 gold badges26 silver badges75 bronze badges
asked Mar 23, 2018 at 19:56
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
3
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).
-
1$\begingroup$ One can get an even stronger result using Kliuchnikov, Maslov, and Mosca proven in Giles Selinger. $\endgroup$– AHusainCommented Mar 26, 2018 at 0:10
-
$\begingroup$ I was just looking at Nielsen and Chuang's proof, and I think they're missing a key point: how do you get CNOT gates that are controlled an arbitrary number of times? (So, CNOT, Toffoli, and then continuing.) If you allow ancillary bits, this can be done classically, and Nilesen and Chuang explain how around p. 184, but without ancillary bits it cannot be done classically. Kitaev, Shen, and Vyalyi give the construction in Section 8.1.2, but it seems to be entirely missing in Nielsen and Chuang. $\endgroup$ Commented Sep 3, 2021 at 13:01
-
$\begingroup$ The construction on p. 180 ff. of Nielsen and Chuang (2000 ed.) can be applied recursively, so no ancilla are needed. $\endgroup$ Commented Sep 4, 2021 at 14:59
$\begingroup$
$\endgroup$
7
You do not even need $Z$ and $X$.
$\rm{CNOT}$, $H$, and $T=\pi/8$ are enough.
- $H$ and $T$ are enough to make any possible unitary transformation on one qubit.
- 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)}$.
answered May 8, 2018 at 20:46
user1271772 No more free timeuser1271772 No more free time
14.2k2 gold badges26 silver badges75 bronze badges
-
5$\begingroup$ CCNOT+H is universal in a different sense, though: It is computationally universal, but it cannot realize any gate. $\endgroup$ Commented May 8, 2018 at 22:30
-
$\begingroup$ @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$? $\endgroup$ Commented May 8, 2018 at 23:37
-
3$\begingroup$ 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. $\endgroup$ Commented May 10, 2018 at 6:39
-
6$\begingroup$ 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. $\endgroup$ Commented May 10, 2018 at 13:55
-
1$\begingroup$ @user1936752 Puh ... There's some notions like "strong" and "weak" simulation. But I'm not sure if there is a standard usage. Note that there is a stronger classical notion as well, namely compute probabilities of outcomes: Sufficient but not necessarily necessary for sampling. $\endgroup$ Commented Mar 24 at 22:48