pith. sign in

arxiv: 2607.00945 · v1 · pith:E56PU5IXnew · submitted 2026-07-01 · 🪐 quant-ph

The Dynamical Lie Algebra of QAOA-MaxCut on the Complete Graph

Jonathan Allcock , Pei Yuan , Shengyu Zhang This is my paper

Pith reviewed 2026-07-02 12:07 UTC · model grok-4.3

classification 🪐 quant-ph
keywords QAOAMaxCutdynamical Lie algebrabarren plateausSchur-Weyl dualityvariance scalingcomplete graphquantum optimization
0
0 comments X

The pith

The variance of the QAOA-MaxCut loss function on complete graphs scales linearly with the number of qubits.

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

The paper derives an explicit form for the dynamical Lie algebra generated by the QAOA-MaxCut ansatz when the underlying graph is complete. It then uses this algebra to prove that the variance of the associated cost function grows linearly rather than decaying with qubit number. A sympathetic reader would care because barren plateaus, in which gradients vanish exponentially, are a known obstacle to training variational quantum circuits at scale. The argument proceeds by projecting the algebra generators onto subspaces furnished by Schur-Weyl duality between the unitary and symmetric groups, thereby determining the scaling without enumerating the full algebra.

Core claim

The dynamical Lie algebra of the QAOA-MaxCut circuit on the complete graph admits an analytical description obtained by projecting its generators onto the irreducible subspaces fixed by Schur-Weyl duality; this structure implies that the variance of the loss function is linear in the number of qubits, which rules out barren plateaus and settles the open question posed in reference [ASYZ26].

What carries the argument

Projection of the dynamical Lie algebra generators onto subspaces defined by Schur-Weyl duality between irreducible representations of the unitary and symmetric groups.

If this is right

  • The QAOA-MaxCut ansatz on complete graphs does not suffer from barren plateaus.
  • The loss-function variance scales linearly rather than exponentially with system size.
  • Representation-theoretic projections suffice to compute the variance without constructing the full algebra.
  • The open scaling question from [ASYZ26] is resolved in the affirmative for this family of instances.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same projection technique might be applied to other regular graphs or to different variational ansatze whose generators admit similar symmetry reductions.
  • If the linear scaling persists under small perturbations of the complete graph, it would suggest that dense connectivity itself protects against exponential gradient suppression.
  • The result supplies a concrete benchmark against which numerical studies of QAOA trainability on non-complete graphs can be compared.

Load-bearing premise

The projection of the dynamical Lie algebra generators onto subspaces defined by Schur-Weyl duality fully determines the variance scaling for the complete-graph case.

What would settle it

A direct numerical evaluation of the QAOA-MaxCut loss variance for n greater than or equal to 20 qubits on the complete graph that exhibits exponential decay rather than linear growth would falsify the claimed scaling.

read the original abstract

We give an analytical expression for the dynamical Lie algebra corresponding to the QAOA-MaxCut problem on complete graphs, and show that the variance of the associated loss function scales linearly in the number of qubits. This solves an open problem from [ASYZ26] and confirms that such systems do not exhibit barren plateaus. The proof is based on projecting the dynamical Lie algebra generators onto subspaces given by the Schur-Weyl duality between irreducible representations of the unitary and symmetric groups.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 0 minor

Summary. The paper derives an analytical expression for the dynamical Lie algebra of the QAOA-MaxCut problem on the complete graph K_n by projecting the cost and mixer generators onto the isotypic components furnished by Schur-Weyl duality for U(2) × S_n. It proves that the variance of the associated loss function scales linearly with the number of qubits n, thereby solving an open problem posed in [ASYZ26] and establishing the absence of barren plateaus for this symmetric instance.

Significance. If the derivation holds, the result is significant because it supplies an explicit, symmetry-based computation of the DLA and a parameter-free variance scaling that directly addresses trainability questions in variational quantum algorithms. The approach demonstrates how full S_n-invariance of both the cost Hamiltonian and the mixer allows the projected algebra to be read off block-by-block, providing a concrete, falsifiable prediction for the complete-graph case.

major comments (1)
  1. [Abstract] Abstract and proof outline: the manuscript asserts a complete proof via Schur-Weyl projection of the two generators, yet supplies neither the explicit form of the projected generators inside each isotypic component nor the resulting variance formula. Without these steps the claimed linear scaling var(loss) ∝ n cannot be verified and remains a load-bearing claim.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful reading of the manuscript. Below we respond to the single major comment.

