Date and Time

Wednesday, October 8, 2003 - 4:00pm to 5:30pm

Location

Computer Science Small Auditorium (Room 105)

Type

Colloquium

Speaker

Umesh Vazirani [1], from UC Berkeley

Host

Sanjeev Arora

Website

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.