16 Universal set of gates

We have seen that various gates are possible with an ion-based quantum computer. For other architectures, other gates may be possible. At this point, the question arises: Which set of gates are necessary to generate all possible gates. Such a set is referred to as universal set of gates.

Formally, this means:

Definition 16.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 \(n\), for all unitaries \(U \in \mathbb{C}^{2^n \times 2^n}\) and for all \(\epsilon\) there exists a circuit \(C\) consisting of elements of \(G\) without auxiliary qubits such that for all quantum states \(\psi\) it holds that \(\| U\psi - C\psi \| \leq \epsilon\).

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

16.1 Pauli gates

We recall the Pauli matrices \(X\), \(Y\) and \(Z\) (see Definition 7.2). If we only have access to the \(X\) and \(Y\) gates, can we construct the \(Z\) gate from them?

We can combine the \(Y\) and \(X\) gates, 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 \(Z\) gate from the \(X\) and \(Y\) gate up to a global phase factor. With some simple math, one can also show that it is possible to get a \(X\) gate (up to a global phase factor) from \(Y\) and \(Z\), and a \(Y\) gate (up to a global phase factor) 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. So they cannot be used to create entanglement. For example, the \(\operatorname{CNOT}\) gate can create entanglement, and therefore it cannot be constructed using only Pauli gates.

But maybe it is possible to create all single-qubit gates from the Pauli matrices. Unfortunately, this is also not true. The product of a Pauli matrix is always either another Pauli matrix (up to a global phase factor) or the identity matrix.

In conclusion, we cannot get a universal set of gates nor even a universal set for single-qubit gates from the Pauli matrices. We must therefore consider a different set of gates.

16.2 Other known gates

We also know the gates \(\operatorname{CNOT}\), \(\operatorname{Toffoli}\) (i.e. \(\operatorname{CNOT}\) with two control wires), \(\operatorname{X}\) and \(\operatorname{SWAP}\). These gates are sufficient for constructing \(U_f\).

Are these gates a universal set of gates?

The answers is also no. Each of those gates \(G\) performs an operation of the form: \[ G \ket{x} = \ket{\text{something}}, \] where \(\ket{\text{something}}\) is another computational basis state (ket-state).

This means that any combination of these gates can only map one computational basis state to another. Therefore, they cannot create superposition or arbitrary quantum states, which are essential. As such, these gates are not sufficient to form a universal set of gates.

Note that any combination of those gates computes \(\ket{x} \rightarrow \ket{f(x)}\) for some classically easy to compute \(f\). Therefore these gates also provides no quantum speedup.

16.3 Rotation gates

We look at a different type of gates: The rotational gates \(R_X\),\(R_Y\) and \(R_Z\). These are defined as: \[ \begin{aligned} R_X(\theta) & \coloneqq 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) & \coloneqq e^{-i Y \theta/2} = \begin{pmatrix} \cos(\theta/2) & -\sin(\theta/2) \\ -\sin(\theta/2) & \cos(\theta/2) \end{pmatrix}, \\ R_Z(\theta) & \coloneqq e^{-i Z \theta/2} =\begin{pmatrix} e^{-i\theta/2} & 0\\ 0 & e^{i\theta/2} \end{pmatrix}. \end{aligned} \]

These represent infinitely many gates. They are also very natural on physical quantum computers. For example, \(R_X(\theta)\) corresponds to applying the \(\operatorname{X}\) gate for the time \(\theta\). Analogous holds for \(R_Y(\theta)\) and \(R_Z(\theta)\).

It turns out that any single-qubit gate can be decomposed into these rotational gates. However, the construction of an arbitrary multiple qubit gate from this is not possible. This leads to the following result:

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

Furthermore, the following holds:

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

Combining bot theorems, we obtain the following corollary.

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

Also only two of the three rotational gates are enough for a universal set of gates.

16.4 Clifford gates

We look at another set of gates called Clifford gates. This set consists of \(\operatorname{CNOT}\), the Hadamard gate \(H\) and \(S\), which is defined as: \[ S \coloneqq \sqrt{Z} = \begin{pmatrix} 1 & 0 \\ 0 & i \end{pmatrix}. \]

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

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

Theorem 16.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 obtain a universal set of gates:

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

There exists also another example of a universal set of gates:

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

16.5 Gottesmann-Knill theorem

We take a closer look at why Theorem 16.3 works. For this, we need two definitions:

Definition 16.2 (Stabilizing) Given a set \(M\) of unitaries, the state \(\psi\) is stabilized by \(M\) iff \(\forall U \in M : U\psi = \psi\).

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

The quantum state \(\ket{0}\) is stabilized by the set \(M = \{Z\}\), because \(Z\ket{0} = \ket{0}\).

The state \(\ket{1}\) is not stabilized by the set \(M\), because \(Z \ket{1} = -\ket{1}\).

The only states stabilized by \(M\) are \(c \cdot \ket{0}\) for \(c \in \mathbb{C}\). So \(\ket{0}\) is uniquely stabilized by \(M\) (up to a global phase factor).

Let \(Pauli\) be the set of all \(n\)-qubit tensor products of \(X, Y, Z, I\) and the factors \(\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\). With this we can define a stabilizer state:

Definition 16.3 (Stabilizer state) We call \(\psi\) a stabilizer state iff \(\exists M \subseteq Pauli\) such that \(\psi\), and only \(\psi\) (up to a global phase factor), is stabilized by \(M\).

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

The quantum state \(\ket{0}^n = \ket{0} \otimes \dots \otimes \ket{0}\) is uniquely 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 \}\).

Therefore the quantum state \(\ket{0}^n\) is a stabilizer state and \(|M_0| = n\).

The notation \(\psi \sim M\) means that \(\psi\) is uniquely stabilized by \(M\).

The big trick is now that if \(\psi \sim M\), it follows that \(U \psi \sim M^U \coloneqq \{UVU^\dagger : V \in M\}\). This follows from \[ UVU^\dagger U \psi = UV \psi = U \psi. \]

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

To prove the Gottesmann-Knill theorem (Theorem 16.3) we want to simulate the result of applying a sequence \(G_1, G_2, \dots, G_l\) of Clifford gates to \(\ket{0}^n\) and measure the the resulting state. This simulation algorithm works as follows:

Set \(M_0 \coloneqq \{Z \otimes I \otimes \dots \otimes I, I \otimes Z \otimes \dots \otimes I, \dots, I \otimes I \otimes \dots \otimes Z \}\). (This is the stabilizer of the state \(\ket{0}^{\otimes n}\).)
For each \(i \in \{1, 2, \dots, l\}\) set \(M_i \coloneqq M_{i-1}^{G_i}\). (\(M_i\) is the stabilizer of the state after applying \(G_i\).)
To calculate the measurement outcomes, do linear algebra (not further specified here).

Since \(M_i\) will always be a set of \(n\) tensor products of \(n\) Pauli matrices, this gives a polynomial time algorithm for simulating Clifford circuits. Additionally, we can simulate a measurement of the final state (details omitted). So Clifford gates alone do not give a quantum speedup.