PaperlayerView exact revision on arXiv

Source-linked AI summary

Beyond Barren Plateaus: Quantum Variational Algorithms Are Swamped With Traps

Eric R. Anschuetz, Bobak T. Kiani

arXiv:2205.05786v2quant-ph

TL;DR

The paper asks whether the absence of barren plateaus is sufficient for variational quantum algorithms to be trainable. It studies noisy optimization through statistical query theory and typical loss landscapes, finding that many shallow models remain untrainable and that barren-plateau-free landscapes do not guarantee trainability.

  • Problem

    Variational quantum models often lack the trainability of classical neural networks, while existing untrainability results have largely emphasized barren plateaus in deep models.

  • Method

    The paper analyzes quantum model trainability using statistical query learning theory, loss-landscape analysis, and numerical experiments across several problem instances.

  • Results

    Many shallow variational quantum models without barren plateaus have local minima far from the global optimum, while noisy learning can require exponentially many queries.

  • Takeaways & Limitations

    The absence of barren plateaus does not by itself vindicate a variational quantum model as trainable, narrowing the set of models with plausible practical utility.

  • Takeaways & Limitations

    The statistical-query hardness results use the correlational SQ setting, which is strictly weaker than the more general SQ setting.

Abstract

from arXiv · show

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.

1 Introduction

Variational quantum algorithms were expected to inherit some trainability advantages of classical neural networks, but prior evidence already showed failures in deep or nonlocal settings. This paper argues that shallow local models can also be difficult to train because their landscapes contain traps far from the global optimum.

  • Classical neural networks are notably trainable despite optimizing complicated, nonconvex loss functions.
  • Prior quantum untrainability results focused on vanishing gradients in deep models and poor local minima in nonlocal models.
  • Shallow local quantum models with local cost functions lacked comparable untrainability results, despite promising experiments using good initialization or highly symmetric problems.
  • The paper shows that shallow models without barren plateaus can still have local minima concentrated far from the global optimum, making training difficult without a good initial point.Figure 1 illustrates a bumpy landscape for a shallow QCNN teacher-student task, with the global minimum at the plot center.

2 Results

The results show that shallow, local variational quantum models can be untrainable even without barren plateaus, because good local minima are rare and noisy optimization is statistically hard. Numerical experiments confirm these obstacles in statistical-query learning, local VQAs, QCNN teacher-student learning, and VQE.

  • Statistical Query Framework: Exponentially many statistical queries can be required to learn function classes generated by shallow variational circuits under 2-design input distributions.The hardness applies to algorithms whose steps reduce to statistical queries and persists for constant noise, often even when noise is exponentially small.
  • Loss Landscapes of Local Variational Quantum Algorithms: Shallow, local VQA landscapes can contain a superpolynomially small fraction of local minima within any constant additive error of the ground state energy.The result follows from approximate local scrambling and the resulting convergence to Wishart hypertoroidal random fields.
  • Loss Landscapes of Local Variational Quantum Algorithms: In the shallow ansatz regime with q, l = O(polylog(n)) and extensive Hamiltonians, poor local minima arise even when barren plateaus are absent.Thus, large gradients do not guarantee good optimization performance.
  • Variational Quantum Eigensolvers: With a four-layer checkerboard ansatz capable of expressing the ground state, gradient descent nonetheless converges around poor local minima as the number of qubits increases.For a 14-qubit VQE, convergence to a global minimum or small additive error is not guaranteed until the ansatz has exponentially many parameters.

3 Discussion

The paper shows that many variational quantum algorithms remain untrainable under noise and poor loss landscapes, even beyond barren plateaus. It nevertheless identifies initialization, symmetries, structured ansatzes, and alternative model classes as reasons for optimism.

  • Main findings: Exponentially many statistical queries may be required to train broad classes of noisy variational quantum models.The result applies across the considered learning settings and often remains valid when query noise is exponentially small.
  • Main findings: Even at constant depth, variational quantum models can have superpolynomially many poor local minima despite only polynomially vanishing gradients.Numerical experiments confirm these theoretical results across several problem instances.
  • Reasons for optimism: Good initialization may make some algorithms practical by placing optimization within the global minimum’s region of attraction.The discussion highlights parameter concentration in QAOA as an example of useful initialization.
  • Reasons for optimism: Strong symmetries or known problem structure may reduce effective dimensionality and support efficient optimization or hierarchical ansatz construction.The paper notes that such structure can sometimes make the relevant Hilbert-space dimension much smaller.
  • Scope and implications: Quantum Boltzmann machines are outside the main framework and are efficiently trainable when the full quantum Gibbs state is observed.Numerical evidence also indicates trainability when the full state is not observed.
  • Scope and implications: The authors aim to focus research on quantum-model classes with genuine trainability potential and narrow the search for practical applications.The contribution is framed as further culling the landscape of potentially trainable variational quantum models.

