  Classical algorithms are often not effective for solving nonconvex
optimization problems where local minima are separated by high barriers. In
this paper, we explore possible quantum speedups for nonconvex optimization by
leveraging the global effect of quantum tunneling. Specifically, we introduce a
quantum algorithm termed the quantum tunneling walk (QTW) and apply it to
nonconvex problems where local minima are approximately global minima. We show
that QTW achieves quantum speedup over classical stochastic gradient descents
(SGD) when the barriers between different local minima are high but thin and
the minima are flat. Based on this observation, we construct a specific
double-well landscape, where classical algorithms cannot efficiently hit one
target well knowing the other well but QTW can when given proper initial states
near the known well. Finally, we corroborate our findings with numerical
experiments.
