25

I'm trying to understand the relationship between graph isomorphism and the hidden subgroup problem. Is there a good reference for this ?

Zsbán Ambrus
  • 287
  • 2
  • 13
Suresh Venkat
  • 32,071
  • 4
  • 95
  • 271
  • 2
    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.) – András Salamon Aug 17 '10 at 01:17
  • 1
    too true. I have to stay away from Dave Bacon now :) – Suresh Venkat Aug 17 '10 at 01:38
  • 2
    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): http://dx.doi.org/10.1137/080724101. The paper is heavy on representation theory, but the intro is not, and is a pretty good read. – Joshua Grochow Aug 26 '10 at 05:23

3 Answers3

23

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).

Joshua Grochow
  • 37,260
  • 4
  • 129
  • 228
17

You might want to read Dave Bacon's recent blog post on Graph Isomorphism with links to the literature.

Martin Schwarz
  • 5,496
  • 25
  • 41
15

"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.

dabacon
  • 309
  • 2
  • 3