# 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.

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

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

## 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:

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

There is also one more example of a universal set:

## 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.

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.