read point-by-point responses

  1. Referee: [Abstract] Abstract and proof outline: the manuscript asserts a complete proof via Schur-Weyl projection of the two generators, yet supplies neither the explicit form of the projected generators inside each isotypic component nor the resulting variance formula. Without these steps the claimed linear scaling var(loss) ∝ n cannot be verified and remains a load-bearing claim.

    Authors: We agree that the abstract and proof outline would benefit from greater explicitness to allow immediate verification of the linear scaling. The full derivation in the manuscript applies the Schur-Weyl projectors (corresponding to the isotypic decomposition under U(2) × S_n) to the cost Hamiltonian (which is the complete-graph MaxCut operator) and the mixer (transverse-field X), producing explicit block-diagonal matrices in each irreducible component labeled by partitions of n. The variance formula is obtained by evaluating the second moment of the loss over the resulting DLA, which reduces to a sum over the dimensions of these blocks and yields the claimed linear scaling in n. In the revised version we will (i) augment the abstract with the leading-order form of the projected generators and the variance expression, and (ii) expand the proof outline (currently in Section II) to display the explicit matrix elements inside the dominant isotypic components together with the trace computation that produces var(loss) = Θ(n). These additions will make every step of the argument directly checkable without altering the underlying mathematics. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained via standard representation theory

full rationale

The paper's central derivation projects the QAOA generators onto isotypic components furnished by Schur-Weyl duality for U(2) × S_n, a classical external theorem in representation theory, then reads the variance scaling directly from the resulting block-diagonal algebra. Because the cost and mixer are fully S_n-invariant by construction, the invariance of each block follows immediately without any fitted parameters, self-defined quantities, or load-bearing self-citations. The reference to the open problem in [ASYZ26] identifies the target result rather than supplying a premise, and no step reduces the claimed linear variance to an input by definition or renaming.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Central claim rests on the applicability of Schur-Weyl duality to the QAOA generators on the complete graph; no free parameters or new entities are introduced in the abstract.

axioms (1)
  • standard math Schur-Weyl duality between irreducible representations of the unitary and symmetric groups
    Invoked to project the dynamical Lie algebra generators onto subspaces

pith-pipeline@v0.9.1-grok · 5598 in / 1089 out tokens · 19169 ms · 2026-07-02T12:07:03.533999+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

