Quantum algorithms for simulated annealing

Abstract

This paper summarizes a quantum algorithm of [R.D. Somma, et.al., Phys. Rev. Lett. 101, 130504 (2008)] that simulates a classical annealing process for solving discrete optimization problems. The complexity of the quantum algorithm scales with the inverse square root of the spectral gap of an associated stochastic matrix. This represents a quadratic quantum speedup, in terms of the gap, with respect to classical simulated annealing.

6 pages. See arXiv:0804.1571 for related work. New version has a corrected address. Encyclopedia of Algorithms, pp. 1-5, July 2015