Quantum variational algorithms are swamped with traps

Classical neural networks are surprisingly trainable despite relying on optimization of nonconvex loss functions. Prior work showed that many variational quantum models (VQAs) are often not trainable, with most attention on barren plateaus that arise for very deep models. Here, we show barren plateaus are only part of the story. We prove that a wide class of shallow, local variational quantum models without barren plateaus have only a superpolynomially small fraction of local minima within any constant energy of the global optimum, rendering them untrainable without good initialization. Using a statistical query (SQ) framework, we further show that noisy optimization of broad classes of quantum models requires a sub-exponential to exponential number of queries, i.e., is impossible with a sub-exponential number. We numerically confirm these results on multiple problem instances, while identifying regimes and design principles that may offer optimism for certain variational algorithms.

Eric R. Anschuetz, Bobak T. Kiani