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.