19.04.2013

Talk proposal: "NP-intermediate problems and quantum algorithms"

Quantum computers are not believed to be able to solve NP-hard problems in polynomial time. Thus, following Shor's discovery of a quantum polynomial-time factoring algorithm, attention in quantum computing has focused on a small set of other problems that do not have a known polynomial-time classical algorithm and yet are not known to be NP-hard. In combinatorics, the most famous such problem is Graph Isomorphism and its variants such as Graph Automorphism and Polytope Isomorphism. I will explain these problems and a little of what is known about both classical and quantum algorithms for solving them.         

Tristram Bogart
Universidad de los Andes