I'm trying to understand the relationship between graph isomorphism and the hidden subgroup problem. Is there a good reference for this ?
$\begingroup$
$\endgroup$
3
asked Aug 16, 2010 at 21:23
-
2$\begingroup$ Tssk, not only will we need to cure your GI disease, but also all the poor readers of your question who also become infected! (This is in jest, I am somewhat prone to GI disease too.) $\endgroup$– András SalamonAug 17, 2010 at 1:17
-
1$\begingroup$ too true. I have to stay away from Dave Bacon now :) $\endgroup$– Suresh VenkatAug 17, 2010 at 1:38
-
2$\begingroup$ FYI, the following relatively recent paper I think put the nail in the coffin on "quantum sieve algorithms" for GI, which covers many of the attempts so far (and is not mentioned in Dave Bacon's blog post): dx.doi.org/10.1137/080724101. The paper is heavy on representation theory, but the intro is not, and is a pretty good read. $\endgroup$– Joshua GrochowAug 26, 2010 at 5:23
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
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).
answered Aug 16, 2010 at 21:46
$\begingroup$
$\endgroup$
0
You might want to read Dave Bacon's recent blog post on Graph Isomorphism with links to the literature.
$\begingroup$
$\endgroup$
"Quantum algorithms for algebraic problems" by Andrew Childs and Wim van Dam arXiv:0812.0380 is a very good survey paper that contains a good intro the non-Abelian HSP and its relation to Graph Isomorphism.
