Exponential Complexity of the Quantum Adiabatic Algorithm for certain Satisfiability Problems

Autor:	Hen, Itay, Young, A. P.
Rok vydání:	2011
Předmět:	Condensed Matter - Statistical Mechanics Computer Science - Computational Complexity Quantum Physics
Zdroj:	Phys. Rev. E 84, 061152 (2011)
Druh dokumentu:	Working Paper
DOI:	10.1103/PhysRevE.84.061152
Popis:	We determine the complexity of several constraint satisfaction problems using the quantum adiabatic algorithm in its simplest implementation. We do so by studying the size dependence of the gap to the first excited state of "typical" instances. We find that at large sizes N, the complexity increases exponentially for all models that we study. We also compare our results against the complexity of the analogous classical algorithm WalkSAT and show that the harder the problem is for the classical algorithm the harder it is also for the quantum adiabatic algorithm. Comment: 9 pages, 7 figures
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/1109.6872 Zobrazit plný text záznamu View this record from Arxiv