Barren plateaus swamped with traps

Two main challenges preventing efficient training of variational quantum algorithms and quantum machine learning models are local minima and barren plateaus. Typically, barren plateaus are associated with deep circuits, while shallow circuits have been shown to suffer from suboptimal local minima. We point out a simple mechanism that creates exponentially many low-quality local minima specifically in the barren plateau regime. These local minima are trivial solutions that optimize only a few terms in the loss function, leaving the rest on their barren plateaus. More precisely, we show the existence of approximate local minima, optimizing a single loss term, and conjecture the existence of exact local minima, optimizing only a logarithmic fraction of all loss function terms. One implication of our findings is that many, if not most, regions with large gradients are vicinities of poor local minima. This highlights additional challenges in finding efficient initialization strategies.