The search for a quantum algorithm for Graph Isomorphism

Since Shor's celebrated quantum algorithm for factoring large integers,
there have been very few new quantum algorithms that offer an
exponential speedup over the best known classical algorithms. A
natural target for such algorithms is the Graph Isomorphism problem,
which like factoring appears to be outside P but not NP-complete.
Indeed, Graph Isomorphism can be reduced to a more general problem, the
Hidden Subgroup Problem, which also includes factoring. I will
describe recent negative results (joint work with Alex Russell and
Leonard J. Schulman) showing that a naive generalization of Shor's
algorithm to Graph Isomorphism cannot work. However, these results
suggest a type of algorithm which may yet succeed, and I will also
describe some recent positive results that offer tantalizing evidence
that a quantum algorithm does indeed exist.

Cristopher Moore holds a joint appointment in the departments of
Computer Science and Physics at the University of New Mexico. He has
worked extensively at the boundary between these two fields, and has
made contributions to quantum computing, statistical physics, and the
theory of social networks.