Size dependence of the minimum excitation gap in the Quantum Adiabatic Algorithm

Autor:	Young, A. P., Knysh, S., Smelyanskiy, V. N.
Rok vydání:	2008
Předmět:	Condensed Matter - Disordered Systems and Neural Networks Condensed Matter - Statistical Mechanics Quantum Physics
Zdroj:	Phys. Rev. Lett. 101, 170503 (2008)
Druh dokumentu:	Working Paper
DOI:	10.1103/PhysRevLett.101.170503
Popis:	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 (QAA) for much larger sizes than before. For a range of sizes, N <= 128, where the classical Davis-Putnam algorithm shows exponential median complexity, the QAA 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). Comment: 4 pages, 5 figures
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/0803.3971 Zobrazit plný text záznamu View this record from Arxiv