Title: How powerful are Adiabatic Quantum Algorithms?
Recently, Farhi et al. proposed a novel paradigm for the design of quantum algorithms - via quantum adiabatic evolution. In the March 2001 issue of Science, they reported intruiging results based on numerical simulations indicating that the algorithm works in polynomial time on certain NP-complete variants on 3-SAT. The running time of the quantum adiabatic algorithm is governed by the minimum gap between the first and second eigenvalue of the (time varying) Hamiltonian that describes the evolution of the algorithm. We show that this gap is exponentially small for a family of instances of 3SAT, thus showing that the algorithm takes exponential time in the worst case. On the other hand, we also show that quantum adiabatic computing does give a quadratic speedup for general search.