Quantum Simulations of Classical Annealing Processes

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δ$ steps to find an optimal solution with bounded error probability, where $δ$ is the minimum spectral gap of the stochastic matrices used in the classical annealing process. This is a quadratic improvement over the order $1/δ$ steps required by the latter.

4 pages - 1 figure. This work differs from arXiv:0712.1008 in that the quantum Zeno effect is implemented via randomization in the evolution