#### Theory Seminar

# The search for a quantum algorithm for Graph Isomorphism

Add to Google Calendar

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.