Complexity of the Quantum Adiabatic Algorithm

The Quantum Adiabatic Algorithm (QAA) has been proposed as a mechanism for efficiently solving optimization problems on a quantum computer. Here, we determine its efficiency by considering several constraint satisfaction (SAT) problems. We do this by studying the size dependence of their typical minimum energy gap using quantum Monte Carlo methods. We find that for most problems this gap decreases exponentially with the size of the problem, indicating that the QAA is not more efficient than existing classical search algorithms. However, for one specific problem, namely, MAX-2-XORSAT, there is evidence to suggest that the gap may be polynomial near the phase transition.