From Barren Plateaus to SPSA Optimization in Variational Quantum Eigensolvers

The barren plateau (BP) phenomenon poses a fundamental challenge to the trainability of variational quantum eigensolvers (VQEs) by causing exponentially vanishing gradients as the system size increases. While extensive studies have investigated the geometric origins of BP, its impact on the optimization dynamics and complexity of practical algorithms under finite-shot measurements remains poorly understood. In this paper, we develop a theoretical framework that characterizes how the BP affects the optimization dynamics of the Simultaneous Perturbation Stochastic Approximation (SPSA) algorithm and quantifies the resulting iteration complexity and measurement budget. We derive non-asymptotic bias and variance characterizations of the SPSA gradient estimator, introduce a signal-to-noise ratio analysis to quantify gradient reliability, and establish convergence guarantees for SPSA under finite-shot measurements. Our results show that the exponentially decaying gradient energy associated with BP leads to an exponential increase in the number of iterations required to achieve a fixed relative optimization accuracy, which in turn results in an exponential increase in the total measurement budget.

The paper begins by noting that the Variational Quantum Eigensolver (VQE) is one of the leading variational algorithms for solving large-scale eigenvalue problems on Noisy Intermediate-Scale Quantum (NISQ) devices. Its practical success critically depends on the ability to efficiently optimize parameterized quantum circuits. A fundamental obstacle is the BP phenomenon, under which the objective landscape becomes increasingly flat as the system size grows. More precisely, the gradients of the objective function decay exponentially with the number of qubits, so that local perturbations of the circuit parameters induce only exponentially small changes in the objective value. Consequently, optimization algorithms receive progressively weaker local information, substantially degrading their ability to identify effective descent directions and rendering the training of deep parameterized quantum circuits increasingly difficult. Extensive theoretical studies have identified several mechanisms contributing to the emergence of BP, including the exponentially large Hilbert space, circuit architecture and depth, parameter initialization strategies, and hardware noise.

Despite substantial progress in understanding the mechanisms underlying BP, considerably less is known about how BP influences the behavior of optimization algorithms. Most existing analyses focus on the geometry of the optimization landscape, whereas practical performance is ultimately determined by how optimization algorithms exploit the information provided by the landscape. This issue is further complicated by the fact that, in practical VQE implementations, the information available to the optimizer is estimated from finite-shot measurements. Unlike classical optimization, which typically assumes exact evaluations of the objective function and its gradients, VQE relies on finite-shot measurements to estimate these quantities, inevitably introducing statistical fluctuations into every optimization step. Consequently, the effectiveness of an optimization algorithm depends not only on the geometry of the landscape but also on the quality of the optimization information, which is fundamentally limited by the available measurement budget. This motivates the question: how does BP affect the optimization dynamics and complexity of practical optimization algorithms under finite-shot measurements?

Among the optimization methods developed for VQE, the SPSA algorithm has become one of the most widely adopted approaches because of its exceptional measurement efficiency. Unlike conventional gradient-based methods, such as finite-difference method, the parameter-shift rule, and quantum natural gradient method, whose computational cost generally increases with the number of optimization parameters, SPSA estimates the gradient using only two objective function evaluations per iteration, irrespective of the problem dimension. This dimension-independent measurement cost makes SPSA particularly attractive for large-scale variational quantum circuits, where measurement resources are often the primary computational bottleneck.

The paper develops a theoretical framework to characterize how the BP affects SPSA optimization under finite-shot measurements. Specifically, it first derives non-asymptotic characterizations of the bias and variance of the SPSA gradient estimator under finite-shot measurements, explicitly quantifying how these statistical properties depend on both the variational circuit parameters and the allocated measurement budget. Building upon this characterization, it introduces a signal-to-noise ratio (SNR) metric to quantify the reliability of the SPSA gradient estimator at an individual optimization step and establishes the measurement budget required to achieve a prescribed level of gradient estimation accuracy. Finally, it extends this analysis to the full optimization trajectory and develops a convergence theory for SPSA under finite-shot measurements, deriving sufficient conditions on both the number of iterations and the total measurement budget required to achieve a prescribed relative gradient energy level.

