Phys. Rev. Lett. 101, 170503 (2008) [4 pages]

Size Dependence of the Minimum Excitation Gap in the Quantum Adiabatic Algorithm

Abstract

References

Citing Articles (20)

Download: PDF (271 kB) Buy this article Export: BibTeX or EndNote (RIS)

A. P. Young^1,*, S. Knysh^2,†, and V. N. Smelyanskiy^3,‡
¹Department of Physics, University of California, Santa Cruz, California 95064, USA
²ELORET Corporation, NASA Ames Research Center, MS 229, Moffett Field, California 94035-1000, USA
³NASA Ames Research Center, MS 269-3, Moffett Field, California 94035-1000, USA

Received 27 March 2008; published 23 October 2008

We study the typical (median) value of the minimum gap in the quantum version of the exact cover problem using quantum Monte Carlo simulations, in order to understand the complexity of the quantum adiabatic algorithm for much larger sizes than before. For a range of sizes N≤128, where the classical Davis-Putnam algorithm shows exponential median complexity, the quantum adiabatic algorithm shows polynomial median complexity. The bottleneck of the algorithm is an isolated avoided-crossing point of a Landau-Zener type (collision between the two lowest energy levels only).

URL:

http://link.aps.org/doi/10.1103/PhysRevLett.101.170503

DOI:

10.1103/PhysRevLett.101.170503

PACS:

03.67.Ac, 03.67.Lx, 75.10.Nr, 89.70.Eg

^*peter@physics.ucsc.edu

^†sergey.i.knysh@nasa.gov

^‡Vadim.N.Smelyanskiy@nasa.gov

About | Terms and Conditions | Subscriptions | Search | Help

Use of the American Physical Society websites and journals implies that the user has read and agrees to our Terms and Conditions and any applicable Subscription Agreement. Physical Review®, Physical Review Letters®, Reviews of Modern Physics®, and Physical Review Special Topics® are trademarks of the American Physical Society.

Citation Search:

Phys. Rev. Lett. 101, 170503 (2008) [4 pages]

Size Dependence of the Minimum Excitation Gap in the Quantum Adiabatic Algorithm