Exponential complexity of the quantum adiabatic algorithm for certain satisfiability problems

We determine the complexity of several constraint satisfaction problems using the quantum adiabatic algorithm in its simplest implementation. We do so by studying the size dependence of the gap to the first excited state of “typical” instances. We find that, at large sizes $N$, the complexity increases exponentially for all models that we study. We also compare our results against the complexity of the analogous classical algorithm WalkSAT and show that the harder the problem is for the classical algorithm, the harder it is also for the quantum adiabatic algorithm.

Figure 1

Gap to the first excited state as a function of $s$ for one instance of the locked 1-in-3 SAT problem. The line is a quadratic fit to the data points from which the location, $s=0.523$, and value, $\Delta E_{\text{min}}=0.207$, of the minimum gap are obtained. Here, $N=64$ and $\beta =1024$.

Figure 2

Energy gaps to even (solid, red) and odd (dashed, blue) excited states for an $N=16$ instance of the locked 2-in-4 problem, which has bit-flip symmetry as discussed in the text. The dotted line shows a characteristic value of another important energy scale in the problem—temperature. In the region where the gap to the first even state has a minimum, the gap to the first odd state becomes very small and is inevitably thermally populated. Hence odd-odd gaps appear in this region as well as even-even gaps. This is the reason why we use a nonstandard Monte Carlo algorithm for this problem, which projects out the symmetric subspace, so only even-even gaps are present in the data. The figure also shows the gap obtained from the even-subspace projected QMC in the vicinity of the minimum. It agrees with exact diagonalization within the error bars.

Figure 3

Log-linear plot of a time-dependent correlation function for an instance of the locked 1-in-3 SAT problem with $N=64$ spins, $\beta =1024$, near the minimum gap at $s=0.54$. The energy gap is the negative of the slope at large values of imaginary time $\tau$. A fit gives $\Delta E=0.037$.

Figure 4

Median minimum gap on a log-linear scale for the locked 1-in-3 problem. The straight-line fit is good, indicating the exponential complexity of the QAA for this problem.

Figure 5

Median minimum gap on a log-log scale for the locked 1-in-3 problem. The straight-line fit is extremely poor, indicating that the minimum gap for this problem is not polynomial in the system size.

Figure 6

Median gap on a log-linear scale for the locked 2-in-4 problem. The straight-line fit is good, indicating the exponential complexity for this problem.

Figure 7

Median gap on a log-log scale for the locked 2-in-4 problem. The straight-line fit is poor, indicating that the complexity for this problem is not polynomial.