Gradient Scalability and Taylor Surrogation of Quantum Cost Landscapes

Abstract

Variational Quantum Algorithms are promising candidates for near-term quantum computing, yet they face scalability challenges due to barren plateaus, where gradients vanish exponentially relative to system size. Recent conjectures suggest that avoiding these plateaus might inherently lead to classical simulability, thereby limiting the opportunities for quantum advantage. In this work, we advance the theoretical understanding of the relationship between gradient scalability at initialization and the computational complexity of variational quantum algorithms. We first present the Taylor surrogate, a classical simulation technique that matches Pauli path runtime guarantees on near-Clifford regions while offering runtime advantages in specific regimes. Leveraging this surrogate, we prove that beyond previously established classically simulable regions, the computational complexity is at least super-polynomial. Next, we introduce the Linear Clifford Encoder, a classically efficient ansatz modifier that ensures constant-scaling gradients within landscape regions close to Clifford circuits. Finally, numerical experiments on these modified landscapes provide preliminary empirical evidence of a transition zone where constant-scaling gradients may decay polynomially in super-polynomially complex regions rather than exponentially. These findings suggest speculative instances where non-vanishing gradients and super-polynomial complexity could potentially coexist, vindicating the need for future formal proofs.

12 pages, 6 figures, 54 pages of supplementary material

References in corpus (18)

• Challenges and Opportunities in Quantum Machine Learning
• Barren Plateaus in Variational Quantum Computing
• Theory of overparametrization in quantum neural networks
• Does provable absence of barren plateaus imply classical simulability?
• Representation Learning via Quantum Neural Tangent Kernels
• On the practical usefulness of the Hardware Efficient Ansatz
• Hamiltonian variational ansatz without barren plateaus
• Analytic theory for the dynamics of wide quantum neural networks
• Classical surrogates for quantum learning models
• Absence of barren plateaus in finite local-depth circuits with long-range entanglement
• Trainability Enhancement of Parameterized Quantum Circuits via Reduced-Domain Parameter Initialization
• Variational quantum simulation: a case study for understanding warm starts
• Tight and Efficient Gradient Bounds for Parameterized Quantum Circuits
• Classically estimating observables of noiseless quantum circuits
• Reduction of finite sampling noise in quantum neural networks
• Lie-algebraic classical simulations for quantum computing
• Adaptive variational preparation of the Fermi-Hubbard eigenstates
• A Quantum Algorithmic Approach to Multiconfigurational Valence Bond Theory: Insights from Interpretable Circuit Design