# Proof for Cardinality of the Clifford Group

In this article: (http://home.lu.lv/~sd20008/papers/essays/Clifford%20group%20[paper].pdf) a proof is given for the cardinality of the Clifford group. I understand all the parts of it except for how the recursion is given. The part above equation (4) which states that:

"The elements of $$C_n$$ that leave both $$X_n$$ and $$Z_n$$ fixed form a group isomorphic to $$C_{n−1}$$ with the number of cosets equal to $$2(4^n − 1)4^n$$ . Hence $$|C_n| = 2(4^n − 1)4^n|C_{n−1}|$$. Therefore,

$$\left|\mathcal{C}_{n}\right|=\prod_{j=1}^{n} 2\left(4^{j}-1\right) 4^{j}=2^{n^{2}+2 n} \prod_{j=1}^{n}\left(4^{j}-1\right) .\textrm{"}$$

Can someone explain how the isomorphism and cosets are defined, and how this leads to a recursion which correctly counts the right amount of elements of $$C_n$$?

What the author wrote is completely correct, they did not make a mistake.

The subgroup of Cliffords fixing $$X_n$$ and $$Z_n$$ is indeed isomorphic to $$C_{n-1}$$ as a group, this is simply because this subgroup acts by assumption as $$U (\sigma_1 \otimes \dots \otimes \sigma_n) U^\dagger = \tilde U (\sigma_1\otimes\dots\otimes\sigma_{n-1})\tilde U^\dagger \otimes \sigma_n.$$ Here, $$\tilde U$$ is a unitary that maps the $$(n-1)$$-qubit Pauli group to itself, so an element of $$C_{n-1}$$. Likewise, we can invert the mapping by the embedding $$C_{n-1} \ni U \mapsto U \otimes I \in C_{n}.$$

The (right or left) cosets are denoted as $$C_n/C_{n-1}$$. By definition, the left coset of an element $$U\in C_n$$ is $$U \cdot C_{n-1} := \{ U (V\otimes I) \, | \, V\in C_{n-1} \}.$$ Thus, the coset of $$U$$ is the set of unitaries which are equivalent to $$U$$ up the multiplication by an element from $$C_{n-1}$$ from the right. Then, the set of such cosets $$U \cdot C_{n-1}$$ is $$C_n/C_{n-1}$$. Hence it can be seen as equivalence classes of Cliffords (if your more familiar with that term).

The relevance of all this is that Lagrange's theorem tells you that the order of $$C_n$$ is now given as $$|C_n| = |C_n/C_{n-1}| |C_{n-1}|.$$ (the notation is kind of suggestive that this indeed holds).

To compute the cardinality of $$C_n$$, we thus first have to determine the number of cosets $$|C_n/C_{n-1}|$$. Two Cliffords $$U,W\in C_n$$ are in the same coset if and only if $$UX_nU^\dagger = WX_nW^\dagger, \quad UZ_nU^\dagger = WZ_nW^\dagger.$$ Thus, the number of cosets is given by the possible images of $$X_n$$ and $$Z_n$$. Up to a $$\pm 1$$ phase, the possible images coincide with ordered pairs of anti-commuting Pauli operators. Let's count those.

Clearly, we can select the first Pauli operator freely, so there are $$4^n-1$$ non-trivial choices. Then, for any fixed Pauli, there are exactly $$2^{2n-1}$$ many Paulis commuting with it (including said Pauli and the identity), so there are $$2^{2n} - 2^{2n-1} = \frac12 \times 4^n$$ many anti-commuting, ordered pairs. Finally, we can pick a $$\pm 1$$ freely for any of the two Paulis, so we have in total $$|C_n/C_{n-1}| = 4\times \frac12 \times 4^n (4^n-1) = 2 \times 4^n (4^n-1)$$ many possible anti-commuting images.

Remark: You can use this subgroup structure to efficiently sample Clifford unitaries in time $$O(n^3)$$ using a recursive subgroup algorithm (see Koenig and Smolin)

• Thank you for the answer! Can you please clarify the mapping from $C_n$ to $C_{n-1}$ you stated? Can you define the inverse of it using the same notation? It is not clear to me how you mapping works. Sep 28 at 17:42
• Is there something wrong with the table showing how the $CNOT$ gate transforms Pauli matrices $X_2, X_1, Z_2$ and $Z_1$ on this Wikipedia page: en.wikipedia.org/wiki/Clifford_gates ? It doesn't seem to align with the proof's recursion... the images of $X_1$ and $Z_1$ show that the qubit position $2$ is not 'fixed' when determining all of the $C_1$ Cliffords, as described in the proof for the cardinality of Cliffords. Sep 28 at 18:31
• @QuantumGuy123 I didn't define any such mapping. I simply stated, that Clifford unitaries that fixe $X_n$ and $Z_n$ have a particular form that allows to see them as elements of $C_{n-1}$ which gives the claimed isomorphism. If you think about the projection $f: C_n \rightarrow C_{n-1}$ that I also mentioned in the other comment, I'm currently not so sure whether it is that easy to write down explicitly (I would have to think about it). Sep 29 at 13:53
• @QuantumGuy123 The CNOT table is correct. I do not understand your comment. CNOT defines a coset by multiplication with Cliffords $V\otimes I$ from the right. This yields all 2-qubit Cliffords that map $X_2$ to $X_2$ and $Z_2$ to $Z_1Z_2$. Sep 29 at 13:59
• I'm not sure it's completely obvious from this perspective that one can choose the first Pauli freely, and that the only constraint on the second is that it must anticommute with the first. (This is a necessary condition, but why is it sufficient?) Nebe, Raines and Sloane give a short alternative proof of the cardinality of the Clifford group in arxiv.org/abs/math/0001038 that uses a bit more group theory to explain why this is true. Oct 6 at 16:00

A Clifford $$C_n$$, defined by how it maps each of $$X_i$$ and $$Z_i$$ for $$1 \leq i \leq n$$, via the functions $$g_i(\sigma_i)$$ where $$\sigma_i = \{\pm I_i, \pm X_i, \pm Y_i, \pm Z_i\},$$ can be seen as the operation $$g_1(\sigma_1) \cdot g_2(\sigma_2) \cdots \cdot g_n(\sigma_n)$$ that acts on any arbitrary Pauli, $$P = \sigma_1 \cdot \sigma_2 \cdots \cdot \sigma_n.$$ The paper explains the previous claim, I am just restating it with additional notation to explain my proof better. Using this new notation, define a function $$f(C_n) \rightarrow C_{n-1}$$ expressed as: $$g_1(\sigma_1) \cdot g_2(\sigma_2) \cdots g_{n-1}(\sigma_{n-1}) \cdot I(\sigma_n) \rightarrow g_1(\sigma_1) \cdot g_2(\sigma_2) \cdots \cdot g_{n-1}(\sigma_{n-1}),$$ where $$I$$ is a function that maps elements to itself (an identity function).

$$f$$ is the function used to define the isomorphism. Let the group operation for the isomorphism be matrix multiplication.

The isomorphism satisfies all of the required properties to be an isomorphism:

1. it satisfies $$f(U \cdot U') = f(U) \cdot f(U')$$, where $$U$$ and $$U$$ are elements of $$C_n$$
2. $$f$$ is bijective

A coset of $$C_n$$, denote it as $$C_n'$$ is defined by applying a new function $$g_n'$$ resulting in: $$C_n' = g_1(\sigma_1) \cdot g_2(\sigma_2) \cdots g'_n(I(\sigma_n))$$

The image has of $$g'_n$$ has size $$2\left(4^{n}-1\right) 4^{n}$$, following the same explanation in the referenced article (The part of the article that explains all the possible images for the pair $$\left(X_{n}, Z_{n}\right)$$. Therefore there are $$2\left(4^{n}-1\right) 4^{n}$$ cosets.

Using this isomorphism I have given, I now see how the recursion results in the correct size of the Clifford group.

The explanation for the recursion does not require group theory. A more straightforward proof-by-construction can be given by the same line of reasoning I assume the author had (combined with some of the notation I introduced).

• The author is completely correct, see my answer below. However, your approach contains a mistake: The Clifford which are factorising as $g_1(\sigma_1)\otimes \dots$ are exactly the local Cliffords. A general Cliford unitary is of the form $g_1(\sigma_1,\dots,\sigma_n) \otimes g_2(\sigma_1,\dots,\sigma_n) \otimes \dots$. You can still define the projection $f$, and it is indeed a homomorphism. This however, does not prove the recursion, for this you would still need to count cosets, or equivalently, the kernel of $f$. Sep 28 at 7:28
• Hi Markus, I am not factorizing the Cliffords. I use multiplication, not tensor products. The subscript I use on the sigma symbol or the Pauli operators, $P_i$ (where $P$ takes on a Pauli matrix, for example $X_i$, $Z_i$) indicates a Pauli matrix of size $n$, that has identity matrices at every indexed qubit position $j$ where $i \ne j$, and the Pauli matrix $P$ at qubit position $i$. I did not explicitly define my construction of the cosets, let me clarify my answer... this might take a while because I have a class to attend soon. Sep 28 at 17:39
• oh boy... I see my mistake. I am not using the correct definition for isomorphisms and homomorphisms. I will fix my answer Sep 28 at 17:50