Size Dependence of the Minimum Excitation Gap in the Quantum Adiabatic Algorithm

We study the typical (median) value of the minimum gap in the quantum version of the exact cover problem using quantum Monte Carlo simulations, in order to understand the complexity of the quantum adiabatic algorithm for much larger sizes than before. For a range of sizes $N\le 128$, where the classical Davis-Putnam algorithm shows exponential median complexity, the quantum adiabatic algorithm shows polynomial median complexity. The bottleneck of the algorithm is an isolated avoided-crossing point of a Landau-Zener type (collision between the two lowest energy levels only).

Figure 1

QMC results for the gap between the ground state and the first excited state as a function of the control parameter $\lambda$ for one instance with $N=64$. The region around the minimum value of the gap $\Delta E_{\min }$, which occurs at $\lambda ={\lambda }^{*}$, is blown up in the inset.

Figure 2

A log-linear plot of the median complexity of the exact cover problem using the (classical) DPLL algorithm as a function of $N$. The straight line fit works well demonstrating that the complexity increases exponentially with $N$ even for quite modest sizes. This figure is for samples with a USA, but the data for all samples (with the same number of clauses $M$) are very similar. The inset plots the same data on a log-log scale. The pronounced curvature shows that the data cannot be fitted to a power law.

Figure 3

A log-linear plot of the time-dependent correlation function for an instance with $N=128$ near the minimum gap. The energy gap is the negative of the slope at large values of $\tau$. The number of time slices was $L_{\tau }=300$. The error bars were estimated by repeating the runs many (typically 100) times.

Figure 4

A log-log plot of the median of the minimum gap as a function of the number of bits $N$ up to $N=128$. From the satisfactory straight line fit, it is seen that the median $\Delta E_{\min }$ decreases as a power law $N^{-\mu }$, with $\mu =0.73\pm 0.06$. The number of instances is 50 except for $N=64$ for which it is 45. The inset shows a log-linear plot. The pronounced curvature shows that the behavior is not exponential for this range of sizes, in contrast to the classical DPLL algorithm, data for which are shown in Fig. 2.

Figure 5

The gap $\Delta E(\lambda )$ (blue) and $-d^2{E}_0/d{\lambda }^2$ (red) against $\lambda$ for an instance with $N=128$. Solid lines are cubic interpolations. The location of the minimum gap ${\lambda }^{*}=0.6306$ is, within a margin of error, equal to the maximum of $-d^2{E}_0/d{\lambda }^2$ at $\lambda =0.6311$ (both shown by vertical dashed lines).