Exponential complexity of an adiabatic algorithm for an NP-complete problem

We prove an analytical expression for the size of the gap between the ground and the first excited state of quantum adiabatic algorithm for the 3-satisfiability, where the initial Hamiltonian is a projector on the subspace complementary to the ground state. For large problem sizes the gap decreases exponentially and as a consequence the required running time is also exponential.

Figure 1

Single-solution random 3-SAT with $\alpha =4.5$. Empty squares are numerically calculated gaps, full circles (overlapping with squares) is the theoretical formula (9) (with numerically calculated ${\gamma }_{-1}$ and ${\gamma }_{-2}$). Dashed line is $1∕\left(2\sqrt{N}\right)$.

Figure 2

Binomial 3-SAT. Full circles are theoretical prediction for $f\left(n\right)$ using Eq. (11), empty squares (overlapping with full circles) are numerical result for full diagonalization. In the bottom figure we show for the same data the difference between the theory and the numerics. Dashed line is $1∕2^n$. For comparison we also show in the top frame $f\left(n\right)$ (obtained by numerically calculating ${\gamma }_{-1}$ and ${\gamma }_{-2}$) for three different single-solution random 3-SAT ensembles (stars and triangles).