# Prove that adding any non Clifford gate to the Clifford group yields a universal gate set

I have seen it claimed in multiple places that adding any non Clifford gate to the Clifford group yields a universal gate set. It is, however, not easy to find an accessible proof of this fact.

The question

https://cstheory.stackexchange.com/questions/34707/theorems-for-universal-set-of-quantum-gates-for-sud?noredirect=1&lq=1

cites Corollary 6.8.2 of Nebe et al. (Self-Dual Codes and Invariant Theory (Springer 2006)) as a proof of the fact that the Clifford group plus any other gate is universal.

This proof by Nebe makes heavy use of invariant theory and coding theory.

I'm looking for a more elementary or self contained proof of this result.

I would also be very happy with an answer along the lines of "Ian you are so silly, the proof in Nebe is actually quite elementary and self contained you just have to know blah blah blah [insert some actually clear explanation of why the ideas in the proof are elementary]."

Just to clarify, I understand the proof in Nielson and Chuang that single qubit gates together with cNot gates are universal.

And I am comfortable with the classification of the subgroups of $$PU_2=PSU_2=SO_3(\mathbb{R}), SU_2, U_2$$ in particular that the Clifford group on one qubit is a maximal closed subgroup and so adding any single qubit gate to the Clifford group gives a universal set for all single qubit gates and thus for all gates.

What I am really trying to understand is why adding any non Clifford gate, even a multi qubit gate, to the Clifford group yields a universal gate set.

