**On quantum algorithms for the graph isomorphism problem** - Martin Roetteler

It is well-known that the graph isomorphism problem reduces
to a hidden subgroup problem (HSP) in the symmetric group. Moreover,
most exponential speedups in quantum computing are obtained by
solving HSP instances. Why is it then, that so far no polynomial quantum
algorithm for the graph isomorphism problem has been found?
We address this question by analyzing this HSP reduction and the
related quantum coset states. We show that entangled quantum
measurements on at least Omega(n log n) coset states are necessary to
get useful information, matching an information theoretic upper
bound.
Joint work with Sean Hallgren and Pranab Sen.