Adiabatic Quantum Computation and the Theory of Quantum Phase Transitions*

We present a general approach to determining the asymptotic scaling of adiabatic quantum computational resources (space, time, energy, and precision) on random instances of NP-complete graph theory problems. By utilizing the isomorphisms between certain NP-complete graph theory problems and certain frustrated spin models, we demonstrate that the asymptotic scaling of the minimum spectral gap that determines the asymptotic running time of adiabatic algorithms is itself determined by the presence and character of quantum phase transitions in these frustrated models. Most notably, we draw the conclusion that adiabatic quantum computers based on quantum Ising models are much less likely to be efficient than those based on quantum rotor or Heisenberg models. We then exhibit practical rotor and Heisenberg model based architectures using Josephson junction and quantum dot circuits.