Somma, R.
, Boixo, S.
, Barnum, H.
and Knill, E.
(2008),
Quantum Simulations of Classical Annealing Processes, Physical Review Letters
(Accessed April 18, 2024)
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
Created September 25, 2008, Updated October 12, 2021