5.11 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.118 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.

  1. Recall the big-\mathcal{O} asymptotic notation introduced in Exercise 1.11.7: given a positive function f(n), we write \mathcal{O}(f(n)) to mean “bounded above by c\,f(n) for some constant c > 0 (for sufficiently large n)”. For example, 15n^2+4n+7 is \mathcal{O}(n^2).↩︎