Somma, R.
, Boixo, S.
, Barnum, H.
and Knill, E.
(2008),
Quantum Simulations of Classical Annealing Processes, Physical Review Letters
(Accessed May 1, 2025)
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
Published
Author(s)
Rolando Somma, S. Boixo, Howard Barnum,
Abstract
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.Citation
Physical Review Letters
Volume
101
Pub Type
Journals
Keywords
quantum computing, quantum algorithms, Monte Carlo Markov chains, simulated annealing
Citation
Issues
If you have any questions about this publication or are having problems accessing it, please contact reflib@nist.gov.
Created September 25, 2008, Updated October 12, 2021