Pith. sign in

REVIEW 4 major objections 5 minor 60 references

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

T0 review · 4 major / 5 minor · reviewed 2026-08-08 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Shallow QAOA for maximum independent set produces loss landscapes whose gradient variance grows with qubit count, opposite to barren-plateau predictions.

desk verdict Honest, large-scale QAOA-MIS census with a plausible but unproven central claim: the BFGS training-path variance diagnostic means 'cragged terrain' may be an optimizer artifact rather than a landscape property. read the letter →

arxiv 2608.04252 v1 pith:6DQWZFJU submitted 2026-08-04 quant-ph cs.ETcs.LG

Harrison Copp , Charlton Li , Anžej Margeta-Cacace , Amy Qiao This is my paper · ORCID
classification quant-phcs.ETcs.LG
keywords barrenplateauscraggedterrainsQAOAmaximumindependentsetdynamicalLiealgebraempiricalhardnessmodelslosslandscapevarianceshallowvariationalcircuits
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper takes aim at the standard Lie-algebraic theory of barren plateaus, which predicts that variational quantum circuits with exponentially large dynamical Lie algebras should have loss landscapes whose variance decays exponentially with qubit count. It argues that for the Quantum Approximate Optimization Algorithm applied to maximum independent set at shallow, near-constant depths, that prediction is wrong: across roughly 23,000 instances, landscapes whose variance grows polynomially with system size (dubbed "cragged terrains") dominate, while true barren plateaus are rare. The evidence is numerical, with mean gradient variance measured along quasi-Newton training runs and clustered by graph features, and the aggregate growth survives across random graphs and over the full set of vertex-transitive graphs up to order 20. If the paper is right, asymptotic design-centric barren-plateau theory does not describe the shallow-circuit regime, and empirical hardness models may be a more reliable way to diagnose landscape scaling.

What carries the argument

The central object is the "cragged terrain," a loss landscape whose gradient variance grows polynomially with qubit number, contrasted with a barren plateau whose variance decays exponentially. The diagnostic is the mean gradient variance computed along the training path of a quasi-Newton optimizer, and the classification tool is a two-step clustering: instances are grouped by fifty-two graph features (degree statistics, spectra, treewidth, and similar quantities), and within each cluster the Pearson correlation of log variance against N is used as a finite-size scaling signature. The paper also isolates the theoretical machinery it is challenging: the DLA-based variance formula, which expresses the loss variance as a sum over simple ideals of the dynamical Lie algebra divided by their dimensions, valid only when the circuit forms an approximate unitary 2-design. That formula is what predicts exponential flatness; the numerical scaling signatures are what contradict it.

What would settle it

Compute the mean gradient variance for the same graphs and depths by uniformly sampling the full parameter domain instead of tracking a quasi-Newton path; if that uniform-sampling variance decays exponentially with N, the cragged-terrain classification collapses to a training-path artifact. A cheaper check is to rerun the cluster analysis with a different optimizer, such as Adam, and see whether the positive Pearson correlations persist.

Watch

Extended reading notes

Core claim

The paper's central claim is that shallow QAOA-MIS landscapes are, in the aggregate, cragged terrains rather than barren plateaus: the mean variance of the loss-gradient components grows with the number of qubits, with aggregate Pearson correlation r=0.977 for random graphs and r=0.941 for the complete set of vertex-transitive graphs up to order 20. Barren-plateau-like clusters, defined by exponential decay of variance with N, make up only about 1% of feature-based clusters at a threshold of r<−0.85, while cragged-terrain clusters at r>0.85 are about seventeen times more common. Because generic graphs in this setting have exponentially large dynamical Lie algebras, the observed polynomial variance growth directly contradicts what the DLA variance formula would predict if the circuits formed unitary 2-designs. The paper therefore concludes that the 2-design assumption, which requires circuit depth to grow with system size, is the point of failure, and that shallow VQA landscapes need empirically informed models rather than asymptotic Lie-algebraic ones.

Load-bearing premise

The load-bearing premise is that variance measured along a quasi-Newton training trajectory is a faithful probe of the whole landscape's scaling class; if gradients shrink superlinearly along the optimizer's path, the observed polynomial increase could be an artifact of the optimizer rather than a property of the loss landscape.

Editorial extensions

