Adiabatic quantum algorithms
Date and Time
Wednesday, October 8, 2003 - 4:00pm to 5:30pm
Computer Science Small Auditorium (Room 105)
Umesh Vazirani, from UC Berkeley
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.