First-Order Phase Transition in the Quantum Adiabatic Algorithm

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\to \infty$.

Figure 1

An instance with a first-order transition with $N=128$. Note the expanded horizontal scale.

Figure 2

The main figure shows the spin glass order parameter $q$, defined in Eq. (5), as a function of $s$ for an instance with $N=64$ which has a first-order transition. The different curves are for different values of $\beta$. The inset shows the energy gap $\Delta E$ as a function of $s$ for $\beta =2048$, indicating that $\Delta E_{\min }=0.0021$ (same value was found for $\beta =1024$ and 4096). From the main figure, one sees that the width of the finite-size rounding increases with $T\equiv 1/\beta$ for $T\gg \Delta E$ but is independent of $T$ in the opposite limit $T\ll \Delta E$, as expected from Eq. (6). Note the expanded horizontal scale.

Figure 3

The fraction of instances with a first-order transition (defined in the way discussed in the text) as a function of size. For each size, 50 instances were studied.