4 Methods

The paper analyzes noisy variational optimization through quantum statistical queries and characterizes local-minimum distributions in Wishart hypertoroidal random fields. These tools connect query complexity, gradient estimation, and parameterization-dependent trainability.

  • Quantum statistical query models: Quantum correlational and unitary statistical queries model noisy access to target observables and unitaries, respectively.qCSQ returns bounded correlations with a target observable, while qUSQ addresses unitary compilation over input/output distributions.
  • Norm normalization: Cmax normalizes query tolerances and hardness bounds, equaling 1 for qUSQ but potentially decaying with qubit number for qCSQ.The normalization accounts for dimension-dependent changes in the query-induced norm.
  • Learning definitions: The qCSQ learning definition requires outputting an observable close to an unknown target in the distribution-dependent L2 norm.The analogous qUSQ definition concerns approximating an unknown target unitary.
  • Query-complexity bound: A qCSQ or qUSQ learner with statistical query dimension d requires at least (dτ^2 −1)/2 queries at tolerance Cmaxτ.The bound applies when hypotheses have distribution-dependent norm at most Cmax.
  • Optimization queries: Parameter-shift gradients can be evaluated using two qCSQ queries for the noisy expectation term.The other expectation term can be evaluated without statistical queries.
  • Loss-landscape analysis: WHRF landscapes have a superpolynomially small fraction of near-global local minima in the underparameterized regime.In the overparameterized regime, local minima are concentrated near the global minimum; Figure 4 presents the asymptotic distributions.

Competing Interests

The paper reports no competing interests.

  • The authors declare no competing interests.

1 Training Error Dominates in the Optimization of Variational Quantum Algorithms

For variational quantum algorithms, optimization error is the central training challenge after approximation and generalization errors can be bounded. The paper frames this challenge through empirical-risk minimization and its error decomposition.

  • Risk minimization: Variational learning searches a function class by minimizing empirical risk over a finite training dataset rather than directly evaluating expected risk.The expected risk requires access to the full data distribution.
  • Error decomposition: The excess-risk decomposition separates approximation, optimization, and generalization errors.The decomposition is obtained by comparing empirical and expected-risk minimizers.
  • Approximation and generalization: Approximation error measures hypothesis-class fit, while generalization error measures finite-dataset statistical error.Approximation can be bounded through expressivity assumptions, and generalization is often small when circuit complexity is limited relative to sample size.
  • Optimization error: Optimization error captures reduction of empirical risk and includes poor local minima and barren plateaus.The paper contrasts this with classical deep networks, where overparameterization can make fitting random data easier.
  • Main implication: The paper concludes that learning failures are typically tied to optimization once approximation and generalization errors are efficiently bounded.It compares this search difficulty loosely with the challenge of searching over Boolean functions.
  • Scope of the decomposition: The chosen excess-risk decomposition is neither unique nor necessarily tight.The authors selected it to relate quantum-machine-learning errors to classical counterparts and emphasize provable learning challenges.

2 Statistical Query Framework: Background and Additional Details