If this is right

  • If the scaling result holds, constant-depth QAOA-MIS does not face the exponential measurement-cost wall that barren plateaus impose, and the practical obstruction, if any, must come from the roughness of the landscape rather than its flatness.
  • DLA dimension alone cannot predict landscape scaling: the paper finds cragged terrains both for generic graphs whose DLAs quickly reach maximal dimension and for vertex-transitive graphs whose DLAs are smaller.
  • Empirical hardness models trained on individual hardness values reproduce the cluster-level scaling class with high fidelity, so they can serve as cheap diagnostics of barren-plateau versus cragged-terrain regimes even though they extrapolate poorly.
  • Constant-depth circuits become progressively worse approximations to unitary 2-designs as N grows, so design-centric variance formulas carry an error term that can grow exponentially through the observable's norm; the paper identifies this as the source of the discrepancy.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • One extension the authors leave implicit is that the feature correlations, with edge density and harmonic diameter associated with cragged terrains and von Neumann entropy and harmonic centrality associated with barren plateaus, could be turned into a testable analytic rule: graph families with high density and large diameter should exhibit polynomial variance growth, while low-entropy, centrally
  • The paper's observation that the cross-instance variance of the hardness metric scales with its mean suggests a gamma or log-normal statistical model of landscape roughness; fitting such a model at N>20 would distinguish power-law growth from log-normal growth, a distinction the paper flags as unresolved.
  • Because the argument against 2-designs rests on depth scaling rather than MIS-specific structure, the same cragged-terrain pattern should appear in other shallow two-local QAOA problems such as MaxCut; running the identical cluster analysis there would show whether the phenomenon is generic.
  • The reliance on quasi-Newton training-path samples is the main threat to the claim; a uniform-sampling replication is the natural next experiment, and the paper itself lists it as future work.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 5 minor

Summary. The paper reports a large numerical study of QAOA applied to maximum independent set (MIS) on roughly 23,000 instances, including random graphs up to 20 vertices and all vertex-transitive graphs up to order 20, at circuit depths p between 1 and 10. The authors define a mean gradient variance diagnostic computed along BFGS training trajectories and find that, for most graph-feature clusters, this variance increases with system size rather than decaying exponentially. They introduce the term 'cragged terrain' for landscapes whose variance grows polynomially with N, claim that barren plateaus are rare in this shallow-circuit regime, and conclude that DLA-based and design-centric barren-plateau theory does not describe shallow QAOA landscapes. The paper also trains random-forest, feedforward-neural-network, and graph-convolutional empirical hardness models; these predict in-distribution hardness well but generalize poorly to larger sizes, while allegedly recovering the empirical landscape-scaling classes.

Significance. If the central scaling claim were established, the paper would be a valuable empirical challenge to the prevailing DLA-based theory of barren plateaus, with implications for the practical use of shallow QAOA. The dataset is unusually broad for a numerical VQA study, the inclusion of the exhaustive vertex-transitive graph catalog is a genuine strength, and the authors are commendably explicit about several limitations. The empirical hardness model results are of moderate interest, mainly as a cautionary demonstration of poor cross-size generalization. However, the headline conclusion about the landscapes themselves currently rests on an optimizer-path diagnostic and on fits over a small range of N, so the significance is contingent on the additional controls and reframing described below.

major comments (4)
  1. [§III.C, Eq. (20); §V] The primary diagnostic is the mean gradient variance computed along BFGS training trajectories, not a uniform sample of the parameter space. Because BFGS convergence behavior (iteration counts, step sizes, restarts) changes with N, the observed positive scaling of Var along the path could reflect optimizer dynamics rather than intrinsic landscape growth. The paper's own Section V acknowledges that uniform-sampling checks are needed to ensure results are "not only induced by training dynamics," but the abstract and title state a claim about the landscapes themselves. This missing control is load-bearing; the authors should either add a uniform-sampling or multi-optimizer control, or explicitly reframe the headline as a statement about BFGS training paths.
  2. [§IV.B.1] The aggregate variance growth is presented as central evidence for 'cragged terrains,' but the text notes that exponential fits are 'statistically indistinguishable from a low-degree (less than or equal to quartic) polynomial increase for N≤20.' Given that the MIS cost is bounded and Popoviciu's inequality permits at most O(N^4) variance growth, a positive Pearson r over N≤20 is consistent with trivial finite-size behavior. The authors should report formal model comparisons (e.g., exponential vs. polynomial vs. log-normal fits with information criteria) and specify a falsifiable prediction at larger N; otherwise the claim of genuine polynomial or near-exponential growth is not established beyond the finite range studied.
  3. [§IV.B.3] The EHM 'recovery' of landscape scaling classes is not an independent validation: the same HDBSCAN clustering and Pearson-r thresholds from Section III.D are applied to the model predictions, and the models are trained on the same instance-wise variance values that define the clusters. The mean percent errors therefore measure consistency with the training relation, not predictive discovery of scaling classes. The abstract's claim that the models 'recover the correct landscape scaling class' should be softened or supported by a held-out protocol that does not reuse the clustering labels derived from the training data.
  4. [§I, §II.F, Appendix A] The title and abstract assert that DLA theory 'cannot describe' shallow QAOA, but the empirical study does not compute DLA-based variance predictions for the shallow circuits; it shows primarily that the 2-design condition required for the Ragone et al. formula is not satisfied in this regime. The paper's own Appendix A argues that the approximation error bound is vacuous because the Schatten 1-norm of the observable grows exponentially, which supports the inapplicability of the asymptotic theory, but it does not constitute a numerical contradiction of a DLA-derived variance at shallow depth. A corrected version should either compute the DLA-predicted variance where feasible (e.g., at small N) or phrase the conclusion as evidence that the design-centric assumptions break down, rather than as a refutation of DLA predictions in a regime where the theory was not claimed to apply.
