Gradient scalability and Taylor surrogation of quantum cost landscapes

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