Quantum Adiabatic Evolution Algorithms versus Simulated Annealing

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

We explain why quantum adiabatic evolution and simulated annealing perform similarly in certain examples of searching for the minimum of a cost function of n bits. In these examples each bit is treated symmetrically so the cost function depends only on the Hamming weight of the n bits. We also give two examples, closely related to these, where the similarity breaks down in that the quantum adiabatic algorithm succeeds in polynomial time whereas simulated annealing requires exponential time.
16pp., 10 EPS figures, using BoxedEPS macros and LaTeX. Email correspondence to E. Farhi <farhi@mit.edu>

Keywords

Quantum Physics

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/89964

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/quant-ph/0201031
 http://arxiv.org/abs/quant-ph/0201031

Collections

arXiv