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

Research Question and Approach

Variational Quantum Algorithms (VQAs) are often hindered by "barren plateaus," where the loss landscape becomes exponentially flat as the number of qubits increases, making optimization intractable. Current theoretical frameworks, such as Dynamical Lie Algebraic (DLA) theory, predict these plateaus by assuming that quantum circuits form approximate unitary 2-designs. However, these theoretical guarantees typically apply only to deep circuits. This study investigates whether these predictions hold for the shallow-circuit regime of the Quantum Approximate Optimization Algorithm (QAOA) applied to the Maximum Independent Set (MIS) problem.

The authors conducted a large-scale numerical analysis across approximately 23,000 problem instances, including various random graph families and vertex-transitive graphs. They compared the observed loss landscape variance against the predictions of DLA theory. Furthermore, they trained empirical hardness models (EHMs) to predict instance-wise landscape scaling, testing whether machine learning could identify the transition between barren plateaus and more favorable landscapes.

Findings: The Prevalence of Cragged Terrains

The study finds that barren plateaus are the exception rather than the rule in shallow QAOA-MIS. Instead, the authors identify "cragged terrains," characterized by a polynomial increase in loss landscape variance with system size. This behavior persists across diverse graph families, including both low-symmetry random graphs and highly symmetric vertex-transitive graphs.

These results demonstrate a fundamental departure from DLA-based predictions. Because DLA theory relies on asymptotic assumptions that may not be met in shallow circuits, it fails to capture the actual scaling behavior observed in near-term quantum applications. The empirical hardness models, while struggling to generalize to deeper circuits or larger qubit counts, successfully classified the landscape scaling class with high fidelity, suggesting that empirical approaches may be more reliable than current asymptotic theories for shallow VQAs.