Quantum variational algorithms are swamped with traps

Classical neural networks' remarkable trainability, despite optimizing complex nonconvex loss functions, motivates the exploration of analogous properties in quantum neural networks—specifically, variational quantum algorithms (VQAs). While some VQAs outperform classical algorithms in specific regimes, significant challenges exist. Previous work has highlighted the problem of barren plateaus in deep VQAs, leading to exponentially vanishing gradients. However, the trainability of shallow, local quantum models, exhibiting no barren plateaus, remained largely unexplored. This paper directly addresses this gap by investigating the trainability of such models, focusing on scenarios lacking good initial parameter guesses and significant model symmetry.

The paper reviews existing literature on the trainability of variational quantum algorithms. Earlier studies demonstrated untrainability in deep VQAs due to vanishing gradients and in nonlocal models due to poor local minima. However, the trainability of shallow, local models with local cost functions remained open. While promising numerical results existed, these often relied on favorable initializations or highly symmetric problem settings. This paper builds upon this prior work by investigating the untrainability of shallow, local models using statistical query learning theory and an analysis of loss landscapes. The authors summarize previous results concerning barren plateaus and poor local minima in Table 1, highlighting the novelty of their work in addressing the shallow, local regime.

The paper employs two complementary approaches to analyze VQA trainability. First, it leverages the statistical query (SQ) framework to analyze the impact of noise on optimization. The authors introduce quantum correlational statistical queries (qCSQs) and quantum unitary statistical queries (qUSQs), which model noisy queries to a quantum oracle. They demonstrate that numerous common variational optimizers, in the presence of noise, reduce to calls to an SQ oracle. By lower-bounding the SQ dimension of several function classes generated by shallow variational circuits (Table 2), they show that an exponential number of queries is required for learning, even with exponentially small noise. Second, the paper analyzes the loss landscapes of VQAs in the noiseless setting. Focusing on shallow, Hamiltonian-agnostic ansatzes, they prove that these landscapes are typically swamped with poor local minima. They introduce the concept of approximate local scrambling, a weaker condition than global scrambling, and show that ansatzes satisfying this condition have loss landscapes that converge to those of Wishart hypertoroidal random fields (WHRFs). This convergence is established by bounding the error in the joint characteristic function of the loss function, gradient, and Hessian. This allows for the inference of the distribution of critical points for local VQAs from the known properties of WHRFs. The analysis relies on assumptions concerning the approximate t-design property of locally scrambled circuits and the locality of the problem Hamiltonian.

The paper's central findings demonstrate the untrainability of a broad class of VQAs, even shallow ones that don't exhibit barren plateaus. The key results are: 1. **Statistical Query Lower Bounds:** Learning simple classes of functions generated by shallow variational circuits requires an exponential number of statistical queries (in problem size or light cone size), even with exponentially small noise. This holds for a variety of circuit architectures and measurement types. 2. **Poor Local Minima in Shallow VQAs:** Typical loss landscapes of shallow, local VQAs, even those without barren plateaus, are dominated by poor local minima far from the global optimum. The fraction of good local minima is superpolynomially small in the problem size. This arises from an underparameterization phenomenon where the number of parameters is much smaller than the local Hilbert space dimension. This is formalized in Theorem 1 and Corollary 2, connecting the distribution of critical points to Wishart hypertoroidal random fields. The degrees of freedom parameter *m* is approximately the sum of the local Hilbert space dimensions of the reverse light cones of terms in the Pauli decomposition of the Hamiltonian. 3. **Numerical Validation:** Numerical simulations on quantum convolutional neural networks (QCNNs) and variational quantum eigensolver (VQE) problems confirm the theoretical findings. In the teacher-student setting for QCNNs, training accuracy decreases dramatically as the number of qubits increases (Figure 2). For VQE, convergence to the ground state is only guaranteed when the number of parameters is exponential in the problem size (Figure 3).

The results significantly advance our understanding of VQA trainability beyond the barren plateau phenomenon. They show that the absence of barren plateaus doesn't guarantee trainability. The observed untrainability stems from the concentration of poor local minima, even in shallow circuits. This has important implications for the design and application of VQAs. However, the findings don't entirely negate the potential of VQAs. The authors suggest several avenues for potential future improvements: carefully designed ansatzes tailored to specific problems, exploitation of model symmetries, hierarchical ansatzes, and consideration of alternative VQA models like quantum Boltzmann machines.

This paper demonstrates that a wide class of variational quantum algorithms, including shallow circuits without barren plateaus, are often untrainable due to a concentration of poor local minima. The results, derived using both statistical query learning theory and loss landscape analysis, are supported by numerical simulations. While this significantly restricts the landscape of potentially practical VQAs, the authors identify promising avenues for future research, including leveraging problem-specific structure, model symmetries, and alternative VQA architectures.

The paper's theoretical analysis relies on certain assumptions about the ansatz structure (approximate local scrambling) and the problem Hamiltonian (locality). While these assumptions hold for many common VQA scenarios, they may not be universally applicable. The numerical simulations, while providing strong evidence, are limited in scope and may not capture all possible scenarios. The analysis primarily focuses on Hamiltonian-agnostic ansatzes; the behavior of Hamiltonian-informed ansatzes may differ.