Quantum variational algorithms are swamped with traps

This paper investigates the trainability of variational quantum algorithms (VQAs), focusing on shallow, local models. It challenges the prevailing focus on barren plateaus as the primary obstacle to VQA trainability. The authors prove that even shallow VQAs, lacking barren plateaus, possess a superpolynomially small fraction of local minima near the global minimum, hindering trainability without a good initial parameter guess. Using a statistical query framework, they demonstrate the impossibility of noisy optimization for a wide class of quantum models with a subexponential number of queries. Numerical simulations on various problem instances confirm these theoretical findings.

Eric R. Anschuetz, Bobak T. Kiani