gates
We’ve proved that the CNOT gate along with all possible single-qubit gates
form a universal set. But this set is still infinite. We’d like to do better: to
get a finite set of gates as in the classical case. Of course we must realize that
the set of possible single qubit gates is itself infinite as opposed to the finite
number of gates in classical computation. Yet it is surprising that there exist
more rigorous theorems (e.g., the Solovay–Kitaev Theorem [23]) confirming
the universality of a smaller set of gates, such as for example, H, CNOT,
S =
“
1 0
0 i
#
and T =
“
1 0
0 e
iπ/4
#
or the Toffoli and H gates. But these sets of
gates cannot be used to construct arbitrary gates to infinite precision. So the
theorems actually prove that one can approximate arbitrary unitary gates, to
any degree of accuracy, by using a finite set of gates. We will not dwell on
these theorems or their proofs here.
Leave a Reply