Skip to main content
U.S. flag

An official website of the United States government

Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.

Quantum Simulations of Classical Annealing Processes



Rolando Somma, S. Boixo, Howard Barnum, Emanuel Knill


We describe a quantum algorithm that solves combinatorial optimization problems by quantum simulation of a classical simulated annealing process. Our algorithm exploits quantum walks and the quantum Zeno effect induced by evolution randomization. It requires order 1/sqrt(delta) steps to find an optimal solution with bounded error probability, where delta is the minimum spectral gap of the stochastic matrices used in the classical annealing process. This is a quadratic improvement over the order 1/delta steps required by the latter.
Physical Review Letters


quantum computing, quantum algorithms, Monte Carlo Markov chains, simulated annealing


Somma, R. , Boixo, S. , Barnum, H. and Knill, E. (2008), Quantum Simulations of Classical Annealing Processes, Physical Review Letters (Accessed July 22, 2024)


If you have any questions about this publication or are having problems accessing it, please contact

Created September 25, 2008, Updated October 12, 2021