Title: On Quantum Algorithms for the Graph Isomorphism Problem
Speaker: Martin Rötteler, NEC
Date: Wednesday, January 31, 2007 11:00-12:00pm
Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
It is well-known that the graph isomorphism problem reduces to the hidden subgroup problem (HSP) in the symmetric group. What is more, 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?
In this talk we address this question by analyzing this HSP reduction and the related quantum coset states, which encode the hidden subgroup. We show that highly entangled quantum measurements on at least Omega(n log n) coset states are necessary to get useful information, matching an information theoretic upper bound. Our main theorem can also be used to rule out some joint measurements for other groups besides the symmetric group, such as linear groups over finite fields and direct powers of a fixed finite group.
Joint work with Sean Hallgren and Pranab Sen.