The Complexity of the Quantum Adiabatic Algorithm

The Quantum Adiabatic Algorithm has been proposed as a general purpose algorithm for solving hard optimization problems on a quantum computer. Early work on very small sizes indicated that the running time complexity only increased as a quite small power of the problem size N. We report results of Quantum Monte Carlo simulations, using parallel tempering, with which we determine the minimum energy gap and hence get information the complexity for much bigger sizes than was possible before. The aim is to see if there is a crossover to exponential complexity at large N. We present data for the typical median complexity as a function of N, which indicate a crossover to a first order transition at large sizes. This implies that the complexity is exponential at large N, at least for the problem studied.