


























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.
| Comments: | 12 pages, 6 figures, 54 pages of supplementary material |
| Subjects: | Quantum Physics (quant-ph); Computational Complexity (cs.CC); Machine Learning (cs.LG) |
| Cite as: | arXiv:2507.06344 [quant-ph] |
| (or arXiv:2507.06344v3 [quant-ph] for this version) | |
| https://doi.org/10.48550/arXiv.2507.06344 arXiv-issued DOI via DataCite |
From: Sabri Meyer [view email]
[v1]
Tue, 8 Jul 2025 19:10:46 UTC (2,918 KB)
[v2]
Thu, 18 Sep 2025 09:26:31 UTC (2,929 KB)
[v3]
Wed, 20 May 2026 10:06:53 UTC (2,925 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。