The hunt for a quantum algorithm for Graph Isomorphism

Cristopher Moore (Santa Fe Institute, USA) — October 20, 2016

Abstract :
Of all the interfaces between physics and computer science that have grown up in the last few decades, quantum computing is one of the most exciting. Much of this excitement was driven by Peter Shor’s 1994 discovery that quantum computers can efficiently factor large integers, and thus break the RSA public-key cryptosystem. After describing how Shor’s algorithm works, I will describe why many of us were hopeful that a similar algorithm could work for Graph Isomorphism, another problem not known to be efficiently solvable by classical computers. Our hopes were dashed by the representation theory of the symmetric group, to which I will give a friendly introduction. As a result, we now know that no quantum algorithm remotely similar to Shor’s will solve this problem.

This is joint work with Alex Russell and Leonard Schulman, with follow-up work joint with Sean Hallgren, Pranab Sen, Martin Roetteler, and Piotr Sniady.

Biography :
Cristopher Moore received his B.A. in Physics, Mathematics, and Integrated Science from Northwestern University, and his Ph.D. in Physics from Cornell. From 2000 to 2012 he was a professor at the University of New Mexico, with joint appointments in Computer Science and Physics. Since 2012, Moore has been a resident professor at the Santa Fe Institute ; he has also held visiting positions at École Polytechnique, École Normale Superieure du Lyon, the University of Michigan, and Northeastern University. He has published over 130 papers at the boundary between physics and computer science, ranging from quantum computing, to phase transitions in NP-complete problems, to the theory of social networks and efficient algorithms for analyzing their structure. He is an elected Fellow of the American Physical Society and the American Mathematical Society. With Stephan Mertens, he is the author of The Nature of Computation from Oxford University Press.

You can also watch this video on savoirs.ens.fr or YouTube