The statistical query framework studies learning through noisy oracle calls and supplies lower bounds on query complexity. The paper applies this framework to variational quantum models while stating important limits on its interpretation.

  • SQ background: Statistical query learning restricts algorithms to noisy queries and measures hardness by the number of queries needed to learn a function class.The paper reviews classical, correlational, quantum, and variationally relevant query settings.
  • Quantum motivation: Quantum variational algorithms naturally fit SQ analysis because sampling, gate errors, and state-preparation noise produce noisy evaluations.The paper considers queries for learning target Hamiltonians and target unitaries.
  • Application to variational circuits: The paper shows that simple variational-circuit function classes are exponentially difficult to learn in the considered SQ settings.It also connects these hardness results to optimization procedures used in practice.
  • Noise limitation: SQ hardness guarantees assume tolerance-bounded worst-case noise, which need not match the typically non-adversarial noise in quantum variational algorithms.Thus, SQ lower bounds provide a useful but idealized noise model.
  • Relation to optimization: SQ analysis does not directly describe loss landscapes, although noisy gradients and loss values can be implemented as statistical queries.Consequently, optimization difficulties can appear in the query-based implementation of an optimizer.
  • Class-wide hardness: Learning every function in a class is more restrictive than learning a specific function or small function set.The paper notes that shallow neural-network classes may be SQ-hard even though neural networks successfully learn particular real-world tasks.
  • Model-specific limitation: The hardness results use correlational SQ constructions based on orthogonal functions, and correlational SQ is strictly weaker than general SQ.Therefore, separations between the two models remain relevant to interpreting the results.

3 Proofs of Statistical Query Results

The section establishes statistical-query lower bounds for learning broad classes of shallow quantum circuits and unitary transformations. These bounds grow exponentially with circuit size or light-cone complexity under suitable input distributions and query tolerances.

  • Statistical query framework: The statistical query dimension measures the largest concept-class subset with pairwise bounded correlations under an input distribution.Theorem 3.3 converts this dimension into a lower bound on the number of qCSQ or qUSQ queries.
  • Single-layer models: A single layer of parameterized single-qubit gates with fixed global measurement requires 2^Omega(n) queries for tolerance greater than 3^(-beta n).Here beta = 1/2 − Omega(1).
  • Logarithmic-depth models: A logarithmic-depth two-qubit circuit class requires 2^Omega(n) queries when the tolerance exceeds 4^(-beta n), with beta = 1/2 − Omega(1).The result applies to ceil(log2 n) layers and a fixed single-qubit Pauli Z measurement.
  • Local circuit classes: For L layers of neighboring two-qubit gates in one dimension, the SQ dimension is at least 4^min(2L,n) − 1.The corresponding learning lower bound is 2^Omega(min(2L,n)) queries for constant tolerance independent of L and n.
  • Higher-dimensional lattices: In d-dimensional lattices, the measured qubit’s reverse light cone grows as Omega(L^d), producing SQ dimensions that scale exponentially with the accessible light cone.The construction uses a tree graph rooted at the measured qubit to realize distinct Pauli operators.
  • Unitary compiling: A single layer of single-qubit unitaries for unitary compiling has SQ dimension at least 4^n and requires 2^Omega(n) qUSQ queries above tolerance 4^(-beta n).The lower bound holds under any 2-design input distribution.

4 Shallow VQAs as Random Fields

The section models shallow variational quantum loss landscapes as random fields and analyzes when their local minima are far from the optimum. Under local-scrambling and independence assumptions, the resulting landscapes inherit poor-trainability behavior from WHRFs.

  • 4.2 Shallow VQAs Converge in Distribution to WHRFs: The analysis maps shallow VQA losses to Wishart hypertoroidal random fields, whose local-minima statistics characterize trainability beyond barren-plateau arguments.The paper uses the joint distribution of the loss, gradient norm, and Hessian determinant.
  • 4.1 Random Fields on Manifolds: WHRF loss landscapes undergo a phase transition governed by the overparameterization ratio gamma.When gamma is much less than one, local minima lie far from the global minimum; when gamma is at least one, they lie near it.
  • 4.2 Shallow VQAs Converge in Distribution to WHRFs: Theorem 4.1 proves weak convergence of the normalized VQA loss, gradient norm, and Hessian determinant to the corresponding WHRF distribution.The convergence is stated in Levy–Prokhorov distance, up to a specified asymptotic error.
  • 4.2 Shallow VQAs Converge in Distribution to WHRFs: A shallow local VQA has a superpolynomially small fraction of local minima within any constant additive error of the ground-state energy.This follows when the Pauli coefficients are Theta(1) and the theorem’s convergence assumptions hold.
  • Assumptions: The proof assumes local approximate t-design behavior, which is associated with locally scrambling gates and is not intended to cover Hamiltonian-informed highly symmetric ansatzes.The ansatz gates scramble regions of size l much smaller than n, so the models need not exhibit barren plateaus.
  • Assumptions: The analysis also assumes independence among reverse-light-cone contributions, a condition described as technically motivated and potentially relaxable.The authors expect an effective overparameterization ratio to govern approximately independent contributions.

