Los Alamos National Laboratory
Lab Home  |  Phone
 
 
Quantum Institute : 2007 Quantum Lunch Seminar Archives

CONTACTS

  • Coordinator
    Diego Dalvit
  • 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 ,
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.


Operated by Los Alamos National Security, LLC for the U.S. Department of Energy's NNSA

Inside | © Copyright 2007-8 Los Alamos National Security, LLC All rights reserved | Disclaimer/Privacy | Web Contact