01350nas a2200145 4500008004100000245004800041210004800089260001500137300001200152490000700164520095400171100002001125700002401145856003501169 2015 eng d00aAdiabatic optimization without local minima0 aAdiabatic optimization without local minima c2015/05/01 a181-1990 v153 a 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.
1 aJarret, Michael1 aJordan, Stephen, P. uhttp://arxiv.org/abs/1405.7552