minor comments (5)
  1. [§IV.B.1] There is a typo in 'these these statistics are, if anything, an overrepresentation'; the figure references 'Fig. IV B 1' are also unclear and should use the actual figure numbers (Figures 2 and 3).
  2. [§IV.A] References to 'Figure D' and 'Fig. C 2' appear inconsistent with the appendix figure numbering; all figure references should be unified and checked against the final layout.
  3. [§III.E.3] In the comparison of graph convolutional aggregation methods, 'GANs' should be 'GATs' or 'graph attention networks' to avoid confusion with generative adversarial networks.
  4. [§II.D, §III.C] The Lagrange multiplier is fixed at λ=1 in Eq. (13) with no sensitivity analysis; a brief study over λ would strengthen the claim that the observed scaling is not an artifact of this penalty choice.
  5. [§III.C, Eq. (20)] The notation Varθ[∂μC(θ)] mixes the variance over parameters with an average over gradient components; the definition should be written more explicitly, e.g., as (1/Nθ) Σ_i Varθ[∂C/∂θ_i], to avoid confusing the per-direction variance with the mean.

Circularity Check

1 steps flagged · score 2.0 of 10

No central circularity; only the EHM scaling-class 'recovery' reduces to its training target by construction.

  1. fitted input called prediction [Section IV.B.3, 'EHMs Predict Barren Plateau and Cragged Terrain Behavior' (Fig. 5)]
    "After running all graphs in each cluster through the feed forward neural network, the GCNN, and the random forest regression, the predictions maintain their exponential scaling signatures. Across all clusters with r < −0.85 or r > 0.95, the Pearson correlation coefficient of the predicted exponential fit matches the true coefficient with a mean percent error of 2.777%, 2.406%, and 2.208%, respectively."

    The scaling classes are defined by Pearson r values computed from the true target Varθ[∂μC] against N. The EHMs are regression models trained to output exactly that same target on the same in-distribution data (80/20 split from the same graph families and depths). A well-fitted regressor therefore reproduces the target values, and any statistic computed from the predicted values—including the cluster exponential fit and its r—is forced to approximate the corresponding statistic computed from the training targets. The 'recovery' of scaling classes is consequently a consistency check on the fitted regressor rather than independent evidence that the landscape classes are structural; it does not add support to the cragged-terrain finding beyond the original measurements.

full rationale

The central claim is an empirical finding, not a derived identity: roughly 23,000 QAOA-MIS instances were simulated, and the mean gradient variance along BFGS training paths was computed directly (Eq. 20). The aggregate positive Pearson correlations (r=0.977 for random graphs, r=0.941 for vertex-transitive graphs) are descriptive fits to those measured values, not outputs of a fitted parameter tuned to produce the scaling trend. The comparison to DLA theory invokes the external Ragone et al. closed form (Eq. 19) and the paper's own DLA-dimension measurements (Appendix B); the latter are independent numerical evidence, and the citation to the coauthor thesis [24] is supplementary to the paper's own Appendix A argument. The one circular-by-construction element is the EHM scaling-class 'recovery' in Section IV.B.3: the models are trained to regress exactly the Var target from which the scaling classes are defined, on the same in-distribution data, so the predicted Pearson r is forced to track the true r by the training objective. The paper explicitly frames this as checking whether predictions 'preserve' scaling signatures, and this step is not load-bearing for the landscape-scaling conclusion. The BFGS-path diagnostic is a genuine methodological limitation (the paper itself calls for uniform landscape sampling in Section V), but it is a measurement-protocol caveat, not a circularity.

Assumptions & free parameters 4 free parameters · 4 assumptions · 1 invented entities

