Computational Bottlenecks of Quantum Adiabatic Annealing

Quantum annealing in a transverse field with rate $d\Gamma/dt$ inversely proportional to the system size $N$ suppresses non-adiabatic transitions for fully connected spin glass such as the Sherrington-Kirpatrick (SK) model at the quantum critical point. This alone is not sufficient to ensure that the problem is solvable in polynomial time. I conjecture the appearance of small gaps associated with macroscopic tunneling events deep in the spin glass phase. This effect is demonstrated rigorously for the annealing of a toy model that shares a set of crtical exponents with SK model: Hopfield network with two Gaussian patterns. It presents with $0.15 \ln N$ additional bottlenecks with gaps that scale as a stretched exponential $\exp\bigl[-c(N\Gamma)^{3/4}\bigr]$. Further, I extend the analysis to the $\rho$-landscapes model (random energy model with correlations) which more faithfully represents real spin glasses.