23
$\begingroup$

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

$\endgroup$
  • 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 Salamon Aug 17 '10 at 1:17
  • 1
    $\begingroup$ too true. I have to stay away from Dave Bacon now :) $\endgroup$ – Suresh Venkat Aug 17 '10 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 Grochow Aug 26 '10 at 5:23
20
$\begingroup$

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

$\endgroup$
17
$\begingroup$

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

$\endgroup$
14
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.