Universality, revisited
We will come across few more gates in this course, but at this stage you already know all the elementary unitary operations that are needed to construct any unitary operation on any number of qubits:
- the Hadamard gate,
- all phase gates, and
- the \texttt{c-NOT}
These gates form a universal set of gates: with \mathcal{O}(4^{n}n) of these gates, we can construct any n-qubit unitary operation.
We should mention that there are many different universal sets of gates.
In fact, almost any gate that can entangle two qubits can be used as a universal gate.
We are particularly interested in any finite universal set of gates (such as the one containing the Hadamard, P_{\frac{\pi}{4}} (the T gate), and the \texttt{c-NOT}) that can approximate any unitary operation on n qubits with arbitrary precision.
The price to pay is the number of gates — better precision requires more gates.