Quantum Lunch Location:
T-Division Conference Room, TA-3,
Building 123, Room 121
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 ,
Quantum Simulated Annealing
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.