First order phase transition in the Quantum Adiabatic Algorithm

Understand

We simulate the quantum adiabatic algorithm (QAA) for the exact cover problem for sizes up to N=256 using quantum Monte Carlo simulations incorporating parallel tempering.

• At large N we find that some instances have a discontinuous (first order) quantum phase transition during the evolution of the QAA.
• This fraction increases with increasing N and may tend to 1 for N -> infinity.