A universal set of gates are able to mimic the operation of any other gate type, given enough gates. For example, a universal set of quantum gates are the Hadamard ( $H$ ), the $\pi/8$ phase shift ( $T$ ), and the $\mathrm{CNOT}$ gate. How would one disprove or prove universality of a set of gates such as $\{H,T\}$, $\{\mathrm{CNOT},T\}$, or $\{\mathrm{CNOT}, H\}$?
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
1
Universality can be a very subtle thing which is quite tricky to prove. There are usually two options for proving it:
show directly, using your chosen gates, how to construct any arbitrary unitary of arbitrary size (there’s no constraint on the size of the construction, just that it can be done) to arbitrary accuracy (on some non-trivial sub space of the full Hilbert space).
show how your chosen set of gates can be used to recreate (to arbitrary accuracy) an existing universal set.
Conversely, if you wish to disprove it, you show that the effect of your set of gates can always be simulated by an (assumed) lesser model of computation, usually classical computation.
There are a few heuristics that you can use for guidance:
you must have a multi-qubit gate in your set. If all you have are single-qubit gates, you can simulate each qubit independently on a classical computer. So, if we believe that quantum computers are more powerful than classical, single qubit gates alone are not universal for quantum computation. This rules out {H,T}.
you must have a gate that creates superpositions. This rules out {CNOT, T}. Again, this is a classical computation with the addition of an irrelevant global phase.
Of course, these are not sufficient conditions: the set {H,S,CNOT} can be efficiently simulated as well (see Gottesman-Knill theorem). This must also be true of {H,CNOT} as they are a subset and so the operations that they can create is no more than those of the original set.
One of the universal sets that I find most interesting is {Toffoli,H}. It always feels surprising to me that this is enough (especially when you compare to the previous set). Note that it does not involve any complex numbers.
It is also possible to get universality from a single two-qubit gate such as $$ \left(\begin{array}{cccc} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & \frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{2}} \\ 0 & 0 & \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \end{array}\right) $$
answered Jun 30, 2018 at 5:41
-
$\begingroup$ Just pointing out that a lot of folks are used to thinking of universal as "can approximate any unitary with arbitrary accuracy." {Toffoli, H} fails to be universal in that sense because it can only approximate real gates. While the ability to approximate any unitary is sufficient for computational universality it is not necessary. And {Toffoli, H} shows exactly that. This is for example discussed in the wonderful comments by Norbert Schuch here quantumcomputing.stackexchange.com/questions/1285/… $\endgroup$ Commented Mar 6, 2022 at 14:26
$\begingroup$
$\endgroup$
0
Nielsen and Chuang, pg 191 of the 10th anniversary edition:
We have just shown that an arbitrary unitary matrix on a $d$-dimensional Hilbert space may be written as a product of two-level unitary matrices. Now we show that single qubit and CNOT gates together can be used to implement an arbitrary two-level unitary operation on the state space of $n$ qubits. Combining these results we see that single qubit and CNOT gates can be used to implement an arbitrary unitary operation on $n$ qubits and therefore are universal for quantum computation.
The first sentence there is an accepted result, so you must simply show that the combination of your gate set can implement "an arbitrary two-level unitary operation". To quote Wikipedia:
Technically, this is impossible since the number of possible quantum gates is uncountable, whereas the number of finite sequences from a finite set is countable. To solve this problem, we only require that any quantum operation can be approximated by a sequence of gates from this finite set.
See also this paper.
