## Presentation of the Clifford group by generators and relations?

The Clifford group $\mathcal{C}_n$ is a matrix group on $\mathbb{C}^{2^n}$ generated by tensor products of the following matrices: $$P = \begin{pmatrix} 1 & 0 \\ 0 & i\end{pmatrix} \quad H = \frac{1}{\sqrt{2}}\begin{pmatrix} 1 & 1 \\ 1 & -1\end{pmatrix} \quad \wedge\! X = \begin{pmatrix}1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0\end{pmatrix}$$ For my purposes I take equality up to a complex unit, i.e., if $A = e^{i\alpha}B$ then $A = B$.

My question is:

is there an abstract presentation of this group by generators and relations?

Or the easier version:

is there a presentation of $\mathcal{C}_2$ or $\mathcal{C}_3$ by generators and relations?

I don't care which set of generators is used, although it would be nice if the generators were those given above.

-

http://home.lu.lv/~sd20008/papers/essays/Clifford%20group%20%5Bpaper%5D.pdf

and references in this survey

-
 I edited because the link was broken. – José Figueroa-O'Farrill Dec 28 2011 at 3:30 @ José Figueroa-O'Farrill: Thank you very much. – Boris Novikov Dec 28 2011 at 10:50 Thanks for this Boris - I had seen that survey, but sadly I don't find what I was looking for there or in the references. Gottesman's thesis was the most useful for my actual purpose. – Ross Duncan Jan 24 2012 at 12:07

I would claim that the "right" way to understand the Clifford group abstractly is to realize that "it is a projective representation of $\mathbb{Z}_2^{2n}\rtimes \mathrm{Sp}(\mathbb{Z}_2^{2n})$" as explained below:

1. Start with the discrete $2n$-dimensional vector space V:=$\mathbb{Z}_2^{2n}$.
2. Next, we introduce a symplectic inner product on $V$. Here's one way of doing it: take a basis $e_1, \dots, e_{2n}$ of $V$. We divide this basis into two blocks by setting $p_i = e_i$ and $q_i = e_{n+i}$ for $i=1,\dots n$. Now the symplectic inner product is defined by the relations $[p_i, q_j] = [q_j, p_i] = \delta_{i,j}, [p_i, p_j]=0, [q_i, q_j]=0$ and their linear extensions. (A symplectic inner product is anti-symmetric, so we'd expect $[p_i,q_i]=-[q_i,p_i]$. But since we're working modulo 2 where $-1=+1$, there's no manifest negative sign in the definition above).
3. Almost there. Now that we have a symplectic geometry on $V$, we can define the symplectic group $\mathrm{Sp}(V)$, i.e. those linear operations $S$ on $V$ which preserve the inner product in that $[Sv, Sw]=[v,w]$ for all vectors $v,w\in V$.
4. Both $\mathrm{Sp}(V)$ and $V$ itself act on $V$ (the latter by addition). Let $G$ be the group generated by these two actions. It's a subgroup of the affine group - namely those affine operations, where the linear part is symplectic. I've heard people calling it the "Symplectic-Affine Group". Technically, it's a semi-direct product between $V$ and $\mathrm{Sp}(V)$.

Anyway, the Clifford group is a faithful projective representation of this Symplectic-Affine group $G$. In other words, the Clifford group up to phases is "just" $V\rtimes \mathrm{Sp}(V)$. And, yes, that's exactly the discrete version of the well-known group of phase-space symmetries in continuous-variable systems. And, no, that's no coincidence.

The question as you asked it would boil down to giving a presentation of the relevant discrete symplectic group in terms of generators and relations. I'd be surprised if there were an insightful way of doing that. So I think you should alter your question to read "(a) what's the best abstract way of understanding the Clifford group and (b) does it involve generators and relations?" to which I would answer: "(a) see above and (b) no, it doesn't".

Everything I said has been discovered and re-discovered many times over in different communities, including mathematical physics ("Stone-von Neumann Theorem" and all that), number theory (Weil), engineering ("oscillator group"), and quantum information ("Clifford group"). Since there are too many references to list them, I just cite my own paper: http://arxiv.org/abs/quant-ph/0602001 and references therein.

Some previous answers referred to spin groups. There's also a "Clifford group" in this context which has, however, nothing to do with the Clifford group as defined in quantum information.

-
 Thanks for this answer David, and the very interesting paper you linked to. I (still!) have not had enough time to digest it properly. It doesn't seem to help me much for my current problem though, because I am really interested in the qubit case. The reason that I am asking for a generators and relations is because I want to prove that a certain formal system (a variation on the one here: arxiv.org/abs/0906.4725 ) decides the equality of Clifford circuits. If someone had already worked out which equations were necessary then this would have helped immensely. Cheers! – Ross Duncan Jan 24 2012 at 13:27 Hi Ross. The restriction to odd dimensions in my paper is not important for what you want to do. One can check equality of Clifford circuits efficiently by translating them back into the discrete symplectic picture. The problem then reduces to 2n-dimensional linear algebra (over the finite field $\mathbbm{Z}_2$). Email me if you want details. – David Gross Jan 25 2012 at 2:36

I don't have Lawson and Michelson's "Spin Geometry'" but this presentation looks like that of the extraspecial group of order 2^{2n+1} which is a subgroup of the Clifford group.

-
 Sorry - just like the above answer - the group you mention here has the wrong order. Thanks anyway. – Ross Duncan Jan 24 2012 at 13:29

Yes, from Lawson and Michelson's "Spin Geometry': If $e_1,\ldots, e_n$ is an orthonormal basis for $\mathbb{R}^n$ then the Clifford group can be presented by the abstract elements $-1,e_1,\ldots, e_n$ subject to the relation that $-1$ is central and $(-1)^2=1$, $(e_i)^2=-1$ , and $e_i e_j = (-1) e_j e_i$ for all $i\neq j$.

You can obtain your matrices through the complex spin representation.

-
 Hi Adam, thanks for the response, but we are not talking about the same group - this can easily be seen by looking at the order. – Ross Duncan Jan 24 2012 at 13:28