I'm trying to understand the relationship between graph isomorphism and the hidden subgroup problem. Is there a good reference for this ?
Graph Isomorphism and hidden subgroups
cc.complexity theory;reference request;quantum computing;graph isomorphism
References can be found in martinschwarz's answer, but here's a summary of a couple reductions.The symmetric group $S_n$ acts on graphs of n vertices by permuting the vertices.  Determining whether two graphs are isomorphic is polynomial-time equivalent to computing a polynomial-size generating set for $Aut(G)$.Reduction to the HSP over the symmetric group $S_n$ (where $n$ is the number of variables in the graph).  The function $f$ is $f(p)=p(G)$ where $p$ is a permutation in $S_n$, and $p(G)$ is the permuted version of $G$.  Then $f$ is constant on cosets of $Aut(G)$ and distinct on distinct cosets (note that the image of $f$ consists of all graphs isomorphic to $G$).  Since the hidden subgroup is exactly $Aut(G)$, if we could solve this HSP then we would have the generating set for $Aut(G)$, which is all we need to solve GI (see above).Reduction to the HSP over $S_n \wr \mathbb{Z}/2\mathbb{Z}$.  If we want to know if two graphs $G$ and $H$ on $n$ vertices are isomorphic, consider the graph $K$ which is the disjoint union of $G$ and $H$ on $2n$ vertices.  Let $\mathbb{Z}/2\mathbb{Z}$ act on the vertices by swapping $i$ with $n+i$ for $i=1,...,n$.  Either $Aut(K) = Aut(G) \times Aut(H)$ or $Aut(K) = (Aut(G) \times Aut(H)) semidirect \mathbb{Z}/2\mathbb{Z}$.  As before, let $f(x)=x(K)$ where $x$ is now an element of $S_n \wr \mathbb{Z}/2\mathbb{Z}$ that acts on $K$ as described.  The hidden subgroup associated to $f$ is exactly $Aut(K)$, as in the previous reduction.  If we solve this HSP, we get a generating set for $Aut(K)$.  It is then easy to check whether the generating set contains any element that swaps the copy of $G$ with the copy of $H$ inside $K$ (has nontrivial $\mathbb{Z}/2\mathbb{Z}$ component).