Presentation of the Clifford group by generators and relations?

Question

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.

Answer 1

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.

Answer 2

Follow-up, many years later:

In the currently (02/2020) most highly up-voted comment and the discussion below it, I claimed that the Clifford group is a projective representation of the semi-direct product of the phase space translations and the symplectic group. As Ross correctly implies in his response to my answer (and I wrongly deny in my response to him), this property only holds for qudits in odd dimensions, not for the qubit case! For qubits, it is still true that the symplectic group arises as a quotient group of the Clifford group (up to Paulis and multiples of the identity). However, the extension does not split.

[I've since lost my old account and access to the old email address - hence this answer comes from a new account. Apparently, the new account does not have enough "reputation" to directly reply.]

Answer 3

In the time since the question was asked this paper appeared which does exactly what I want:

Generators and relations for n-qubit Clifford operators

Answer 4

Please see

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

and references in this survey

Answer 5

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.

Answer 6

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.