An official website of the United States government
Here’s how you know
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, Emanuel Knill
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
Somma, R.
, Boixo, S.
, Barnum, H.
and Knill, E.
(2008),
Quantum Simulations of Classical Annealing Processes, Physical Review Letters
(Accessed April 26, 2024)