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 investigate the even more basic question of whether adiabatic optimization

algorithms always succeed in polynomial time for trivial optimization problems

in which there are no local energy minima other than the global minimum.

Surprisingly, we 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. In this counterexample, the ground state wavefunction

consists of two "lobes" separated by a region of exponentially small amplitude.

Conversely, we prove if the ground state wavefunction is single-peaked then the

eigenvalue gap scales at worst as one over the square of the number of

vertices.