<p><del>I'm not aware of any proof that the Clifford group + any non-Clifford element gives a universal set of quantum gates. The closest related result that I know is that the Clifford group + any non-Clifford element densely generates an infinite group. (This is theorem 6.5 of Nebe et al. <a href="http://arxiv.org/abs/math/0001038v2" rel="nofollow noreferrer">http://arxiv.org/abs/math/0001038v2</a>). But this falls short of proving that the Clifford group + any non-Clifford element is universal, because it is possible you could densely generate a continuous group on $n$ qubits that is not all of $U(2^n)$. So I believe that proving this result remains open. 
Note that in the case of the Clifford group on qubits, one can easily show that the Clifford group + any non-Clifford <strong>one-qubit</strong> gate is universal, using the representation theory of $SU(2)$. But the more general statement about adding arbitrary elements to the Clifford group is open.</del></p>

<p><strong>Update</strong>: The answer to the first problem is known. In particular, the statement that the Clifford group + any non-Clifford element yields a universal gate set follows from two theorems of Nebe, Rains and Sloane. First, Theorem 6.5 of Nebe et al (<a href="http://arxiv.org/abs/math/0001038v2" rel="nofollow noreferrer">http://arxiv.org/abs/math/0001038v2</a>) shows that adding any element to the Clifford group renders it infinite. Second, Corollary 6.8.2 of Nebe et al. (Self-Dual Codes and Invariant Theory (Springer 2006)) states that any infinite group which contains the Clifford group contains all of $SU(d^n)$. Combining these shows that the Clifford group + any non-Clifford element is universal, in any local dimension $d$ (prime or composite). This was previously discussed on stackexchange here: <a href="https://cstheory.stackexchange.com/questions/11308/universal-sets-of-gates-for-su3?rq=1">Universal sets of gates for SU(3)?</a></p>

<p>With regards to rotations by irrational multiples of pi: it's not necessary for your gate set to contain a rotation by an irrational multiple of pi to be universal - for example the gate set $CNOT, H,T$ is universal where $T$ is a Z-rotation by $\pi/8$. All that's required for universality is that the gate set densely generates all rotations. A priori it's possible that even as you take longer and longer products of your gate elements, all the resulting rotations are by rational multiples of pi, but the gate is still universal as the rational rotations are dense in the reals.  So I don't believe one can argue that "the gate added to the Clifford group must generate an irrational rotation to be universal". We only know that "the gate added to the Clifford group must <em>densely</em> generate and irrational rotation to be universal". </p>

CC BY-SA 3.0
2016-05-11T22:19:03.763Z
Hi Adam, thanks for the answer. I found that the proof of the theorem has been discussed in the appendix D of PhysRevX.2.041021. Also, rotation by irrational multiple of pi can be done using T gate in the manner discussed in Boykin et al. / Information Processing Letters 75 (2000) 101–107).
user25957
CC BY-SA 3.0
2016-05-11T22:25:55.483Z
I do believe that "the gate added to the Clifford group must generate an irrational rotation to be universal" may not be true but could you give a counter-example where the converse doesn't work/do you have an example where you add an irrational rotation to the Clifford group and don't get universality ?
user25957
CC BY-SA 3.0
2016-05-11T22:27:13.547Z
Thanks for the reference. In Boykin et al. It seems all they're using is the fact that the Clifford group for qubits + any non-Clifford one-qubit gate is universal (this is described in section 3 of their paper).  I didn't see the statement about adding generic non-Clifford elements - let me know if I'm missing something!
Adam Bouland
CC BY-SA 3.0
2016-05-11T22:28:54.900Z
I agree the statement "the gate added to the Clifford group must generate an irrational rotation to be universal" could be true - but I don't know how to prove it, nor do I know of a counterexample.
Adam Bouland
CC BY-SA 3.0
2016-05-11T22:30:07.683Z
Hey, I mentioned that reference for rotation by irrational multiple of pi. The proof for the theorem is mentioned in appendix D of PhysRevX.2.041021
user25957
CC BY-SA 3.0
2016-05-11T22:30:12.883Z
For the converse, if I had to guess I'd guess that adding any irrational rotation to the Clifford group actually **does** generate all unitaries. I just don't know of any proof of this fact.
Adam Bouland
CC BY-SA 3.0
2016-05-12T15:20:24.687Z
Thanks! You're correct that the theorem about adding non-Clifford elements holds for prime dimension d. The proof in the PRX reference combines the Nebe et al. reference I gave above, which says the Clifford group is a maximal finite group in any prime dimension d, plus Corollary 6.8.2 of Nebe,  Rains, and Sloane, Self-Dual Codes and Invariant Theory (Springer 2006), which shows that any infinite group which contains the Clifford group is all of SU(2^n). So by this theorem, it is known that adding any rotation by an irrational multiple of pi to the Clifford group boosts it to universality.
Adam Bouland
CC BY-SA 3.0
2016-05-12T15:21:02.817Z
Therefore I believe the above reference resolves the second part of your question, about whether adding any irrational rotation to the Clifford group boosts it to universality for composite d.
Adam Bouland
CC BY-SA 3.0
2016-05-12T15:43:29.163Z
Thanks. You are right, that resolves the 2nd part. Seems like I cannot upvote your comments because of my rating. I guess now the only question left is whether having a non-Clifford gate provides the rotation by irrational multiple of pi.
user25957
CC BY-SA 3.0
2016-05-12T17:43:46.393Z
Actually an even stronger statement is known for the second part, because I believe the quantum clifford group is actually the "complex" Clifford group $\chi_m$ described in the Nebe et al. references, not the "real" clifford group $C_m$. In that case, Theorem 6.5 of Nebe et. al 2000 tells you that that Complex Clifford group is a maximal subgroup of the unitaries for any d (prime or composite). So therefore, combining this with Corollary 6.8.2 of Nebe et al. 2006, you get that adding any non-Clifford element to any Clifford group (prime or composite) boosts you to universality.
Adam Bouland
CC BY-SA 3.0
2016-05-12T17:48:04.277Z
(It seems the PRX reference was using theorem 7.3 of Nebe et al (2000) which is the same statement for the real Clifford group and which only applies to prime d. So if I'm correct that the quantum Clifford group is actually the complex Clifford group $\chi_m$, then that implies the PRX reference was using the wrong theorem. It seems this should be the case, because the real Clifford group is defined as the stabilizer of the real Pauli group in the orthogonal matrices (see definition 2.1 of Nebe et al 2000), which is smaller than the complex quantum Clifford group.)
Adam Bouland
CC BY-SA 3.0
2016-05-12T22:21:38.237Z
Thanks for pointing that out. You might be right that the statement for universality using Clifford gates and one non-Clifford gate holds for any dimension d. I guess I am curious whether one necessarily needs a rotation by an irrational multiple of pi in order to be dense in SU(d) and whether there exists a proof proving or contradicting such a statement.
user25957
CC BY-SA 3.0
2016-05-12T22:21:45.097Z
Let us [continue this discussion in chat](http://chat.stackexchange.com/rooms/39704/discussion-between-user25957-and-adam-bouland).
user25957
CC BY-SA 4.0
2022-06-21T11:09:17.570Z
This is an interesting answer with great references (note that the references only address the case that $ d $ is prime) so I upvoted it. But I do want to clarify that your claim for composite $ d $ is false. For $ d $ composite, it is not true that adding any non Clifford gate to the Clifford group in $ SU(d^n) $ will generate a universal subgroup.
Ian Gershon Teixeira
CC BY-SA 3.0
2016-05-11T22:13:02.720Z
2016-05-13T17:06:14.307Z
2017-04-13T12:32:28.743Z
Adam Bouland
<p>It seems that there is a theorem that for prime dimension d, the set of Clifford gates and one non-Clifford gate together forms a universal set of quantum gates for SU(d). It also seems that for a universal set of gates, there is a requirement of a gate using which can provide non-trivial rotation by an irrational multiple of Pi. Does this imply that using any non-Clifford gate for prime d, one can construct such a gate ? Also, it probably does not follow directly that the non-Clifford gate used to get such a non-trivial rotation itself has irrational eigenvalues but it seems that is usually the case- for example, the qubit T gate and qudit versions of it. </p>

<p>Is there any similar theorem as mentioned above, for composite d ? It seems that if one finds a gate using which one can construct a non-trivial rotation by an irrational multiple of Pi, that should be enough to have universal set of gates even for composite d. Is it obvious that such a gate has to be non-Clifford ?</p>

CC BY-SA 3.0
2016-05-10T15:40:27.617Z
Irrational multiple of pi rotation is a sufficient condition (allow to approximate any angle), not a requirement. Except if you mean that an irrational angle should be easily approximated (otherwise the set is obviously non-universal)
Frédéric Grosshans
CC BY-SA 3.0
2016-05-10T21:37:27.817Z
I think my theorem was not written precisely and probably that's the reason for your comment. According to the theorem, Clifford gates and a Non-Clifford gate give the universal set of gates. I think this is not just approximate universal in the sense that it can be actually used to give a rotation which is an irrational multiple of pi, just like the T gate.
user25957
CC BY-SA 3.0
2016-05-11T06:11:57.823Z
You cannot have exactly all irrational rotations with a discrete set of gates: the number of combinations is countable while the number of irrational angles is uncountable. A set is universal is the set of operations you can prepare is dense in the total set of operations, i.e. you can approximate any gate
Frédéric Grosshans
<quantum-computing><quantum-information><universal-computation>
theorems for universal set of quantum gates for SU(d)
user25957
# theorems for universal set of quantum gates for SU(d)

(Asked by: username_0 on 2016-05-09)

It seems that there is a theorem that for prime dimension d, the set of Clifford gates and one non-Clifford gate together forms a universal set of quantum gates for SU(d). It also seems that for a universal set of gates, there is a requirement of a gate using which can provide non-trivial rotation by an irrational multiple of Pi. Does this imply that using any non-Clifford gate for prime d, one can construct such a gate ? Also, it probably does not follow directly that the non-Clifford gate used to get such a non-trivial rotation itself has irrational eigenvalues but it seems that is usually the case- for example, the qubit T gate and qudit versions of it.

Is there any similar theorem as mentioned above, for composite d ? It seems that if one finds a gate using which one can construct a non-trivial rotation by an irrational multiple of Pi, that should be enough to have universal set of gates even for composite d. Is it obvious that such a gate has to be non-Clifford ?

**Tags:** quantum-computing, quantum-information, universal-computation

> **Comments:**
> **username_1**: Irrational multiple of pi rotation is a sufficient condition (allow to approximate any angle), not a requirement. Except if you mean that an irrational angle should be easily approximated (otherwise the set is obviously non-universal)  
> **username_0**: I think my theorem was not written precisely and probably that's the reason for your comment. According to the theorem, Clifford gates and a Non-Clifford gate give the universal set of gates. I think this is not just approximate universal in the sense that it can be actually used to give a rotation which is an irrational multiple of pi, just like the T gate.  
> **username_1**: You cannot have exactly all irrational rotations with a discrete set of gates: the number of combinations is countable while the number of irrational angles is uncountable. A set is universal is the set of operations you can prepare is dense in the total set of operations, i.e. you can approximate any gate  

---

## 1 answers

### Answer by username_2 on 2016-05-11. Score: 8 | Accepted answer

~~I'm not aware of any proof that the Clifford group + any non-Clifford element gives a universal set of quantum gates. The closest related result that I know is that the Clifford group + any non-Clifford element densely generates an infinite group. (This is theorem 6.5 of Nebe et al. <http://arxiv.org/abs/math/0001038v2>). But this falls short of proving that the Clifford group + any non-Clifford element is universal, because it is possible you could densely generate a continuous group on $n$ qubits that is not all of $U(2^n)$. So I believe that proving this result remains open.
Note that in the case of the Clifford group on qubits, one can easily show that the Clifford group + any non-Clifford **one-qubit** gate is universal, using the representation theory of $SU(2)$. But the more general statement about adding arbitrary elements to the Clifford group is open.~~

**Update**: The answer to the first problem is known. In particular, the statement that the Clifford group + any non-Clifford element yields a universal gate set follows from two theorems of Nebe, Rains and Sloane. First, Theorem 6.5 of Nebe et al (<http://arxiv.org/abs/math/0001038v2>) shows that adding any element to the Clifford group renders it infinite. Second, Corollary 6.8.2 of Nebe et al. (Self-Dual Codes and Invariant Theory (Springer 2006)) states that any infinite group which contains the Clifford group contains all of $SU(d^n)$. Combining these shows that the Clifford group + any non-Clifford element is universal, in any local dimension $d$ (prime or composite). This was previously discussed on stackexchange here: [Universal sets of gates for SU(3)?](https://cstheory.stackexchange.com/questions/11308/universal-sets-of-gates-for-su3?rq=1)

With regards to rotations by irrational multiples of pi: it's not necessary for your gate set to contain a rotation by an irrational multiple of pi to be universal - for example the gate set $CNOT, H,T$ is universal where $T$ is a Z-rotation by $\pi/8$. All that's required for universality is that the gate set densely generates all rotations. A priori it's possible that even as you take longer and longer products of your gate elements, all the resulting rotations are by rational multiples of pi, but the gate is still universal as the rational rotations are dense in the reals. So I don't believe one can argue that "the gate added to the Clifford group must generate an irrational rotation to be universal". We only know that "the gate added to the Clifford group must *densely* generate and irrational rotation to be universal".

> **Comments:**
> **username_0**: Hi Adam, thanks for the answer. I found that the proof of the theorem has been discussed in the appendix D of PhysRevX.2.041021. Also, rotation by irrational multiple of pi can be done using T gate in the manner discussed in Boykin et al. / Information Processing Letters 75 (2000) 101–107).  
> **username_0**: I do believe that "the gate added to the Clifford group must generate an irrational rotation to be universal" may not be true but could you give a counter-example where the converse doesn't work/do you have an example where you add an irrational rotation to the Clifford group and don't get universality ?  
> **username_2**: Thanks for the reference. In Boykin et al. It seems all they're using is the fact that the Clifford group for qubits + any non-Clifford one-qubit gate is universal (this is described in section 3 of their paper).  I didn't see the statement about adding generic non-Clifford elements - let me know if I'm missing something!  
> **username_2**: I agree the statement "the gate added to the Clifford group must generate an irrational rotation to be universal" could be true - but I don't know how to prove it, nor do I know of a counterexample.  
> **username_0**: Hey, I mentioned that reference for rotation by irrational multiple of pi. The proof for the theorem is mentioned in appendix D of PhysRevX.2.041021  
> **username_2**: For the converse, if I had to guess I'd guess that adding any irrational rotation to the Clifford group actually **does** generate all unitaries. I just don't know of any proof of this fact.  
> **username_2**: Thanks! You're correct that the theorem about adding non-Clifford elements holds for prime dimension d. The proof in the PRX reference combines the Nebe et al. reference I gave above, which says the Clifford group is a maximal finite group in any prime dimension d, plus Corollary 6.8.2 of Nebe,  Rains, and Sloane, Self-Dual Codes and Invariant Theory (Springer 2006), which shows that any infinite group which contains the Clifford group is all of SU(2^n). So by this theorem, it is known that adding any rotation by an irrational multiple of pi to the Clifford group boosts it to universality.  
> **username_2**: Therefore I believe the above reference resolves the second part of your question, about whether adding any irrational rotation to the Clifford group boosts it to universality for composite d.  
> **username_0**: Thanks. You are right, that resolves the 2nd part. Seems like I cannot upvote your comments because of my rating. I guess now the only question left is whether having a non-Clifford gate provides the rotation by irrational multiple of pi.  
> **username_2**: Actually an even stronger statement is known for the second part, because I believe the quantum clifford group is actually the "complex" Clifford group $\chi_m$ described in the Nebe et al. references, not the "real" clifford group $C_m$. In that case, Theorem 6.5 of Nebe et. al 2000 tells you that that Complex Clifford group is a maximal subgroup of the unitaries for any d (prime or composite). So therefore, combining this with Corollary 6.8.2 of Nebe et al. 2006, you get that adding any non-Clifford element to any Clifford group (prime or composite) boosts you to universality.  
> **username_2**: (It seems the PRX reference was using theorem 7.3 of Nebe et al (2000) which is the same statement for the real Clifford group and which only applies to prime d. So if I'm correct that the quantum Clifford group is actually the complex Clifford group $\chi_m$, then that implies the PRX reference was using the wrong theorem. It seems this should be the case, because the real Clifford group is defined as the stabilizer of the real Pauli group in the orthogonal matrices (see definition 2.1 of Nebe et al 2000), which is smaller than the complex quantum Clifford group.)  
> **username_0**: Thanks for pointing that out. You might be right that the statement for universality using Clifford gates and one non-Clifford gate holds for any dimension d. I guess I am curious whether one necessarily needs a rotation by an irrational multiple of pi in order to be dense in SU(d) and whether there exists a proof proving or contradicting such a statement.  
> **username_0**: Let us [continue this discussion in chat](http://chat.stackexchange.com/rooms/39704/discussion-between-username_0-and-adam-bouland).  
> **username_3**: This is an interesting answer with great references (note that the references only address the case that $ d $ is prime) so I upvoted it. But I do want to clarify that your claim for composite $ d $ is false. For $ d $ composite, it is not true that adding any non Clifford gate to the Clifford group in $ SU(d^n) $ will generate a universal subgroup.  

---

