Does anyone know the list of all known universal sets of quantum gates?

Question

Does anyone know the list of all known universal sets of quantum gates? I know only two such sets: Cliffords + $T$ and rotations + CNOT.

Answer 1

Too many to list

There exist uncountably many universal sets of gates. We will sketch a proof of this fact by outlining a construction of an uncountable, though by no means exhaustive, family of such sets.

First, recall (e.g. from sections 4.5.2 and 4.5.3 of Nielsen & Chuang) that if $\mathcal{A}$ is a set of single-qubit gates that is universal for $SU(2)$, i.e. that generates a set dense in $SU(2)$, then $\mathcal{A}\cup\{CNOT\}$ is universal. Therefore, it suffices to exhibit an uncountable family of sets of single-qubit gates universal for $SU(2)$.

For any irrational number $a$ in the interval $(-2, 2)$ and any two distinct unit vectors $\hat{n}$ and $\hat{m}$ in $\mathbb{R}^3$, let $\mathcal{A}(a,\hat{n},\hat{m})$ consist of just two gates

$$ \mathcal{A}(a,\hat{n},\hat{m}) = \{R_{\hat{n}}(a\pi), R_{\hat{m}}(a\pi)\}. $$

Note that since $a$ is irrational, $R_{\hat{n}}(a\pi)$ generates a set dense in the set of all rotations around $\hat{n}$. Similarly, $R_{\hat{m}}(a\pi)$ generates a set dense in the set of all rotations around $\hat{m}$. Now, $SU(2)$ is three dimensional and does not have any two dimensional subgroups, so rotations around $\hat{n}$ and $\hat{m}$ generate the entire $SU(2)$. In other words, any $U\in SU(2)$ can be written as

$$ U = R_{\hat{n}}(\theta_1)R_{\hat{m}}(\phi_2) R_{\hat{n}}(\theta_3) \dots R_{\hat{n}}(\phi_k)\tag1 $$

for some positive integer $k$ (Caution: In exercise 4.11 on page 176 in Nielsen & Chuang it is incorrectly stated that $k=3$ always). By approximating the factors in $(1)$ using elements of $\mathcal{A}(a,\hat{n},\hat{m})$ we can approximate $U$ arbitrarily well.

Finally, there are uncountably many irrational numbers in the interval $(-2, 2)$ and uncountably many different pairs of distinct unit vectors in $\mathbb{R}^3$. Therefore, there are uncountably many different universal sets $\mathcal{A}(a,\hat{n},\hat{m})\cup\{CNOT\}$. $\square$

Technically speaking, only countable collections can be put into a list, so by the arguments above a complete list of universal sets of gates does not exist.

Notable universal sets of gates

That said, there are a few notable examples of universal sets of gates:

• any set of generators of the Clifford group, such as $\{H, S, CNOT\}$, together with a non-Clifford gate, such as $T$ gate or the Toffoli gate,
• Deutsch's gate, i.e. controlled-controlled-$iR_x(a\pi)$, is universal whenever $a$ is irrational, see exercise 4.44 on page 198 in Nielsen & Chuang,
• $\sqrt{X}$, $\sqrt{W}$ and the two-qubit $\text{fSim}$ gate, see sections VII E and VII F in this paper (disclosure: I'm a co-author).

See also this question for other interesting universal sets of gates.