Abstract
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 , 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.
- Received 1 October 2011
DOI:https://doi.org/10.1103/PhysRevE.84.061152
©2011 American Physical Society
Synopsis
Mind the Gap
Published 29 December 2011
Simulations of a key quantum algorithm reveal the time required for executing a sample computation and point to possible methods for optimization.
See more in Physics