Quantum Institute: Visitor Schedule

The Quantum Lunch is regularly held on Thursdays in the Theoretical Division Conference Room, TA-3, Building 123, Room 121.
For more information, contact Diego Dalvit.

December 20, 2007
Thursday, 12:30 PM to 2 PM

Rolando Somma ,
Perimeter Institute

Quantum Simulated Annealing

Abstract

In this talk, I present a new quantum algorithm (QA) to solve combinatorial optimization problems through the quantum simulation of a classical annealing process. The quantum algorithm involves techniques from quantum walks and quantum Zeno effect. The latter can be implemented using the phase estimation algorithm or randomization over evolution time. I will show that the implementation complexity of the QA scales with the inverse of the square root of the the spectral gap of the stochastic matrix used in the classical simulation. Thus, it greatly outperforms well-known classical simulated annealing algorithms with Monte Carlo methods, where the number of operations scales with the inverse of the gap.