The central scaling claim rests on a few chosen modeling and algorithmic parameters: lambda=1, HDBSCAN hyperparameters, BFGS iteration budget, and EHM hyperparameters. The most load-bearing axioms are the training-path variance diagnostic and the interpretation of short-range exponential fits as polynomial growth. The paper introduces one new named concept, 'cragged terrain', which is terminological rather than a physical entity.

free parameters (4)
  • Lagrange penalty multiplier lambda = 1
    Section III.C sets lambda=1 in the MIS cost Hamiltonian (Eq. 13). Landscape variance and scaling can depend on the penalty strength, but no lambda-dependence study is reported.
  • HDBSCAN cluster hyperparameters = min_cluster_size = dataset size/60 for random graphs, /30 for vertex-transitive; min_samples = half of min_cluster_size
    Section III.D chooses these by hand. Cluster composition determines the Pearson r values used to label barren plateau versus cragged terrain, so the scaling statistics depend on this choice.
  • BFGS max iterations = 1000
    Section III.C fixes the BFGS budget. Training-path gradient variance may depend on when optimization stops, and the paper uses this as its primary barren plateau diagnostic.
  • EHM hyperparameters = FFNN: 3 hidden layers (32,32,16), ReLU, Adam lr=0.006; GraphSAGE: 3 layers with top-K pooling
    Chosen via Optuna and empirical tuning. Model performance is not the central claim, but these choices affect the reported generalization results.
assumptions (4)
  • standard math The circuit ensemble must form an approximate unitary 2-design for the DLA variance formula (Eq. 19) to apply.
    Invoked in Section II.F to set up the DLA prediction that QAOA-MIS should exhibit barren plateaus. This is the background assumption from Ragone et al. and related work.
  • domain assumption Mean gradient variance sampled along the BFGS training path (Eq. 20) is a valid diagnostic for barren-plateau scaling.
    Section III.C states that variances along the training path are expected to be smaller than full-domain sampling, and the authors use this as a 'conservative indicator of flatness'. The entire scaling analysis rests on this surrogate.
  • domain assumption Clustering graphs by tabular features fixes problem structure so that N-scaling within a cluster is meaningful, and cluster Pearson r over N<=20 approximates the asymptotic scaling class.
    Section III.D applies HDBSCAN across 52 features and four circuit depths, with no multiple-testing correction, and interprets the resulting correlations as barren plateau or cragged terrain behavior.
  • ad hoc to paper Exponential fits over N<=20 can be interpreted conservatively as low-degree polynomial growth rather than truncated exponential decay.
    Section IV.B reports aggregate exponential correlations with r=0.977, but then states that these fits are statistically indistinguishable from a quartic polynomial for N<=20 and that a log-normal distribution cannot be discounted. The 'polyomal growth' label is the paper's chosen interpretation.
invented entities (1)
  • Cragged terrain
    purpose: A named landscape class in which loss or gradient variance grows polynomially with system size, in contrast to barren plateaus.
    This is a new term the paper introduces for an observed behavior. It has a precise definition only within this paper, and no independent falsifiable handle outside the reported data.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Dynamical Lie Algebras Cannot Describe Shallow QAOA: Cragged Terrains, Barren Plateaus, and Empirical Hardness Models." pith.science (2026). https://pith.science/paper/6DQWZFJU

@misc{pith2026260804252,
  author       = {Pith},
  title        = {Pith review of: Dynamical Lie Algebras Cannot Describe Shallow QAOA: Cragged Terrains, Barren Plateaus, and Empirical Hardness Models},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/6DQWZFJU}},
  note         = {Machine review of arXiv:2608.04252}
}
abstract

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.

Figures

Figures reproduced from arXiv: 2608.04252 by the authors.

