First-Order Transitions and the Performance of Quantum Algorithms in Random Optimization Problems

We present a study of the phase diagram of a random optimization problem in the presence of quantum fluctuations. Our main result is the characterization of the nature of the phase transition, which we find to be a first-order quantum phase transition. We provide evidence that the gap vanishes exponentially with the system size at the transition. This indicates that the quantum adiabatic algorithm requires a time growing exponentially with system size to find the ground state of this problem.

Figure 1

(Top) Phase diagram of Eq. (1) for $c=3$. Open symbols are results of the RS calculation: first-order transition line separating the CP and QP (circles), with the corresponding spinodals (diamonds). Full symbols are the result of the 1RSB calculation: squares, clustering transition separating the CP and dCP. (Bottom) Energy and $m_x$ as a function of $\Gamma$ for temperature $T=0.05$. MC data for a sample with $N=2049$.

Figure 2

(Top) Phase diagram of Eq. (1) for $c=4$. Symbols as in Fig. 1, with the addition of the spin-glass transition line (full triangles); the correct first-order transition line is obtained from the 1RSB calculation (full circles). (Bottom) Energy and $m_x$ as a function of $\Gamma$ for temperature $T=0.05$. MC data for $N=120$ and averaged over 20 samples (full symbols) and extrapolated in $1/N$ to the $N\to \infty$ limit (open symbols). Black curve, starting from the classical ground state found using an exact MAXSAT solver [19]. Red curve, starting from the QP.

Figure 3

Lowest energy levels from exact diagonalization of a USA instance with $c=3$ and $N=15$. In the inset the region close to the phase transition is magnified.

Figure 4

Data for $c=3$ on USA instances. (Main panel) Average of the minimal gap ${\Delta }_{\min }$ as a function of $N$. Dashed line is a fit to ${\Delta }_{\min }(N)=0.911\exp (-0.081N)$. Inset: average of $[d{m}_x/d\Gamma {]}_{\max }$. In both cases, error bars are of the order of the symbol size except when explicitly shown ($N=24$). Dashed bars represent the standard deviation of a single realization of the random variables ${\Delta }_{\min }$ and $[d{m}_x/d\Gamma {]}_{\max }$.