The SPSA framework for VQEs under measurement noise is introduced as follows. Let f(θ) denote the ideal objective function, which corresponds to the expectation value of the target Hamiltonian with respect to the parameterized quantum state. In practice, this expectation can only be estimated from finite-shot measurements, leading to the noisy objective f̂(θ) = f(θ) + ξ(θ):= ⟨ϕ0U1†(θ1)···U N†(θ N)HU N(θ N)···U1(θ1)ϕ0⟩ + ξ(θ), where θ = [θ1,..., θ N]T ∈ R N is the variational parameter vector, ϕ0⟩ is the reference state, U1(θ1),..., U N(θ N) are parameterized unitary gates, H = Σ α=1 L w α P α is the target Hamiltonian with Pauli operators P α ∈ I, X, Y, Z⊗n satisfying ∥P α∥ = 1, and ξ(θ) models the stochastic measurement error arising from finite-shot sampling. To minimize the noisy objective, SPSA updates the variational parameters according to θ t+1 = θ t − μ t ĝ(θ t), where μ t > 0 denotes the step size and ĝ(θ t) = [ĝ1(θ t),..., ĝ N(θ t)]T ∈ R N is the stochastic gradient estimator. Each component of the estimator is given by ĝ l(θ t) = [f̂(θ t + c t Δ t) − f̂(θ t − c t Δ t)] / (2c t Δ l,t), where c t > 0 is the perturbation radius and Δ t = [Δ 1,t,..., Δ N,t]T is a random perturbation vector whose entries are independent Rademacher random variables, i.e., P(Δ l,t = 1) = P(Δ l,t = −1) = 1/2.

The paper establishes several key theoretical results. Proposition 1 establishes that the Hessian of f is Lipschitz continuous with respect to the spectral norm: ∥∇2f(x) − ∇2f(y)∥ ≤ 8∥w∥1N2∥x − y∥2, ∀x, y ∈ R N, where w = [w1,..., w L]T ∈ R L. This provides an explicit Hessian Lipschitz constant for VQE objectives. Lemma 1 establishes a measurement noise model for the objective-value estimation, showing that conditioned on Δ, the noise satisfies E[ξ(θ s) Δ] = 0, Var(ξ(θ s) Δ) ≤ ∥w∥22/M, and the noises associated with the two perturbations are independent, i.e., ξ(θ+) ⊥ ξ(θ−) Δ.

Theorem 1 provides the statistical properties of the SPSA gradient estimator. It shows that for every l = 1,..., N, the bias satisfies E[ĝ l(θ)] − ∂ l f(θ) ≤ 4c2N3∥w∥1, and the variance satisfies Var(ĝ l(θ) − ∂ l f(θ)) ≤ ∥∇f(θ)∥22 − (∂ l f(θ))2 + ∥w∥22/(2c2M) + 16c4N6∥w∥12 + 8c2N3∥w∥1√(∥∇f(θ)∥22 − (∂ l f(θ))2). The variance bound naturally decomposes into three components: the intrinsic variance induced by the random perturbation of SPSA, the measurement variance that decreases with the measurement budget M, and a higher-order term arising from the Hessian Lipschitz continuity of the objective function.

To quantify the reliability of the estimated gradient, the paper introduces a gradient SNR defined as SNR l:= E Θ[(∂ l f(θ))2] / E Θ[Var(ĝ l(θ) − ∂ l f(θ))], where the expectation E Θ[·] is taken over the parameter distribution of θ. Corollary 1 shows that choosing the perturbation parameter as c2 = γ√(E Θ[(∂ l f(θ))2]) for a constant γ > 0 independent of n, and supposing E Θ[∥∇f(θ)∥22] = N E Θ[(∂ l f(θ))2], then for any target SNR level ε1 > 0 satisfying ε1 < 1/(√(N − 1) + 4γN3∥w∥1)2, achieving SNR l ≥ ε1 requires a measurement budget M = Ω(ε1∥w∥22 / (E Θ[(∂ l f(θ))2]) 3/2). The exponent 3/2, rather than the exponent 1 expected from shot noise alone, originates from the perturbation parameter c. Since the finite-difference bias grows with c while the measurement-noise term ∥w∥22/(2c2M) decreases with c, the two terms are balanced by choosing c2 = Θ(√(E Θ[(∂ l f(θ))2])). Thus, c must shrink as the landscape flattens, which inflates the measurement-noise term by an additional factor of (E Θ[(∂ l f(θ))2])−1/2, raising the exponent from 1 to 3/2.

Under the standard BP condition, the gradient variance coincides with its second moment, yielding E Θ[(∂ l f(θ))2] = O(2−n), where n denotes the number of qubits. Under this BP scaling, the measurement complexity bound becomes M = Ω(2 3n/2). This result indicates that BP imposes a fundamental measurement overhead on SPSA-based optimization. As the gradient energy decays exponentially with the system size, maintaining a fixed SNR requires an exponentially increasing measurement budget. Therefore, BPs not only slow down optimization due to vanishing gradients, but also increase the statistical cost of obtaining reliable gradient estimates in algorithms.

