TITLE: Adiabatic quantum algorithms
SPEAKER: Umesh Vazirani [UC, Berkeley]
DATE: 2:00 - 3:00 P.M., Thursday August 21, 2003
LOCATION: Sigma, 1L (PA)
HOSTS: Vinay Deolalikar/Ram Swaminathan
ABSTRACT:
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.
|
printable version
