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

Question

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.

Answer 1

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