Format

Send to

Choose Destination
Phys Rev Lett. 2008 Sep 26;101(13):130504. Epub 2008 Sep 26.

Quantum simulations of classical annealing processes.

Author information

1
Perimeter Institute for Theoretical Physics, Waterloo, ON N2L 2Y5, Canada. rsomma@perimeterinstitute.ca

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.

PMID:
18851429
DOI:
10.1103/PhysRevLett.101.130504
[Indexed for MEDLINE]

Supplemental Content

Full text links

Icon for American Physical Society
Loading ...
Support Center