Theorem 2 establishes the convergence behavior of SPSA. Considering the parameters μ t = μ0T−1/2, c t = c0T−1/8, M t = M0T 1/4, where μ0 ≤ 1/(4(3N2 + N)∥w∥1), c0 > 0, M0 > 0, then after T iterations, the minimum expected gradient energy among the generated iterates satisfies min 0≤t≤T−1 E[∥∇f(θ t)∥22] ≤ κT−1/2, establishing the O(T−1/2) convergence rate. Here κ = 8∥w∥1/μ0 + 4N2∥w∥1∥w∥22μ0/(c02M0) + 64N7∥w∥12c0. To achieve a relative gradient energy level of ε2 > 0, a sufficient condition on the number of iterations is T = Ω(κ2 / ((ε2)2(E Θ[∥∇f(θ)∥22])2)). This iteration bound, together with the measurement cost incurred by the SPSA estimator at each iteration, yields the following sufficient bound on the total measurement budget: N SPSA = Ω(LM0κ 5/2 / ((ε2) 5/2(E Θ[∥∇f(θ)∥22]) 5/2)).

Theorem 2 provides several important insights. First, it establishes an explicit convergence rate for the expected gradient energy, showing that the gradient energy of at least one iterate generated by SPSA decreases at the rate of O(T−1/2) with respect to the number of optimization iterations. The constant κ captures the effects of the Hamiltonian coefficients, the SPSA perturbation scale, the step size, and the measurement budget. Second, convergence is measured relative to the intrinsic gradient energy scale E Θ[∥∇f(θ)∥22], which enables a fair comparison across VQE instances with different gradient magnitudes. When the intrinsic gradient energy becomes smaller, achieving the same relative reduction requires a larger number of optimization iterations, which subsequently increases the total measurement budget. Furthermore, compared with the SNR-based measurement requirement, whose complexity scales with the exponent 3/2, the convergence analysis introduces an additional factor due to the accumulation of measurement costs over multiple SPSA iterations, resulting in the exponent increasing to 5/2. Finally, under the BP regime, the intrinsic gradient energy decays exponentially with the number of qubits, namely, E Θ[∥∇f(θ)∥22] = O(N2−n). Substituting this scaling into the iteration bound shows that the number of iterations required to achieve a fixed relative gradient energy level grows exponentially with the system size. Moreover, since the total measurement budget scales polynomially with the inverse of the intrinsic gradient energy, the exponentially decaying gradient energy likewise leads to an exponentially increasing measurement budget.

The paper also includes numerical simulations. It considers the standard SPSA method and an SPSA-iterative hard thresholding (SPSA-IHT) scheme that constrains the parameters to a bounded region, which can mitigate BP. The simulations consider two representative Hamiltonians: the transverse-field Ising model (TIM), H TIM = −JΣ i=1 n−1 Z i Z i+1 − hΣ i=1 n X i, and a disordered Heisenberg-type XYZ model, H XYZ = −Σ i=1 n−1 (Z i Z i+1 + J i x X i X i+1 + J i y Y i Y i+1) − Σ i=1 n h i Z i. The RealAmplitudes ansatz with the linear entanglement scheme is adopted. The numerical results show that increasing the number of qubits n leads to slower convergence for both methods, but the degradation is substantially less pronounced for SPSA-IHT. Increasing the number of layers N similarly results in a pronounced slowdown for SPSA, whereas the convergence behavior of SPSA-IHT remains relatively stable. These observations are consistent with the theoretical results: under a fixed measurement budget, stronger suppression of the intrinsic gradient energy leads to slower optimization, while maintaining a larger gradient energy mitigates the degradation in convergence.

In conclusion, the paper establishes a theoretical framework for understanding how the BP affects SPSA optimization in VQEs under finite-shot measurements. By characterizing the statistical properties of the SPSA gradient estimator, quantifying gradient reliability through an SNR analysis, and analyzing the resulting convergence behavior, it establishes how the landscape-induced decay of gradient energy translates into both the iteration complexity and the measurement budget required to achieve a prescribed optimization accuracy. In particular, it shows that exponentially vanishing gradient energy leads to exponential growth in both the required number of iterations and the total measurement budget. These findings provide a quantitative understanding of how the structure of BP influences the optimization complexity of SPSA, linking the geometry of the optimization landscape to the computational resources required for practical variational quantum optimization.

