From Barren Plateaus to SPSA Optimization in Variational Quantum Eigensolvers
Abstract
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 has received comparatively less attention. 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 bounds for the SPSA gradient estimator, introduce a signal-to-noise ratio (SNR) defined as the ratio of the gradient energy to the mean squared error of the estimator, and establish convergence guarantees for SPSA under finite-shot measurements. Our results show that, under the proposed parameter schedules, the number of iterations sufficient to guarantee a fixed relative first-order stationarity level scales polynomially with the inverse of the intrinsic gradient energy. Consequently, when this energy decays exponentially under BP, the resulting guaranteed iteration complexity and total measurement budget both grow exponentially with the number of qubits.
Related
- Pointwise boundary observation in geometric optimization problems associated to variational inequalities
- Eigensolvers for polynomial roots and tensor decomposition
- From Variational Optimization to Flow-Based Transport: Posterior-Geometry Regularization for Ill-Conditioned Data Assimilation
- Real-Arithmetic Sketched Eigensolvers for Symmetric Matrices
- Hybrid Variational Quantum Circuits for Multivariate Regression and High-Dimensional Data Reconstruction
BibTeX
@misc{qin2026from,
title = {{From Barren Plateaus to SPSA Optimization in Variational Quantum Eigensolvers}},
author = {Zhen Qin},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2608.09810},
eprint = {2608.09810},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.09810},
}
RIS
TY - UNPB
TI - From Barren Plateaus to SPSA Optimization in Variational Quantum Eigensolvers
AU - Zhen Qin
PY - 2026
DA - 2026/10/28
PB - arXiv
DO - 10.48550/arxiv.2608.09810
UR - https://arxiv.org/abs/2608.09810
AB - 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 has received comparatively less attention. 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 bounds for the SPSA gradient estimator, introduce a signal-to-noise ratio (SNR) defined as the ratio of the gradient energy to the mean squared error of the estimator, and establish convergence guarantees for SPSA under finite-shot measurements. Our results show that, under the proposed parameter schedules, the number of iterations sufficient to guarantee a fixed relative first-order stationarity level scales polynomially with the inverse of the intrinsic gradient energy. Consequently, when this energy decays exponentially under BP, the resulting guaranteed iteration complexity and total measurement budget both grow exponentially with the number of qubits.
ER -