Quantum Simulations of Classical Annealing Processes
Loading...
Date
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Description
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
4 pages - 1 figure. This work differs from arXiv:0712.1008 in that the quantum Zeno effect is implemented via randomization in the evolution