Long comment: Ah you are totally right that naively taking the determinant 1 subgroup can go horribly wrong, thanks for catching that! I guess what I really meant is take the group $$sG:=\pi_2^{-1}[\pi_1(G)]=\{ (e^{i \theta} g) \in SU(d): g \in G \}$$ where $$\pi_1: U(d) \to PU(d)$$ and $$\pi_2: SU(d) \to PU(d)$$ are the natural projections and $$\pi_2^{-1}[\pi_1(G)]$$ just denotes taking the inverse image under $$\pi_2$$ of the group $$\pi_1(G) \subset PU(d)$$ (see https://quantumcomputing.stackexchange.com/a/27232/19675 for another situation where I define and use this group $$sG$$). And I'm not saying anything new because the group I describe is exactly the group you call $$\overline G := \{ \det(U^\dagger)^{1/d} U \, | \, U \in G\}$$ where by $$\det(U^\dagger)^{1/d} U$$ you mean all possible $$d$$ roots, so for example $$\det(H^\dagger)^{1/d} H$$ is both $$iH$$ and $$-iH$$ and $$\det(I^\dagger)^{1/d} I$$ is both $$I$$ and $$-I$$. So for $$G=\{ I, H \} \subset U(2)$$ the corresponding subgroup of $$SU(2)$$ is $$\{ I,-I,iH,-iH \}$$ exactly as you say

There is at least one other way to prove this I'm aware of. The argument uses the concept of a unitary 2-design and how this restricts the representation theory of a group.

To avoid pathological cases, we restrict our attention to the special unitary group $$SU(d)$$. Note that we can regard any subgroup $$G\subset U(d)$$ as a subgroup of $$SU(d)$$ by taking $$\overline G := \{ \det(U^\dagger)^{1/d} U \, | \, U \in G\}$$.

The goal is to prove that the Clifford group plus any non-Clifford gate generates a dense subgroup of $$SU(p^m)$$ and hence is universal.

A unitary 2-design is a (finite) set $$D\subset SU(d)$$ such that $$\frac{1}{|D|} \sum_{U\in D} U^{\otimes 2} X (U^{\otimes 2})^\dagger = \int_{SU(d)} U^{\otimes 2} X (U^{\otimes 2})^\dagger \,\mathrm{d}U, \qquad \forall X \in \mathbb C^{d^2\times d^2}.$$ Note that the right hand side projects onto the commutant of the tensor square representation, i.e. on the subspace of matrices which commute with the representation $$U\mapsto U^{\otimes 2}$$ of $$SU(d)$$. The definition of unitary 2-design extends naturally to infinite sets endowed with an appropriate measure to perform the average on the LHS.

Fact 1: We call a subgroup $$G\subset SU(d)$$ a unitary 2-group if it is a unitary 2-design, i.e. we have $$\int_G U^{\otimes 2} X (U^{\otimes 2})^\dagger \,\mathrm{d}U, = \int_{SU(d)} U^{\otimes 2} X (U^{\otimes 2})^\dagger \,\mathrm{d}U, \qquad \forall X \in \mathbb C^{d^2\times d^2}.$$ By the above remark, this is equivalent to saying that the commutant of $$G$$ and $$SU(d)$$ is the same.

Fact 2: Let $$\mathrm{Cl}_p(m)$$ be the $$m$$-qudit Clifford group of local prime dimension $$p$$. Then, $$\mathrm{Cl}_p(m)$$ is a unitary 2-group. See e.g. Zhu: "Multiqubit Clifford groups are unitary 3-designs"

Fact 3: Let $$V\in SU(p^m)\setminus \overline{\mathrm{Cl}_p(m)}$$ be any non-trivial non-Clifford gate. Then $$G:=\langle \overline{\mathrm{Cl}_p(m)}, V\rangle$$ is an infinite subgroup. [Nebe, "The invariants of the Clifford group", Thm. 6.5 and 7.3]

Claim: $$G$$ is a unitary 2-group.

Proof: Since $$G$$ is a subgroup of $$SU(p^m)$$ the commutant of $$G$$ has to contain the commutant of $$SU(p^m)$$. Likewise, since $$\mathrm{Cl}_p(m)$$ is a subgroup of $$G$$, the commutant of $$\mathrm{Cl}_p(m)$$ has to contain the commutant of $$G$$. But the commutant of $$\mathrm{Cl}_p(m)$$ and $$SU(d)$$ is the same, since $$\mathrm{Cl}_p(m)$$ is a unitary 2-group. qed

Fact 4: Any finitely generated infinite unitary 2-group is dense in $$SU(d)$$. [A. Sawicki and K. Karnas, "Universality of single qudit gates", Cor. 3.5; See also Prop. 3 in my paper]

Final remark: We can also replace Nebe's argument on the maximal finiteness of the Clifford group ("Fact 3") with the classification of finite unitary group designs [Bannai et al. "Unitary t-groups"] which implies that any finite unitary 2-group that contains the Clifford group, has to be the Clifford group (up to its centre). However, this results makes itself heavy use of the classification of finite groups and thus at least on the same level as Nebe's proof. I would say it's vastly more difficult.

• Interesting that both Thm 7.3 and the Bannai et al paper (which relies on the Guralnick Tiep paper) rely on CFSG to prove maximal finiteness. Even more interesting that the Nebe paper seems to be able to prove maximal finiteness for the qubit Clifford group in Thm 6.5 Do you understand why Nebe can do the qubit case without CFSG but has to fall back on CFSG for Thm 7.3? Why is the the proof so much harder for odd primes? Mar 23, 2022 at 23:42
• @IanGershonTeixeira Good question. I don't know the answer, so I'm guessing. In the qubit case, $p$ is fixed, while in the qudit case, it is not. So Nebe uses a special argumentation for $p=2$, while for odd $p$ more cases could occur and she relies on CFSG instead. As I said, it's just guessing, I could not point out where the $p=2$ proof goes wrong or had to be adapted for $p > 2$. Mar 24, 2022 at 8:41
• Was looking back at this again and appreciating what a great answer it is! One small note, your definition of $\overline{G}$ does not seem to be contained in $SU(d)$. For example if we take the unitary matrix $H$ (the Hadamard matrix) then $det(H^\dagger)H=-H$ which has determinant $-1$ and so is not in $SU(d)$ The most obvious definition for $\overline{G}$ would be just take the determinant $1$ subgroup of $G$. I think that works fine Dec 14, 2023 at 18:25
• @IanGershonTeixeira I missed the dimensional correction, that should read $\mathrm{det}(U^\dagger)^{1/d} U$. As this is a group homomorphism, that works as intended. Taking the determinant 1 subgroup of $G$ is not enough, as you might "lose" group elements. For instance, the determinant 1 subgroup of $\{ \mathbb{1}, H \}$ is trivial. Dec 20, 2023 at 9:32
• Ah you are totally right that naively taking the determinant 1 subgroup can go horribly wrong, thanks for catching that! I guess what I really meant is take the group $$sG:=\pi_2^{-1}[\pi_1(G)]=\{ (e^{i \theta} g) \in SU(d): g \in G \}$$ where $\pi_1: U(d) \to PU(d)$ and $\pi_2: SU(d) \to PU(d)$ are the natural projections and $\pi_2^{-1}[\pi_1(G)]$ just denotes taking the inverse image under $\pi_2$ of the group $\pi_1(G) \subset PU(d)$ (see quantumcomputing.stackexchange.com/a/27232/19675 ). This comment is getting long so I put more details at the end of my question. Dec 20, 2023 at 16:57