14 Universal set of gates

So far we have seen a wide variety of different quantum gates, depending on the quantum computer architecture. We now look further more into which gates are needed to create arbitrary circuits on a quantum computer.

14.1 Pauli gates as universal qubit gates?

As a warmup recall the Pauli matrices \(X\), \(Y\) and \(Z\). If we only have access to a \(X\) and \(Y\) gate, could we construct the \(Z\) gate from this as well?

We could combine \(Y\) and \(X\) gate, which gives us the gate \[ XY = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} 0 & -i \\ i & 0 \end{pmatrix} = \begin{pmatrix} i & 0 \\ 0 & -i \end{pmatrix} = iZ \]

So we can get the Pauli \(Z\) gate from the \(X\) and \(Y\) gate up to a global phase factor. With simple math, one can show that it is also possible to get a \(X\) gate from \(Y\) and \(Z\) and also the \(Y\) gate from \(X\) and \(Z\).

So with this, we might assume that we can create all gates on a quantum computer only by using two of the Pauli matrices.

Unfortunately this is not true, since we can only manipulate a single qubit using the Pauli matrices. Therefore a e.g. \(\operatorname{CNOT}\) is not possible.

But maybe we can create all single qubit gates from the Pauli matrices? Unfortunately this is also not true, since the product of a Pauli matrix is always either another Pauli matrix or the identity matrix. So we won’t get a universal set of gates from the Pauli matrix and we have to try a different set of gates.

14.2 Rotation gates

We look at a different type of gates, the rotational gates \(R_X\),\(R_Y\) and \(R_Z\). These gates are defined by \[ \begin{aligned} R_X(\theta) &= e^{-i X \theta/2}= \begin{pmatrix} \cos(\theta/2) & -i \sin(\theta/2) \\ -i \sin(\theta/2) & \cos(\theta/2) \end{pmatrix} \\ R_Y(\theta) &= e^{-i Y \theta/2} = \begin{pmatrix} \cos(\theta/2) & -\sin(\theta/2) \\ -\sin(\theta/2) & \cos(\theta/2) \end{pmatrix} \\ R_Z(\theta) &= e^{-i Z \theta/2} =\begin{pmatrix} e^{-i\theta/2} & 0\\ 0 & e^{i\theta/2} \end{pmatrix} \end{aligned} \]

We can obviously not create any multiple qubit gates from this, but is possible to get all single qubit gates from this. We call this universal for single qubit gates.

Definition 14.1 (Universal set of gates) A set \(G\) of gates is universal, iff any unitary can be approximated to an arbitrary precision.

This means that for all unitary \(U \in \mathbb{C}^{n \times n}\), for all \(n\) and for all \(\epsilon\) there exists a circuit \(C\) consisting of elements of \(G\) without auxillary qubits such that for all quantum states \(\psi\) it holds that \(\| U_\psi - C_\psi \| \leq \epsilon\).

We call \(G\) universal for single qubit gates when this holds for \(n=1\).

Using this definition, we can formalize what is stated above:

Theorem 14.1 (Rotation gates) The set \(\{R_X,R_Y,R_Z: \theta \in [0,2\pi]\}\) is universal for single qubit gates.

When adding a \(\operatorname{CNOT}\) to the set of universal single qubit gates, we get a general set of universal gates.

Theorem 14.2 (Single qubit gates and \(\operatorname{CNOT}\)) The set of \(\{\text{all single qubit gates}, \operatorname{CNOT}\}\) is universal.

Corollary 14.1 (Rotation gates and \(\operatorname{CNOT}\)) The set of \(\{R_X,R_Y,R_Z, \operatorname{CNOT}: \theta \in [0,2\pi]\}\) is universal for all \(\theta \in [0,2\pi]\).

14.3 Clifford gates

We look at another set of gates called Clifford gates. This set consists of \(\operatorname{CNOT}\), \(H\) and \(S\).

While there are many gates, which can be construct from the set of Clifford gates, the set is not universal. For example, there is a gate called \(T\), which can not be constructed from Clifford gates. \(T\) is denoted by \[ T = \begin{pmatrix} 1 & 0 \\ 0 & e^{i \pi/4} \end{pmatrix} \] Note that \(T^2=S\) and \(S^2=Z\) and \(Z^2=I\).

But while the Clifford gates are not universal, there is a different useful fact, which we can especially use without access to a quantum computer:

Theorem 14.3 (Gottesmann-Knill theorem) A quantum circuit only using Clifford gates can be efficiently simulated on a classical computer.

However if we add \(T\), we get a universal set:

Theorem 14.4 (Clifford gates and \(T\)) The set of all Clifford gates and \(T\) is universal.

There is also one more example of a universal set:

Theorem 14.5 (Toffoli and \(H\)) The set of \(\{\operatorname{Toffoli}, H\}\) is universal.

14.4 Gottesmann-Knill theorem

We take a closer look into why Theorem 14.3 works.

First we look into stabilizer states. Given a set of unitaries \(M\), \(\psi\) is stabilized by \(M\) if for all \(U\in M\) is holds that \(U\psi=\psi\). The state \(\ket{0}\) is for example stabilized by \(\{Z\}\), since \(Z\ket{0}=\ket{0}\) and it is the only state (up to global phase) stabilized by \(\{Z\}\), since e.g. \(Z\ket{1} = -\ket{1}\).

Let \(P\) be the set of all \(n\)-qubit tensor products of \(X,Y,Z,I\) and a factor \(\pm 1\) and \(\pm i\). For \(n=4\) \(P\) contains for example \(X\otimes I \otimes Z \otimes Z\) and \(-i X \otimes Y \otimes I \otimes I\).

We call \(\psi\) a stabilizer state if there exists a set \(M \subseteq P\) such that \(\psi\) and only \(\psi\) is stabilized by \(M\) up to a global phase.

Example: Stabilizing \(\ket{0}^n\)

The quantum state \(\ket{0}^n = \ket{0} \otimes \dots \otimes \ket{0}\) is stabilized by \(M_0 = \{Z \otimes I \otimes \dots \otimes I, I \otimes Z \otimes \dots \otimes I, I \otimes I \otimes \dots \otimes Z \}\) and therefore the quantum state \(\ket{0}^n\) is a stabilizer state and \(|M_0| = n\).

The big trick is now that if \(\psi\) is stabilized by \(M\), it follows that \(U\psi\) is stabilized by \(M'\) for some \(M'\). But what is \(M'\)?

We know that if \(A\in M\) it holds that \(A\psi = \psi\). So it follows that \(UAU^\dagger = U\psi\) and therefore \(UAU^\dagger\) is a stabilizer of \(U\psi\). The converse also holds. So \(M'=\{UAU^\dagger : A\in M\}\).

Now we can use a useful fact: For any Clifford gate \(G\), if \(M\) contains “Pauli tensors”, then \(M^G\) also contains “Pauli tensors”.

The simulation algorithm to simulate Clifford gates basically works as follows:

\(M:= M_0\), which is the stabilizer for \(\ket{0}^n\).
For each gate \(G\): \[ M:=M^G \]
To calculate the measurement outcomes, do linear algebra (not further specified here).

Since \(M\) will always be a set of \(n\) tensor products of \(n\) Pauli matrices, this gives a polynomial time algorithm for simulation Clifford circuits.