Adiabatic Optimization and Dirichlet Graph Spectra

Several previous works have investigated the circumstances under which quantum adiabatic optimization algorithms can tunnel out of local energy minima that trap simulated annealing or other classical local search algorithms. Here we pursue two particular questions: (1) do adiabatic optimization algorithms always succeed in polynomial time for trivial optimization problems in which there is only one local minimum and (2) what characterizes the boundary between large- and small- gapped Hamiltonians? In addressing the first, we surprisingly find a counterexample in which the potential is a single basin on a graph, but the eigenvalue gap is exponentially small as a function of the number of vertices. For the second, we discover an equivalence between adiabatic interpolation Hamiltonians and the Dirichlet spectrum of weighted graphs. From this observation, we derive a number of bounds on the eigenvalue gap based on well-studied graph quantities. Additionally, in the context of quantum systems exhibiting path- and hypercube-like connectivity, we obtain a discrete analogue to the "fundamental gap theorem," yielding a tight lower bound to the eigenvalue gap in the presence of convex potentials.