10-08

Adiabatic quantum algorithms

A couple of years ago a new paradigm, based on the quantum adiabatic theorem, was introduced for the design of quantum algorithms for solving optimization problems. In this talk, I will present recent results showing that for certain objective functions, the quantum adiabatic algorithm tunnels through local optima, thus performing exponentially faster than classical local search algorithms. I will also discuss limits on the power of this new paradigm, as well as its relationship to simulated annealing, a classical heuristic for algorithm design.