NIST logo

Publication Citation: Quantum Simulations of Classical Annealing Processes

NIST Authors in Bold

Author(s): Rolando Somma; S. Boixo; Howard Barnum; Emanuel H. Knill;
Title: Quantum Simulations of Classical Annealing Processes
Published: September 26, 2008
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
Pages: pp. 130504-1 - 130504-4
Keywords: quantum computing;quantum algorithms, Monte Carlo Markov chains;simulated annealing
Research Areas: Math