# Dynamical Lie Algebras Cannot Describe Shallow QAOA: Cragged Terrains, Barren Plateaus, and Empirical Hardness Models

arXiv: https://arxiv.org/abs/2608.04252 · HTML: https://mlsanity.com/paper/2608.04252/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 48 references that are in the map.
- First posted on arXiv 4 Aug 2026.

## Builds on (most cited first, 11 of 11)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [Optuna: A Next-generation Hyperparameter Optimization Framework](https://mlsanity.com/paper/1907.10902/) (2019)
- [Variational Quantum Algorithms](https://mlsanity.com/paper/2012.09265/) (2020)
- [Barren plateaus in quantum neural network training landscapes](https://mlsanity.com/paper/1803.11173/) (2018)
- [A Random Forest Guided Tour](https://mlsanity.com/paper/1511.05741/) (2015)
- [Equivalence of quantum barren plateaus to cost concentration and narrow gorges](https://mlsanity.com/paper/2104.05868/) (2021)
- [A Unified Theory of Quantum Neural Network Loss Landscapes](https://mlsanity.com/paper/2408.11901/) (2024)
- [A Maximum Independent Set Method for Scheduling Earth Observing Satellite Constellations](https://mlsanity.com/paper/2008.08446/) (2020)
- [Fast Simulation of High-Depth QAOA Circuits](https://mlsanity.com/paper/2309.04841/) (2023)
- [Revisiting Random Forests in a Comparative Evaluation of Graph Convolutional Neural Network Variants for Traffic Prediction](https://mlsanity.com/paper/2305.19292/) (2023)

## Abstract (arXiv)

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 ~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.