Adiabatic quantum optimization has attracted a lot of attention because
small scale simulations gave hope that it would allow to solve
NP-complete problems efficiently. Later, negative results proved the
existence of specifically designed hard instances where adiabatic
optimization requires exponential time. In spite of this, there was
still hope that this would not happen for random instances of
NP-complete problems. This is an important issue since random instances
are a good model for hard instances that can not be solved by current
classical solvers, for which an efficient quantum algorithm would
therefore be desirable. Here, we will show that because of a phenomenon
similar to Anderson localization, an exponentially small eigenvalue gap
appears in the spectrum of the adiabatic Hamiltonian for large random
instances, very close to the end of the algorithm. This implies that
unfortunately, adiabatic quantum optimization also fails for these
instances by getting stuck in a local minimum, unless the computation is
exponentially long.
Joint work with Boris Altshuler and Hari Krovi.
