# Is the Clifford group finite?

For any fixed $$n$$, how do we prove that the $$n$$-qubit Clifford group (subgroup of $$U(2^n)$$ generated by Hadmard gates, phase-shift gates and CNOT gates) is finte or not? I know that for the single qubit case, where only H gate and S gate are involved, it is a finite group since these two gates correspond to $$\pi$$ rotations on the Bloch sphere along axes that manifest symmetry. I guess it remains to be finite in multi-qubit case but I couldn't find a way to prove that rigorously.

Moreover, if it is finite, what is the expression of the number of elements in the group as a function of $$n$$?

• A Clifford gate conjugates Pauli group elements into other Pauli group elements, and the Pauli group on N qubits is finite... Sep 8, 2020 at 6:28
• But does that suffice to prove the finiteness? Sep 8, 2020 at 6:39
• It means that every Clifford of size N is a function can be thought of as a function that takes inputs from a finite set (size 4^N) and produces outputs to the same set. There are at most $(4^N)^{(4^N)}$ such functions, even before accounting that only the $2N$ generator inputs matter or that the function must preserve commutativity. Sep 8, 2020 at 17:15
• I got it, thank you! So what remains is to prove that the identity matrix is the only (up to a global phase) unitary that keeps each Pauli operator fixed under conjugation, and that is trivial. Sep 9, 2020 at 2:10

Sometimes, there is a bit of confusion around the Clifford group in the field ... and it's a matter of definition.

A lot of people define the Clifford group $$\mathrm{Cl}_n(p)$$ of $$n$$ qudits of prime dimension $$p$$ as the unitary normaliser of the generalised Pauli group (e.g. Gottesman, Nielsen & Chuang). As such, it is clearly not a finite group as the centre is $$U(1)$$.

However, this is also a bad definition, both from the mathematical and the physical point of view. Why? First, because the centre is mathematically boring and doesn't add anything to the structure of the group and second, because the global phase of a unitary is unphysical.

There are three ways of resolving this:

1. Define it by its generators (see Gottesman's paper on higher-dimensonal generators). Then, it's clear that it is finite since all generators have algebraic matrix entries. Using the standard generators, you will still get a too large centre in the qubit case: $$\mathbb{Z}_8$$. The minimal one is $$\mathbb{Z}_4$$ in the qubit case an $$\mathbb{Z}_p$$ in the qudit case. Redefining the $$H$$ gate as $$\frac{1+i}{\sqrt{2}} H$$ makes the centre minimal for qubits.
2. You can define it as the normaliser in the unitary group with entries in $$\mathbb{Q}[i]$$ (rational complex numbers). This will give you a group with minimal centre (see Ref. 1).
3. Define the projective group $$\overline{\mathrm{Cl}}_n(p):=\mathrm{Cl}_n(p)/U(1)$$, or equivalently, the image under the adjoint representation, i.e.~the unitary channels associated to Cliffords. Its elements can be seen as permutations of the Pauli operators (possibly with added phases) which preserve commutation relations. Since there are $$p^{2n}$$ Pauli operators, the number of permutations is finite (and thus is $$\overline{\mathrm{Cl}}_n(p)$$). Moreover, it holds $$\overline{\mathrm{Cl}}_n(p)/\overline{\mathcal{P}}_n(p) \simeq \mathrm{Sp}_{2n}(p),$$ where $$\overline{\mathcal{P}}_n(p)$$ is the (generalised) Pauli group up to phases and $$\mathrm{Sp}_{2n}(p)$$ is the symplectic group over the finite field $$\mathbb{F}_p$$. Its cardinality is $$|\mathrm{Sp}_{2n}(p)| = p^{n^2} \prod_{i=1}^n (p^{2i} - 1).$$ Thus, the projective Clifford group has cardinality $$|\overline{\mathrm{Cl}}_n(p)| = |\overline{\mathcal{P}}_n(p)| |\mathrm{Sp}_{2n}(p)| = p^{2n} p^{n^2} \prod_{i=1}^n (p^{2i} - 1)$$ For the non-projective ones, one has to multiply with the order of the centre. For a reference, see e.g. Ref. 2

References:

1. Gabriele Nebe, E. M. Rains, and N. J. A. Sloane. “The invariants of the Clifford groups”
2. D. Gross, "Hudson’s theorem for finite-dimensional quantum systems"
• Nice answer...of the three options, #3 is my favorite : the link to symplectic groups gives a new angle to look at clifford operators in terms of their symplectic counterparts.... Sep 11, 2020 at 2:53
• I agree, for me it's the right way of looking at it, although I wouldn't call it "new". It's the basis for a lot of remarkable results on the Clifford group, and the bread and butter of my daily research. Sep 12, 2020 at 16:59
• It's something that comes up in many different areas...often under disguise. I'm sure you're aware of Folland's book on Harmonic Analysis. Here's another source you might find interesting link.springer.com/article/10.1155/ASP/2006/85685 Sep 14, 2020 at 1:06
• @IanGershonTeixeira We have $\mathrm{Cl}_n(p) \simeq \mathrm{Sp}_{2n}(p) \ltimes \mathcal{P}_n(p)$ if and only if $p$ is an odd prime(-power). In this case, the subgroup isomorphic to $\mathrm{Sp}_{2n}(p)$ is the image under the metaplectic/Weil representation (which is linear for finite fields). There is no such subgroup for $p=2$. This is related to the Wigner function being non-covariant under Cliffords and has already been proven by Bolt et al. in 1960. This holds in the non-projective version for equal centres. I can provide more details if you raise a separate question. Mar 20, 2022 at 11:40
• @IanGershonTeixeira it is indeed true that for any prime $p$, the group of centre-fixing automorphisms of the Pauli/Heisenberg-Weyl group is isomorphic to the projective Clifford group $\overline{\mathrm{Cl}}_n(p)$. See Section 3.2 ($p$ odd), 3.3.1 ($p$ even) and 4.1 in my thesis kups.ub.uni-koeln.de/50465 May 12, 2022 at 13:54