Phys. Rev. E 84, 061152 (2011) [8 pages]Exponential complexity of the quantum adiabatic algorithm for certain satisfiability problems
See accompanying Physics Synopsis 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. ©2011 American Physical Society URL:
http://link.aps.org/doi/10.1103/PhysRevE.84.061152
DOI:
10.1103/PhysRevE.84.061152
PACS:
75.10.Nr, 03.67.Lx, 03.67.Ac, 64.70.Tg
|
|
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.