Figure 1
Figure 1. Performance of the graph convolutional neural net [PITH_FULL_IMAGE:figures/full_fig_p009_1.png] view at source ↗
Figure 3
Figure 3. (a) Pearson r Distribution for Vertex Tran￾sitive Graphs. Pearson correlation coefficients of the mean variance of gradients against N for each cluster of random graphs. We a similarly left-skewed distribution, indicating that vertex transitive graphs also exhibit widespread cragged terrain behavior. (b) Aggregated Vertex Transitive Data also is a Cragged Terrain. Plotting the mean variance of the gradients for each… view at source ↗
Figure 4
Figure 4. Example of barren plateau and cragged ter￾rain cluster behaviors. the behavior observed here is specific to the shallow￾circuit, MIS-on-general-graphs setting and represents a novel departure from conventional expectations. 2. Graph Features Correlated with Baren Plateau / Cragged Terrain Behavior Several graph features are strongly predictive of BP and cragged terrain cluster membership (Table IV). For random graph… view at source ↗
Figures from the paper (3 more)
Figure 5
Figure 5. Figure 5: GCNN Predicts Barren Plateaus and Cragged Terrains. Example of the graph neural network predictions for a cluster of graphs exhibiting a barren plateau and cragged terrain. The clusters are the same as in Figures 4a and 4b: von Neumann entropy for p = 3 and edge densit…
Figure 7
Figure 7. Figure 7: FIG. 7. Mean Gradient Variance Model [PITH_FULL_IMAGE:figures/full_fig_p017_7.png]
Figure 9
Figure 9. Figure 9: FIG. 9 [PITH_FULL_IMAGE:figures/full_fig_p018_9.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

60 extracted references · 37 canonical work pages

  1. [1]

    Each of these trees makes their own pre- diction

    Random Forest Random forest regression is a supervised ensemble learning method that creates several decision trees, each trained on a random subset of data using a random sub- set of features. Each of these trees makes their own pre- diction. The final prediction is the average of each the prediction from each decision tree. We choose random forest regre...

    work page

  2. [2]

    7 Table I

    Mean gradient variance (here calculated along the 2 Preliminary testing was done on other optimizers such as Adam [36] and the modified conjugate natural gradient method (CQNG) [37], but BFGS seemed to be more performant than these alternatives. 7 Table I. Features computed for each graph. Bold features are integer-valued; unbolded features are continuous...

    work page

  3. [3]

    We use three hidden layers with 32, 32, and 16 neurons, respectively, each followed by the ReLU activation function

    Feed Forward Neural Network We use a feed forward neural network as a baseline neural network model. We use three hidden layers with 32, 32, and 16 neurons, respectively, each followed by the ReLU activation function. We found that increasing the number of layers and nodes had a minimal impact on the performance of the model. Based on results from Optuna ...

    work page

  4. [4]

    Cerezo, A

    M. Cerezo, A. Sone, T. Volkoff, L. Cincio, and P. J. Coles, Cost function dependent barren plateaus in shal- low parametrized quantum circuits, Nature Communica- tions12, 1791 (2021)

    2021

  5. [5]

    Naturally, one may worry that our choice of graph features does not completely capture the graph struc- ture

    Graph Convolutional Neural Network The empirical hardness models implemented thus far have been trained on a set of fifty-two tabular graph fea- tures. Naturally, one may worry that our choice of graph features does not completely capture the graph struc- ture. One solution to this problem comes in the form of a graph neural network-based empirical hardne...

    work page

  6. [6]

    cragged terrain

    Cragged Terrain Prevalence Using the clustering procedure of Sec. III D, we observe a striking asymmetry in the distribution of Pearson cor- relation coefficients (Fig. IV B 1). For randomly gener- ated graphs, only 0.998% of clusters satisfyr <−0.85 (indicative of barren plateaus), while 17.115% of clusters satisfyr >0.85 (cragged terrains). At a looser ...

    work page

  7. [7]

    Graph Features Correlated with Baren Plateau / Cragged Terrain Behavior Several graph features are strongly predictive of BP and cragged terrain cluster membership (Table IV). For random graphs, the von Neumann graph entropy is the most strongly BP-associated feature (aggregated Pear- sonr=−0.672), while edge density and harmonic di- ameter are the most s...

    work page

  8. [8]

    EHMs Predict Barren Plateau and Cragged Terrain Behavior Although the EHMs are trained on individual instance hardness values, it is natural to examine whether they preserve the exponentialN-scaling relationships charac- teristic of barren plateaus and the polynomial growth of cragged terrains (which is proffered in our analysis as exponential growth with...

    work page

Show all 60 references
  1. [9]

    Cerezo, A

    M. Cerezo, A. Arrasmith, R. Babbush, S. C. Benjamin, S. Endo, K. Fujii, J. R. McClean, K. Mitarai, X. Yuan, L. Cincio, and P. J. Coles, Variational Quantum Algo- rithms (2021), arXiv:2012.09265

    2021 arXiv

  2. [10]

    Larocca, S

    M. Larocca, S. Thanasilp, S. Wang, K. Sharma, J. Bia- monte, P. J. Coles, L. Cincio, J. R. McClean, Z. Holmes, and M. Cerezo, Barren Plateaus in Variational Quantum Computing (2025), arXiv:2405.00781

    2025 arXiv

  3. [11]

    J. R. McClean, S. Boixo, V. N. Smelyanskiy, R. Bab- bush, and H. Neven, Barren plateaus in quantum neural network training landscapes, Nature Communications9, 4812 (2018)

    2018

  4. [12]

    Leyton-Brown, E

    K. Leyton-Brown, E. Nudelman, and Y. Shoham, Empir- ical hardness models: Methodology and a case study on combinatorial auctions, Journal of the ACM56, 1 (2009)

    2009

  5. [13]

    Ragone, B

    M. Ragone, B. N. Bakalov, F. Sauvage, A. F. Kemper, C. Ortiz Marrero, M. Larocca, and M. Cerezo, A Lie algebraic theory of barren plateaus for deep parameter- ized quantum circuits, Nature Communications15, 7172 (2024)

    2024

  6. [14]

    Fontana, D

    E. Fontana, D. Herman, S. Chakrabarti, N. Kumar, R. Yalovetzky, J. Heredge, S. H. Sureshbabu, and M. Pis- toia, The Adjoint Is All You Need: Characterizing Barren Plateaus in Quantum Ans¨ atze (2024), arXiv:2309.07902

    2024 arXiv

  7. [15]

    N. L. Diaz, D. Garc ´ ıa-Mart ´ ın, S. Kazi, M. Larocca, and M. Cerezo, Showcasing a Barren Plateau Theory Beyond the Dynamical Lie Algebra (2023), arXiv:2310.11505

    2023 arXiv

  8. [16]

    E. R. Anschuetz, A Unified Theory of Quantum Neural Network Loss Landscapes (2025), arXiv:2408.11901

    2025 arXiv

  9. [17]

    Larocca, P

    M. Larocca, P. Czarnik, K. Sharma, G. Muraleedharan, P. J. Coles, and M. Cerezo, Diagnosing Barren Plateaus with Tools from Quantum Optimal Control, Quantum6, 824 (2022)

    2022

  10. [18]

    E. R. Anschuetz and B. T. Kiani, Quantum variational algorithms are swamped with traps, Nature Communica- tions13, 7760 (2022)

    2022

  11. [19]

    R. Mao, P. Yuan, J. Allcock, and S. Zhang, Qaoa- maxcut has barren plateaus for almost all graphs (2025), arXiv:2512.24577 [quant-ph]

    2025

  12. [20]

    Arrasmith, Z

    A. Arrasmith, Z. Holmes, M. Cerezo, and P. J. Coles, Equivalence of quantum barren plateaus to cost concen- tration and narrow gorges, Quantum Science and Tech- nology7, 045015 (2022)

    2022

  13. [21]

    Leyton-Brown, H

    K. Leyton-Brown, H. H. Hoos, F. Hutter, and L. Xu, Understanding the empirical hardness ofNP-complete problems, Communications of the ACM57, 98 (2014)

    2014

  14. [22]

    Farhi, J

    E. Farhi, J. Goldstone, and S. Gutmann, A Quan- tum Approximate Optimization Algorithm (2014), 14 arXiv:1411.4028

    2014 arXiv

  15. [23]

    L. T. Brady and S. Hadfield, Iterative Quantum Algo- rithms for Maximum Independent Set: A Tale of Low- Depth Quantum Algorithms (2023), arXiv:2309.13110

    2023 arXiv

  16. [24]

    Eddy and M

    D. Eddy and M. J. Kochenderfer, A Maximum Indepen- dent Set Method for Scheduling Earth Observing Satel- lite Constellations (2020), arXiv:2008.08446

    2020 arXiv

  17. [25]

    Yao and Y

    Y. Yao and Y. Hasegawa, Gradient analysis of barren plateau in parameterized quantum circuits with multi- qubit gates (2026), arXiv:2602.05288 [quant-ph]

    2026

  18. [26]

    Kashif, M

    M. Kashif, M. Rashid, S. Al-Kuwari, and M. Shafique, Alleviating barren plateaus in parameterized quantum machine learning circuits: Investigating advanced param- eter initialization strategies, in2024 Design, Automation & Test in Europe Conference & Exhibition(IEEE, 2024) p. 1–6

    2024

  19. [27]

    Glover, G

    F. Glover, G. Kochenberger, and Y. Du, A tuto- rial on formulating and using qubo models (2019), arXiv:1811.11538 [cs.DS]

    2019 arXiv

  20. [28]

    Ramos-Ruiz, A

    P. Ramos-Ruiz, A. M. Fuentes-Jim´ enez, J. E. Ramos- Ruiz, and I. Jim´ enez-Manchado, On the use of the quan- tum alternating operator ansatz in quantum-informed re- cursive optimization: A case study on the minimum ver- tex cover, AppliedMath6, 10.3390/appliedmath6020024 (2026)

    2026 doi

  21. [29]

    Cleve, D

    R. Cleve, D. Leung, L. Liu, and C. Wang, Near- linear constructions of exact unitary 2-designs (2016), arXiv:1501.04592 [quant-ph]

    2016 arXiv

  22. [30]

    Allcock, M

    J. Allcock, M. Santha, P. Yuan, and S. Zhang, On the dy- namical Lie algebras of quantum approximate optimiza- tion algorithms (2024), arXiv:2407.12587

    2024 arXiv

  23. [31]

    Wiersema, E

    R. Wiersema, E. K¨ okc¨ u, A. F. Kemper, and B. N. Bakalov, Classification of dynamical Lie algebras for translation-invariant 2-local spin systems in one dimen- sion (2023), arXiv:2309.05690

    2023 arXiv

  24. [32]

    A. Margeta-Cacace,Krylov-Lie Algebras for Variational Quantum Algorithms: Geometric, Depth-Aware Insights into Expressivity and Trainability, Master’s thesis, Texas Tech University (2026), 2607.02626

    2026 arXiv

  25. [33]

    Volkoff and P

    T. Volkoff and P. J. Coles, Large gradients via correla- tion in random parameterized quantum circuits, Quan- tum Science and Technology6, 025008 (2021)

    2021

  26. [34]

    Sohrabizadeh, W.-H

    A. Sohrabizadeh, W.-H. Lin, D. B. Tan, M. Cain, S.-T. Wang, M. D. Lukin, and J. Cong, GNN-Based Performance Prediction of Quantum Optimization of Maximum Independent Set: Special Session Paper, in 2024 ACM/IEEE International Conference On Com- puter Aided Design (ICCAD)(2024) ...

    2024

  27. [35]

    G. E. Crooks, Performance of the quantum approximate optimization algorithm on the maximum cut problem (2018), arXiv:1811.08419

    2018 arXiv

  28. [36]

    with a learning rate ofη= 0.006 to be most effective

  29. [37]

    J. R. Weggemans, A. Urech, A. Rausch, R. Spreeuw, R. Boucherie, F. Schreck, K. Schoutens, J. Min´ aˇ r, and F. Speelman, Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approach, Quantum6, 687 (2022)

    2022

  30. [38]

    S. S. Bhat, P. Wang, and U. Parampalli, Benchmarking Swarm Optimization Algorithms for Parameter Initial- ization in the Quantum Approximate Optimization Al- gorithm (2026), arXiv:2506.06790 [quant-ph]

    2026 arXiv

  31. [39]

    Pisanski, D

    T. Pisanski, D. Maruˇ siˇ c, P. Potoˇ cnik, A. Orbani´ c, B. Hor- vat, and P. Lukˇ siˇ c, The Encyclopedia of Graphs. At http://atlas.gregas.eu. Accessed on Aug 20, 2025

    2025

  32. [40]

    A. A. Hagberg, D. A. Schult, and P. J. Swart, Ex- ploring network structure, dynamics, and function us- ing networkx, inProceedings of the 7th Python in Sci- ence Conference (SciPy2008), G¨ ael Varoquaux, edited by T. Vaught and J. Millman (Pasadena, CA USA, 2008) pp. 11–15

    2008

  33. [41]

    Cazalset al., Identifying hard native instances for the maximum independent set problem on neutral atoms quantum processors (2025), arXiv:2502.04291

    P. Cazalset al., Identifying hard native instances for the maximum independent set problem on neutral atoms quantum processors (2025), arXiv:2502.04291

    2025 arXiv

  34. [42]

    W. H. Haemers, Eigenvalue techniques in design and graph theory (1979), https: doi.org/10.6100/IR41103

    1979 doi

  35. [43]

    Lykov, R

    D. Lykov, R. Shaydulin, Y. Sun, Y. Alexeev, and M. Pis- toia, Fast simulation of high-depth qaoa circuits, inPro- ceedings of the SC ’23 Workshops of The International Conference on High Performance Computing, Network, Storage, and Analysis, SC-W 2023 (ACM, 2023)

    2023

  36. [44]

    D. P. Kingma and J. Ba, Adam: A method for stochas- tic optimization, inProceedings of the 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015(2015)

    2015

  37. [45]

    Halla, Modified conjugate quantum natural gradient (2025), arXiv:2501.05847

    M. Halla, Modified conjugate quantum natural gradient (2025), arXiv:2501.05847

    2025

  38. [46]

    Nocedal and S

    J. Nocedal and S. J. Wright,Numerical Optimization, 2nd ed., Springer Series in Operations Research and Fi- nancial Engineering (Springer, New York, 2006)

    2006

  39. [47]

    R. J. G. B. Campello, D. Moulavi, and J. Sander, Density-based clustering based on hierarchical density es- timates, inAdvances in Knowledge Discovery and Data Mining, Lecture Notes in Computer Science, Vol. 7819, edited by J. Pei, V. S. Tseng, L. Cao, H. Motoda, and G. Xu (Sp...

    2013

  40. [48]

    Biau and E

    G. Biau and E. Scornet, A random forest guided tour (2015), arXiv:1511.05741 [math.ST]

    2015 arXiv

  41. [49]

    Akiba, S

    T. Akiba, S. Sano, T. Yanase, T. Ohta, and M. Koyama, Optuna: A Next-generation Hyperparameter Opti- mization Framework, inProceedings of the 25th ACM SIGKDD International Conference on Knowledge Dis- covery & Data Mining(ACM, Anchorage AK USA, 2019) pp. 2623–2631

    2019

  42. [50]

    W. L. Hamilton, R. Ying, and J. Leskovec, Inductive rep- resentation learning on large graphs, inNIPS(2017)

    2017

  43. [51]

    T. J. Ting, X. Li, S. Sanner, and B. Abdulhai, Revisiting random forests in a comparative evaluation of graph con- volutional neural network variants for traffic prediction, in2021 IEEE International Intelligent Transportation Systems Conference (ITSC)(IEEE, 2021) p. 1259–1265

    2021

  44. [52]

    Bechler-Speicher, I

    M. Bechler-Speicher, I. Amos, R. Gilad-Bachrach, and A. Globerson, Graph neural networks use graphs when they shouldn’t (2024), arXiv:2309.04332 [cs.LG]

    2024 arXiv

  45. [53]

    G. F. Royle and C. E. Praeger, Constructing the vertex- transitive graphs of order 24, Journal of Symbolic Com- putation8, 309 (1989)

    1989

  46. [54]

    Erdos and A

    P. Erdos and A. Renyi, On the evolution of random graphs, Publ. Math. Inst. Hungary. Acad. Sci.5, 17 (1960)

    1960

  47. [55]

    Watts and S

    D. Watts and S. Strogatz, Collective dynamics of ‘small- world’ networks, Nature393, 440–442 (1998)

    1998

  48. [56]

    Barab´ asi and R

    A.-L. Barab´ asi and R. Albert, Emergence of scal- ing in random networks, Science286, 509 (1999), 15 https://www.science.org/doi/pdf/10.1126/science.286.5439.509

    1999 doi

  49. [57]

    Braunstein, S

    S. Braunstein, S. Ghosh, and S. Severini, The laplacian of a graph as a density matrix: a basic combinatorial ap- proach to separability of mixed states, Annals of Combi- natorics , 291 (2006). Appendix A: Barren Plateau Theory: Limitations in the Shallow-Circuit Regime

    2006

  50. [58]

    F ramework The main result of Ragone et al

    Limitations of the Ragone et al. F ramework The main result of Ragone et al. [5] (Theorem 1 therein) expresses Varθ[C(θ)], initial stateρand observ- ableO, exactly: Varθ[C(θ)] = k−1X j=1 Pgj (ρ)Pgj (O) dim(gj) (A1) wheregis the dynamical Lie algebra induced by the PQC,g j ⊆gar...

  51. [59]

    TheBarab´ asi-Albertmodel uses preferential at- tachment to generate scale-free graphs with power-law degree distributions [48]

    Random Graph Models TheErd˝ os-R´ enyimodelG(n, p) places edges inde- pendently with probabilityp[46] TheW atts-Strogatz model begins with a regular ring lattice and rewires each edge independently with probabilityβ[47], producing graphs with high clustering coefficient and sm...

  52. [60]

    TheHaemers bound[34] on the independence num- ber isα(G)≤ −nλ1λn/(d2 min −λ 1λn), whereλ 1 ≥ · · · ≥ λn are adjacency eigenvalues andd min is the minimum degree

    Select Graph F eature Definitions Thevon Neumann entropyof a graphGwith LaplacianLisS(G) =− P i λi log2 λi, whereλ i are the eigenvalues of the density matrixρ(G)≡L/tr(L) [49]. TheHaemers bound[34] on the independence num- ber isα(G)≤ −nλ1λn/(d2 min −λ 1λn), whereλ 1 ≥ · · · ≥...

Pith tools

Reviewed August 8, 2026 · model on record in the stance chip above.