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

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

• For most choices of two qubit entangling gates plus "rotations" you can synthesize a CNOT (SWAP being a notable exception), and so sets like {rotations, sqrt(SWAP)} and {rotations, ISWAP} and so on are also universal. Apr 20, 2021 at 18:51
• Also any gate set containing a universal gate set as a subset is universal, so it might help to constrain what you're asking for. Apr 20, 2021 at 18:53
• A universal quantum gate set (for qubits) is any finite set of elements that generate a dense subset (topologically) of $PU(2)$ (the projective group of $2\times 2$ unitaries). In fact, there is probably an infinite number of them. Apr 20, 2021 at 20:36
• Yes, I know, that there infinite count of them. I asked about non-intersecting known! sets... Apr 21, 2021 at 6:18
• Have a look at this paper. You can find there a criteria for universality journals.aps.org/pra/abstract/10.1103/PhysRevA.105.052602 and arxiv version arxiv.org/abs/2111.03862 Aug 8, 2022 at 11:02

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