DIMACS Theoretical Computer Science Seminar

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


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.