First order phase transition in the Quantum Adiabatic Algorithm*

We investigate the complexity of the Quantum Adiabatic Algorithm using quantum Monte Carlo simulations incorporating parallel tempering for sizes up to $N = 256$. For a particular model, known as Exact Cover, we find that an increasing fraction of instances have a first order (discontinuous) quantum phase transition during the evolution of the algorithm. This implies a very small gap (probably exponential) and hence a very long running time for the algorithm to succeed. Preliminary results on other models will also be reported.