<p>You might want to read Dave Bacon's recent <a href="http://dabacon.org/pontiff/?p=4148">blog post</a> on Graph Isomorphism with links to the literature.</p>

CC BY-SA 2.5
2010-08-16T21:38:07.933Z
2010-08-16T21:38:07.933Z
Martin Schwarz
<p>"Quantum algorithms for algebraic problems" by Andrew Childs and Wim van Dam <a href="http://arxiv.org/abs/0812.0380">arXiv:0812.0380</a> is a very good survey paper that contains a good intro the non-Abelian HSP and its relation to Graph Isomorphism.</p>

CC BY-SA 2.5
2010-11-14T20:43:14.893Z
2010-11-14T20:43:14.893Z
dabacon
<p>References can be found in martinschwarz's answer, but here's a summary of a couple reductions.</p>

<p>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)$.</p>

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

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

CC BY-SA 2.5
2010-08-16T21:46:57.627Z
2010-08-31T14:41:35.667Z
2010-08-31T14:41:35.667Z
Joshua Grochow
<p>I'm trying to understand the relationship between graph isomorphism and the hidden subgroup problem. Is there a good reference for this ?</p>

CC BY-SA 2.5
2010-08-26T05:23:43.413Z
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
CC BY-SA 2.5
2010-08-17T01:17:05.660Z
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
CC BY-SA 2.5
2010-08-17T01:38:26.933Z
too true. I have to stay away from Dave Bacon now :)
Suresh Venkat
<cc.complexity-theory><reference-request><quantum-computing><graph-isomorphism>
Graph Isomorphism and hidden subgroups
Suresh Venkat
# Graph Isomorphism and hidden subgroups

(Asked by: username_0 on 2010-08-16)

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

**Tags:** cc.complexity-theory, reference-request, quantum-computing, graph-isomorphism
> **Comments:**
> **username_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.)  
> **username_0**: too true. I have to stay away from Dave Bacon now :)  
> **username_1**: 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.  

---

## 3 answers

### Answer by username_1 on 2010-08-16. Score: 24 | Accepted answer

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


---

### Answer by username_3 on 2010-08-16. Score: 18

You might want to read Dave Bacon's recent [blog post](http://dabacon.org/pontiff/?p=4148) on Graph Isomorphism with links to the literature.


---

### Answer by username_4 on 2010-11-14. Score: 16

"Quantum algorithms for algebraic problems" by Andrew Childs and Wim van Dam [arXiv:0812.0380](http://arxiv.org/abs/0812.0380) is a very good survey paper that contains a good intro the non-Abelian HSP and its relation to Graph Isomorphism.


---

