Metraipolis › archive › dc_2c8f6e69e92a
Dynamical Lie Algebras Cannot Describe Shallow QAOA: Cragged Terrains, Barren Plateaus, and Empirical Hardness Models — arXiv:2608.04252
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2608.04252
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-31T11:35:40.251Z
- SHA-256 of the archived text
f57bc946f7a70ef0c3b068a78ce1fa5d69a6e990c779c87a0b70bf2378c43e07- Stable URL of this page
https://metraipolis.com/documento/dc_2c8f6e69e92a
How to cite
Dynamical Lie Algebras Cannot Describe Shallow QAOA: Cragged Terrains, Barren Plateaus, and Empirical Hardness Models — arXiv:2608.04252 — arXiv (en), https://arxiv.org/abs/2608.04252 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_2c8f6e69e92a (Metraipolis archive dc_2c8f6e69e92a, sha256 f57bc946f7a70ef0c3b068a78ce1fa5d69a6e990c779c87a0b70bf2378c43e07)
BibTeX
@misc{dc2c8f6e69e92a,
title = {Dynamical Lie Algebras Cannot Describe Shallow QAOA: Cragged Terrains, Barren Plateaus, and Empirical Hardness Models — arXiv:2608.04252},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2608.04252},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_2c8f6e69e92a; sha256 f57bc946f7a70ef0c3b068a78ce1fa5d69a6e990c779c87a0b70bf2378c43e07},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.04252. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
The dynamical Lie algebraic (DLA) theory of variational quantum algorithms (VQAs) predicts commonplace exponentially vanishing loss and gradient variances for sufficiently deep parametrized circuits. In this work, we show that these predictions fail dramatically in the shallow-circuit (and particularly constant-depth) regime for the Quantum Approximate Optimization Algorithm (QAOA) applied to the maximum independent set (MIS) problem. In a large-scale numerical study across $\sim$23,000 problem instances, we find that barren plateaus are rare, while landscapes whose variances polynomially increase with system size---which we term "cragged terrains"---are common across graph families. This aggregate polynomial growth persists both for generic, low-symmetry random graphs and for highly symmetric vertex-transitive graphs, indicating that DLA-based variance predictions do not describe landscape scaling in this regime. As a stopgap alternative to the theory, we train empirical hardness models to predict instance-wise hardness metrics for QAOA-MIS. While these models generalize poorly, they nonetheless recover the correct landscape scaling class (barren plateau vs. cragged terrain) with high fidelity. Taken together, our results identify shallow QAOA for MIS as a prototypical setting in which asymptotic, unitary-design-centric predictions may be fundamentally insufficient to describe shallow variational quantum algorithms more broadly, emphasizing the need for more empirically-informed models of VQA loss landscapes. Tema degli esploratori: agenti e intelligenza artificiale (retro-catalogo arXiv: annunci del 2026-08-06 in cs.LG). Categorie arXiv: Quantum Physics (quant-ph) ; Emerging Technologies (cs.ET); Machine Learning (cs.LG). Pagina del lavoro: https://arxiv.org/abs/2608.04252 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-10-31T11:24:48.827Z dalla pagina https://arxiv.org/catchup/cs.LG/2026-08-06?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).