5
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – forky40
    Apr 20 '21 at 18:51
  • $\begingroup$ 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. $\endgroup$
    – forky40
    Apr 20 '21 at 18:53
  • $\begingroup$ 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. $\endgroup$
    – Condo
    Apr 20 '21 at 20:36
  • $\begingroup$ Yes, I know, that there infinite count of them. I asked about non-intersecting known! sets... $\endgroup$ Apr 21 '21 at 6:18
7
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.