5 Additional Numerical Experiments

Additional experiments show that shallow quantum models can remain difficult to train despite sufficient expressivity, with optimization often settling at poor local minima. Increasing depth or parameters improves performance, but reliable convergence may require exponential overparameterization.

  • 5.1 Teacher Student Learning with Checkerboard Ansatz: Exponential depth and parameter count are needed to always learn data generated by a shallow four-layer checkerboard circuit.The simulations used eight qubits, where smaller systems and shallower circuits were sometimes successfully learned.
  • 5.2 Random VQE model: Layer-wise optimization can converge to local minima at successive layers, even when the checkerboard ansatz can express the global minimum.The loss decreases smoothly only in the overparameterized regime, while adding layers can briefly produce training instabilities.
  • 5.3 XYZ Hamiltonian Model: The XYZ Hamiltonian is challenging for the tested ansatz: few layers produce poor critical points, while many layers improve optima but can introduce barren-plateau effects under finite shots.Table 1 reports normalized energy error and trace distance, averaged over 12 random initializations.

6 Details of Numerical Experiments

The numerical studies use several parameterized circuit families, optimizers, and VQE settings to probe trainability across teacher–student learning and Hamiltonian-ground-state problems. Experimental details include circuit parameterizations, initialization, training schedules, and alternative optimizer checks.

  • Implementation: The experiments use automatic differentiation in PyTorch, Nvidia RTX A6000 GPUs, and 32-bit analytic gradients unless otherwise stated.These settings avoid gradient-decay and barren-plateau effects associated with finite-precision sampling in the reported simulations.
  • QCNN experiments: The QCNN uses shared 2-local transformations, measures every other qubit, and has depth ⌈log2 n⌉ for n qubits.Teacher–student experiments predict the final green measurement from 512 computational-basis inputs using 16⌈log2 n⌉ parameters.
  • Checkerboard experiments: Checkerboard teacher–student experiments use 512 computational-basis states, Adam optimization, batch size 128, and 5000 training epochs.Training stops below loss 0.001, a threshold reached only in the overparameterized setting.
  • VQE experiments: Random-Hamiltonian VQE experiments use target Hamiltonians formed by conjugating a local n-qubit Hamiltonian with alternating products of two-qubit unitaries.The checkerboard ansatz directly optimizes Lie-algebra matrix entries representing fully parameterized 2-local unitaries.
  • VQE experiments: The random-Hamiltonian VQE experiment runs 30000 steps with vanilla gradient descent, while an Adam replication shows similar convergence behavior.The reported calculations use computer precision, providing a best-case optimization setting relative to noisy hardware sampling.
  • XYZ Hamiltonian experiments: The XYZ ansatz fully parameterizes single-qubit gates, uses Pauli Z ⊗Z terms between qubits, and shares parameters across layers.Parameter sharing reflects the model Hamiltonian’s approximate translational invariance.

7 Untrainability Beyond Gradient Descent

The paper examines whether modifying the loss or optimizer can overcome untrainability beyond ordinary gradient descent. Its analysis argues that bounded loss transformations may preserve separated traps, while second-order methods cannot escape local minima and broader guarantees remain limited to near-convex settings.

  • Changing the loss function: Loss-function changes are analyzed when the new loss bounds the original and paths from local to global minima must rise by a sufficiently large factor.Under these conditions, a local minimum remains outside a convex region around the global optimum in the transformed landscape.
  • Changing the optimization algorithm: Second-order optimization transforms gradients using a Hessian or Fubini–Study metric pseudoinverse but does not escape a local minimum.At a local minimum, the gradient term is zero, so the transformed update also vanishes.
  • Broader implications: Layer-wise training and related methods can alleviate barren plateaus without guaranteeing avoidance of landscape traps.The paper states that global-optimum guarantees require convex or close-to-convex settings.
Loading 2205.05786v2…