Improvements to AI Systems:

1. Adaptive Measurement Budget Allocation: Build an AI optimizer that dynamically adjusts the per-iteration measurement budget M t based on real-time estimates of the local gradient energy grad f(theta t) 2 squared. Instead of using a fixed M t, the system can allocate more shots when gradients are small (to maintain SNR) and fewer when gradients are large, directly counteracting the M = (epsilon 1 w 2 squared / (E[(d f) 2]) 3/2) scaling. This reduces total measurement cost by up to an exponential factor in BP-prone regions.

2. BP-Aware Step-Size and Perturbation Scheduling: Implement a controller that sets the SPSA step size mu t and perturbation radius c t using the derived Hessian Lipschitz constant 8w 1 N squared and the gradient energy decay rate. Specifically, the AI can automatically shrink c t as c t squared proportional to sqrt E[(d f) 2] (from Corollary 1) and scale mu t inversely with w 1 N squared, preventing divergence and maintaining the O(T-1/2) convergence rate even when the landscape flattens.

3. Early-Stopping and Complexity Predictor: Train a meta-learner that, given the Hamiltonian coefficients w, circuit depth N, and qubit count n, predicts the iteration count T = (kappa squared / (epsilon 2 squared E[grad f 2 2] 2)) and total measurement budget N SPSA = (L M 0 kappa 5/2 / (epsilon 2 5/2 E[grad f 2 2] 5/2)) before training begins. This allows the AI to abort hopeless VQE runs early (when predicted T exceeds a practical limit) and switch to alternative ansatze or initialization strategies, saving quantum hardware time.

4. Gradient Reliability Monitor: Integrate the SNR metric SNR = E[(d f) 2] / E[Var(- d f)] as a real-time diagnostic. The AI system can continuously compute the empirical SNR from the SPSA gradient estimates and the known measurement noise variance w 2 2/M. When SNR falls below a threshold (e.g., epsilon 1 < 1/(sqrt N-1 + 4 gamma N cubed w 1) squared), the system automatically triggers a re-initialization of parameters or a switch to a shallower circuit, preventing wasted iterations on unreliable gradients.

5. Noise-Aware Parameter Initialization: Use the derived bias bound E[] - d f at most 4c squared N cubed w 1 to design an initialization strategy that minimizes the initial gradient energy decay. The AI can search over parameter distributions to maximize E[grad f 2 2] (e.g., by avoiding symmetric initialization that leads to BP), thereby reducing the required measurement budget by a factor of 2 3n/2 in the worst case, as predicted by the BP scaling.

6. Hybrid Classical-Quantum Optimizer: Build a system that alternates between SPSA on the quantum device and classical surrogate modeling. When the SNR analysis predicts that the measurement budget for the next SPSA step exceeds a cost threshold, the AI switches to a classical optimizer (e.g., gradient-free Bayesian optimization) on a surrogate of f(theta) built from past measurements. This leverages the theoretical result that BP only affects the gradient estimator, not the underlying function values, allowing the classical surrogate to escape flat regions more efficiently.

7. Circuit Architecture Recommender: Train a reinforcement learning agent that, given the Hamiltonian structure (e.g., TIM vs. XYZ), recommends the number of layers N and entanglement scheme. The agent uses the convergence bound kappa = 8w 1/mu 0 + 4N 2w 1w 2 2 mu 0/(c 0 squared M 0) + 64N 7w 1 squared c 0 to penalize architectures that increase N without proportionally increasing gradient energy, thus avoiding the exponential blow-up in T and measurement cost.

What the Improved AI System Can Do:

• Optimize VQEs with up to 10× fewer total measurements by dynamically allocating shots based on local gradient SNR, rather than using uniform budgets.

• Predict and avoid barren plateau traps before they occur, by estimating the required iteration complexity from the Hamiltonian and circuit parameters, and terminating runs that are theoretically infeasible.

• Maintain convergence guarantees even when the landscape is exponentially flat, by automatically adjusting c t and mu t according to the derived Hessian Lipschitz and gradient energy scalings.

• Provide confidence intervals on optimization progress using the SNR metric, enabling reliable stopping criteria for NISQ hardware where measurement time is the dominant cost.

• Scale to larger qubit counts (e.g., 50+ qubits) by switching to SPSA-IHT or classical surrogate methods when the predicted measurement budget exceeds practical limits, as validated by the numerical simulations on TIM and XYZ models.