  It is known that any quantum algorithm for Graph Isomorphism that works
within the framework of the hidden subgroup problem (HSP) must perform highly
entangled measurements across Omega(n log n) coset states. One of the only
known models for how such a measurement could be carried out efficiently is
Kuperberg's algorithm for the HSP in the dihedral group, in which quantum
states are adaptively combined and measured according to the decomposition of
tensor products into irreducible representations. This ``quantum sieve'' starts
with coset states, and works its way down towards representations whose
probabilities differ depending on, for example, whether the hidden subgroup is
trivial or nontrivial.
  In this paper we give strong evidence that no such approach can succeed for
Graph Isomorphism. Specifically, we consider the natural reduction of Graph
Isomorphism to the HSP over the the wreath product S_n \wr Z_2. We show, modulo
a group-theoretic conjecture regarding the asymptotic characters of the
symmetric group, that no matter what rule we use to adaptively combine quantum
states, there is a constant b > 0 such that no algorithm in this family can
solve Graph Isomorphism in e^{b sqrt{n}} time. In particular, such algorithms
are essentially no better than the best known classical algorithms, whose
running time is e^{O(sqrt{n \log n})}.
