  One of the most important properties of classical neural networks is how
surprisingly trainable they are, though their training algorithms typically
rely on optimizing complicated, nonconvex loss functions. Previous results have
shown that unlike the case in classical neural networks, variational quantum
models are often not trainable. The most studied phenomenon is the onset of
barren plateaus in the training landscape of these quantum models, typically
when the models are very deep. This focus on barren plateaus has made the
phenomenon almost synonymous with the trainability of quantum models. Here, we
show that barren plateaus are only a part of the story. We prove that a wide
class of variational quantum models -- which are shallow, and exhibit no barren
plateaus -- have only a superpolynomially small fraction of local minima within
any constant energy from the global minimum, rendering these models untrainable
if no good initial guess of the optimal parameters is known. We also study the
trainability of variational quantum algorithms from a statistical query
framework, and show that noisy optimization of a wide variety of quantum models
is impossible with a sub-exponential number of queries. Finally, we numerically
confirm our results on a variety of problem instances. Though we exclude a wide
variety of quantum algorithms here, we give reason for optimism for certain
classes of variational algorithms and discuss potential ways forward in showing
the practical utility of such algorithms.