102 extracted references · 14 canonical work pages · 4 internal anchors

  1. [1]

    On the dynamical

    Allcock, Jonathan and Santha, Miklos and Yuan, Pei and Zhang, Shengyu , journal =. On the dynamical

  2. [2]

    arXiv preprint arXiv:2308.01432 , year=

    Lie-algebraic classical simulations for variational quantum computing , author=. arXiv preprint arXiv:2308.01432 , year=

    work page arXiv

  3. [3]

    Ragone, Michael and Bakalov, Bojko N and Sauvage, Fr. A. Nature Communications , volume=. 2024 , publisher=

    2024

  4. [4]

    Physical Review Letters , volume=

    Almost any quantum logic gate is universal , author=. Physical Review Letters , volume=. 1995 , publisher=

    1995

  5. [5]

    Efficient implementation of unitary transformations

    Efficient implementation of unitary transformations , author=. arXiv preprint arXiv:1901.03431 , year=

    work page internal anchor Pith review Pith/arXiv arXiv 1901

  6. [6]

    Journal of Mathematical Physics , volume=

    Product formulas for exponentials of commutators , author=. Journal of Mathematical Physics , volume=. 2013 , publisher=

    2013

  7. [7]

    Nagoya Mathematical Journal , volume=

    On everywhere dense imbedding of free groups in Lie groups , author=. Nagoya Mathematical Journal , volume=. 1951 , publisher=

    1951

  8. [9]

    Fixed depth

    K. Fixed depth. Physical Review Letters , volume=. 2022 , publisher=

    2022

  9. [10]

    A Trotter-Suzuki approximation for Lie groups with applications to

    Somma, Rolando D , journal=. A Trotter-Suzuki approximation for Lie groups with applications to. 2016 , publisher=

    2016

  10. [11]

    Classification of dynamical

    Wiersema, Roeland and K. Classification of dynamical. arXiv preprint arXiv:2309.05690 , year=

    work page arXiv

  11. [12]

    2013 , publisher=

    Lie groups, Lie algebras, and representations , author=. 2013 , publisher=

    2013

  12. [13]

    1996 , publisher=

    Lie groups beyond an introduction , author=. 1996 , publisher=

    1996

  13. [14]

    2008 , publisher=

    An introduction to Lie groups and Lie algebras , author=. 2008 , publisher=

    2008

  14. [15]

    Nature Communications , volume=

    Barren plateaus in quantum neural network training landscapes , author=. Nature Communications , volume=. 2018 , publisher=

    2018

  15. [16]

    arXiv preprint arXiv:2309.07902 , year=

    The Adjoint Is All You Need: Characterizing Barren Plateaus in Quantum Ansatze , author=. arXiv preprint arXiv:2309.07902 , year=

    work page arXiv

  16. [17]

    Characterizing barren plateaus in quantum ans

    Fontana, Enrico and Herman, Dylan and Chakrabarti, Shouvanik and Kumar, Niraj and Yalovetzky, Romina and Heredge, Jamie and Sureshbabu, Shree Hari and Pistoia, Marco , journal=. Characterizing barren plateaus in quantum ans. 2024 , publisher=

    2024

  17. [18]

    Showcasing a barren plateau theory beyond the dynamical

    Diaz, NL and Garc. Showcasing a barren plateau theory beyond the dynamical. arXiv preprint arXiv:2310.11505 , year=

    work page arXiv

  18. [19]

    1994 , publisher=

    Concrete mathematics: a foundation for computer science , author=. 1994 , publisher=

    1994

  19. [20]

    Real forms of simple

    Hota, Kaushalya Rani , year=. Real forms of simple

  20. [21]

    Proceedings of the twenty-eighth annual ACM symposium on Theory of computing , pages=

    A fast quantum mechanical algorithm for database search , author=. Proceedings of the twenty-eighth annual ACM symposium on Theory of computing , pages=

  21. [22]

    Proceedings 35th annual symposium on foundations of computer science , pages=

    Algorithms for quantum computation: discrete logarithms and factoring , author=. Proceedings 35th annual symposium on foundations of computer science , pages=. 1994 , organization=

    1994

  22. [23]

    Physical review letters , volume=

    Quantum algorithm for linear systems of equations , author=. Physical review letters , volume=. 2009 , publisher=

    2009

  23. [24]

    Nature Communications , volume=

    A variational eigenvalue solver on a photonic quantum processor , author=. Nature Communications , volume=. 2014 , publisher=

    2014

  24. [25]

    Nature Communications , volume=

    Cost function dependent barren plateaus in shallow parametrized quantum circuits , author=. Nature Communications , volume=. 2021 , publisher=

    2021

  25. [26]

    Nature Communications , volume=

    Noise-induced barren plateaus in variational quantum algorithms , author=. Nature Communications , volume=. 2021 , publisher=

    2021

  26. [27]

    PRX Quantum , volume=

    Entanglement-induced barren plateaus , author=. PRX Quantum , volume=. 2021 , publisher=

    2021

  27. [28]

    PRX Quantum , volume=

    Connecting ansatz expressibility to gradient magnitudes and barren plateaus , author=. PRX Quantum , volume=. 2022 , publisher=

    2022

  28. [29]

    Quantum , volume=

    Diagnosing barren plateaus with tools from quantum optimal control , author=. Quantum , volume=. 2022 , publisher=

    2022

  29. [30]

    Nature Reviews Physics , volume=

    Variational quantum algorithms , author=. Nature Reviews Physics , volume=. 2021 , publisher=

    2021

  30. [31]

    Nature , volume=

    Hardware-efficient variational quantum eigensolver for small molecules and quantum magnets , author=. Nature , volume=. 2017 , publisher=

    2017

  31. [32]

    Quantum approximate optimization is computationally universal

    Quantum approximate optimization is computationally universal , author=. arXiv preprint arXiv:1812.11075 , year=

    work page internal anchor Pith review Pith/arXiv arXiv

  32. [33]

    Quantum Information Processing , volume=

    On the universality of the quantum approximate optimization algorithm , author=. Quantum Information Processing , volume=. 2020 , publisher=

    2020

  33. [34]

    2012 , publisher=

    An introduction to linear algebra , author=. 2012 , publisher=

    2012

  34. [35]

    2004 , publisher=

    A treatise on algebraic plane curves , author=. 2004 , publisher=

    2004

  35. [36]

    Scientific Reports , volume=

    Multi-angle quantum approximate optimization algorithm , author=. Scientific Reports , volume=. 2022 , publisher=

    2022

  36. [37]

    Algorithms , volume=

    From the quantum approximate optimization algorithm to a quantum alternating operator ansatz , author=. Algorithms , volume=. 2019 , publisher=

    2019

  37. [38]

    A simple method for finding the inverse matrix of

    Rawashdeh, Edris Ahmad , journal=. A simple method for finding the inverse matrix of

  38. [39]

    SIAM Journal on Computing , volume=

    Quantum computation and lattice problems , author=. SIAM Journal on Computing , volume=. 2004 , publisher=

    2004

  39. [40]

    Quantum computation of

    Beals, Robert , booktitle=. Quantum computation of

  40. [41]

    A Quantum Observable for the Graph Isomorphism Problem

    A quantum observable for the graph isomorphism problem , author=. arXiv preprint quant-ph/9901029 , year=

    work page internal anchor Pith review Pith/arXiv arXiv

  41. [42]

    Advances in Cryptology—CRYPT0’95: 15th Annual International Cryptology Conference Santa Barbara, California, USA, August 27--31, 1995 Proceedings 15 , pages=

    Quantum cryptanalysis of hidden linear functions , author=. Advances in Cryptology—CRYPT0’95: 15th Annual International Cryptology Conference Santa Barbara, California, USA, August 27--31, 1995 Proceedings 15 , pages=. 1995 , organization=

    1995

  42. [43]

    npj Quantum Information , volume=

    Theoretical guarantees for permutation-equivariant quantum neural networks , author=. npj Quantum Information , volume=. 2024 , publisher=

    2024

  43. [44]

    Exploring entanglement and optimization within the

    Wiersema, Roeland and Zhou, Cunlu and de Sereville, Yvette and Carrasquilla, Juan Felipe and Kim, Yong Baek and Yuen, Henry , journal=. Exploring entanglement and optimization within the. 2020 , publisher=

    2020

  44. [45]

    arXiv preprint arXiv:2001.11897 , year=

    Learning unitaries by gradient descent , author=. arXiv preprint arXiv:2001.11897 , year=

    work page arXiv 2001

  45. [46]

    Quantum , volume=

    Efficient classical algorithms for simulating symmetric quantum systems , author=. Quantum , volume=. 2023 , publisher=

    2023

  46. [47]

    Journal of Mathematical Physics , volume=

    Controllability of symmetric spin networks , author=. Journal of Mathematical Physics , volume=. 2018 , publisher=

    2018

  47. [48]

    On the universality of

    Kazi, Sujay and Larocca, Martin and Cerezo, Marco , journal=. On the universality of. 2024 , publisher=

    2024

  48. [49]

    Nature Physics , volume=

    Restrictions on realizable unitary operations imposed by symmetry and locality , author=. Nature Physics , volume=. 2022 , publisher=

    2022

  49. [50]

    Physical Review Letters , volume=

    Rotationally invariant circuits: Universality with the exchange interaction and two ancilla qubits , author=. Physical Review Letters , volume=. 2024 , publisher=

    2024

  50. [51]

    1997 , publisher=

    Geometric control theory , author=. 1997 , publisher=

    1997

  51. [52]

    Controllability of quantum mechanical systems by root space decomposition of \

    Altafini, Claudio , journal=. Controllability of quantum mechanical systems by root space decomposition of \. 2002 , publisher=

    2002

  52. [53]

    Monbroussou, E

    Monbroussou, L. Trainability and expressivity of. arXiv preprint arXiv:2309.15547 , year=

    work page arXiv

  53. [54]

    PRX Quantum , volume=

    Theory for equivariant quantum neural networks , author=. PRX Quantum , volume=. 2024 , publisher=

    2024

  54. [55]

    Quantum Machine Intelligence , volume=

    Subtleties in the trainability of quantum machine learning models , author=. Quantum Machine Intelligence , volume=. 2023 , publisher=

    2023

  55. [56]

    Physical Review Research , volume=

    Entanglement devised barren plateau mitigation , author=. Physical Review Research , volume=. 2021 , publisher=

    2021

  56. [57]

    Scientific Reports , volume=

    Quantum neural network cost function concentration dependency on the parametrization expressivity , author=. Scientific Reports , volume=. 2023 , publisher=

    2023

  57. [58]

    Physical Review Letters , volume=

    Trainability of dissipative perceptron-based quantum neural networks , author=. Physical Review Letters , volume=. 2022 , publisher=

    2022

  58. [59]

    Physical Review X , volume=

    Absence of barren plateaus in quantum convolutional neural networks , author=. Physical Review X , volume=. 2021 , publisher=

    2021

  59. [60]

    Quantum , volume=

    Barren plateaus in quantum tensor network optimization , author=. Quantum , volume=. 2023 , publisher=

    2023

  60. [61]

    Nature Physics , volume=

    Limitations of optimization algorithms on noisy quantum devices , author=. Nature Physics , volume=. 2021 , publisher=

    2021

  61. [62]

    Physical Review Research , volume=

    Effects of noise on the overparametrization of quantum neural networks , author=. Physical Review Research , volume=. 2024 , publisher=

    2024

  62. [63]

    Physical Review A , volume=

    Importance of kernel bandwidth in quantum machine learning , author=. Physical Review A , volume=. 2022 , publisher=

    2022

  63. [64]

    Nature Computational Science , volume=

    The power of quantum neural networks , author=. Nature Computational Science , volume=. 2021 , publisher=

    2021

  64. [65]

    Physical Review Letters , volume=

    Barren plateaus preclude learning scramblers , author=. Physical Review Letters , volume=. 2021 , publisher=

    2021

  65. [66]

    Journal of Physics A: Mathematical and Theoretical , volume=

    On barren plateaus and cost function locality in variational quantum algorithms , author=. Journal of Physics A: Mathematical and Theoretical , volume=. 2021 , publisher=

    2021

  66. [67]

    The impact of cost function globality and locality in hybrid quantum neural networks on

    Kashif, Muhammad and Al-Kuwari, Saif , journal=. The impact of cost function globality and locality in hybrid quantum neural networks on. 2023 , publisher=

    2023

  67. [68]

    Quantum , volume=

    Quantum-assisted quantum compiling , author=. Quantum , volume=. 2019 , publisher=

    2019

  68. [69]

    PRX Quantum , volume=

    Exploiting symmetry in variational quantum machine learning , author=. PRX Quantum , volume=. 2023 , publisher=

    2023

  69. [70]

    Physical Review Research , volume=

    Quantum-optimal-control-inspired ansatz for variational quantum algorithms , author=. Physical Review Research , volume=. 2021 , publisher=

    2021

  70. [71]

    Nature Computational Science , volume=

    Theory of overparametrization in quantum neural networks , author=. Nature Computational Science , volume=. 2023 , publisher=

    2023

  71. [72]

    2006 , publisher=

    Introduction to Lie algebras , author=. 2006 , publisher=

    2006

  72. [73]

    https://quantumalgorithmzoo.org/ , volume=

    Quantum algorithm zoo , author=. https://quantumalgorithmzoo.org/ , volume=. 2021 , publisher=

    2021

  73. [74]

    Physics Reports , volume=

    A review on quantum approximate optimization algorithm and its variants , author=. Physics Reports , volume=. 2024 , publisher=

    2024

  74. [75]

    2008 , publisher=

    Quantum error correction and fault tolerant quantum computing , author=. 2008 , publisher=

    2008

  75. [76]

    PRX Quantum , volume=

    Focus beyond quadratic speedups for error-corrected quantum advantage , author=. PRX Quantum , volume=. 2021 , publisher=

    2021

  76. [77]

    Communications of the ACM , volume=

    Disentangling hype from practicality: On realistically achieving quantum advantage , author=. Communications of the ACM , volume=. 2023 , publisher=

    2023

  77. [78]

    Full classification of

    Aguilar, Gerard and Cichy, Simon and Eisert, Jens and Bittel, Lennart , journal=. Full classification of

  78. [79]

    Analyzing the Quantum Approximate Optimization Algorithm: Ans\"atze, Symmetries, and

    Kazi, Sujay and Larocca, Mart\'. Analyzing the Quantum Approximate Optimization Algorithm: Ans\"atze, Symmetries, and. PRX Quantum , volume =. 2025 , month =. doi:10.1103/yfwq-yqmk , url =

    work page doi:10.1103/yfwq-yqmk 2025

  79. [80]

    Quantum , volume=

    Characterization of variational quantum algorithms using free fermions , author=. Quantum , volume=. 2023 , publisher=

    2023

  80. [81]

    npj Quantum Information , volume=

    Quantum computational phase transition in combinatorial problems , author=. npj Quantum Information , volume=. 2022 , publisher=

    2022

Showing first 80 references.