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.

arXiv comment12 pages, 6 figures, 54 pages of supplementary material

References in corpus (42)

• Quantum Machine Learning
• A variational eigenvalue solver on a quantum processor
• Variational Quantum Algorithms
• Area laws for the entanglement entropy - a review
• Efficient classical simulation of slightly entangled quantum computations
• Barren plateaus in quantum neural network training landscapes
• Quantum Circuit Learning
• Improved Simulation of Stabilizer Circuits
• Parameterized quantum circuits as machine learning models
• Cost Function Dependent Barren Plateaus in Shallow Parametrized Quantum Circuits
• Evaluating analytic gradients on quantum hardware
• Expressibility and entangling capability of parameterized quantum circuits for hybrid quantum-classical algorithms
• Challenges and Opportunities in Quantum Machine Learning
• Connecting ansatz expressibility to gradient magnitudes and barren plateaus
• An initialization strategy for addressing barren plateaus in parametrized quantum circuits
• Layerwise learning for quantum neural networks
• Improved classical simulation of quantum circuits dominated by Clifford gates
• Simulation of quantum circuits by low-rank stabilizer decompositions
• Barren Plateaus in Variational Quantum Computing
• Theory of overparametrization in quantum neural networks
• Large gradients via correlation in random parameterized quantum circuits
• Entanglement Devised Barren Plateau Mitigation
• Higher Order Derivatives of Quantum Neural Networks with Barren Plateaus
• From pulses to circuits and back again: A quantum optimal control perspective on variational quantum algorithms
• 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
• Heisenberg XXZ Model and Quantum Galilei Group
• 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
• Quantifying the efficiency of state preparation via quantum variational eigensolvers
• 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
• Variational quantum state preparation via quantum data buses
• A Quantum Algorithmic Approach to Multiconfigurational Valence Bond Theory: Insights from Interpretable Circuit Design