User david gross - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-19T18:37:03Z http://mathoverflow.net/feeds/user/20318 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/84388/presentation-of-the-clifford-group-by-generators-and-relations/84744#84744 Answer by David Gross for Presentation of the Clifford group by generators and relations? David Gross 2012-01-02T13:30:59Z 2012-01-02T13:30:59Z <p>I would claim that the "right" way to understand the Clifford group abstractly is to realize that "it is a projective representation of <code>$\mathbb{Z}_2^{2n}\rtimes \mathrm{Sp}(\mathbb{Z}_2^{2n})$</code>" as explained below:</p> <ol> <li>Start with the discrete <code>$2n$</code>-dimensional vector space <code>V:=$\mathbb{Z}_2^{2n}$</code>.</li> <li>Next, we introduce a symplectic inner product on <code>$V$</code>. Here's one way of doing it: take a basis <code>$e_1, \dots, e_{2n}$</code> of <code>$V$</code>. We divide this basis into two blocks by setting <code>$p_i = e_i$</code> and <code>$q_i = e_{n+i}$</code> for <code>$i=1,\dots n$</code>. Now the symplectic inner product is defined by the relations <code>$[p_i, q_j] = [q_j, p_i] = \delta_{i,j}, [p_i, p_j]=0, [q_i, q_j]=0$</code> and their linear extensions. (A symplectic inner product is anti-symmetric, so we'd expect <code>$[p_i,q_i]=-[q_i,p_i]$</code>. But since we're working modulo 2 where <code>$-1=+1$</code>, there's no manifest negative sign in the definition above).</li> <li>Almost there. Now that we have a symplectic geometry on <code>$V$</code>, we can define the symplectic group $\mathrm{Sp}(V)$, i.e. those linear operations <code>$S$</code> on <code>$V$</code> which preserve the inner product in that <code>$[Sv, Sw]=[v,w]$</code> for all vectors <code>$v,w\in V$</code>.</li> <li>Both <code>$\mathrm{Sp}(V)$</code> and <code>$V$</code> itself act on <code>$V$</code> (the latter by addition). Let <code>$G$</code> 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 <code>$V$</code> and <code>$\mathrm{Sp}(V)$</code>.</li> </ol> <p>Anyway, the Clifford group is a faithful projective representation of this Symplectic-Affine group <code>$G$</code>. In other words, the Clifford group up to phases is "just" <code>$V\rtimes \mathrm{Sp}(V)$</code>. 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. </p> <p>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".</p> <p>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: <a href="http://arxiv.org/abs/quant-ph/0602001" rel="nofollow">http://arxiv.org/abs/quant-ph/0602001</a> and references therein.</p> <p>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.</p> http://mathoverflow.net/questions/84388/presentation-of-the-clifford-group-by-generators-and-relations/84744#84744 Comment by David Gross David Gross 2012-01-25T02:36:58Z 2012-01-25T02:36:58Z 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.