quantum-computing

On the dynamical Lie algebras of quantum approximate optimization algorithms

Quantum Journal

23 min read

0 likes

On the dynamical Lie algebras of quantum approximate optimization algorithms

Summarize this article with:

AbstractDynamical Lie algebras (DLAs) have emerged as a valuable tool in the study of parameterized quantum circuits, helping to characterize both their expressiveness and trainability. In particular, the absence or presence of barren plateaus (BPs) – flat regions in parameter space that prevent the efficient training of variational quantum algorithms – has recently been shown to be intimately related to quantities derived from the associated DLA. In this work, we investigate DLAs for the quantum approximate optimization algorithm (QAOA), one of the most studied variational quantum algorithms for solving graph MaxCut and other combinatorial optimization problems. While DLAs for QAOA circuits have been studied before, existing results have either been based on numerical evidence, or else correspond to DLA generators specifically chosen to be universal for quantum computation on a subspace of states. We initiate an analytical study of barren plateaus and other statistics of QAOA algorithms, and give bounds on the dimensions of the corresponding DLAs and their centers for general graphs. We then focus on the $n$-vertex cycle and complete graphs. For the cycle graph we give an explicit basis, identify its decomposition into the direct sum of a $2$-dimensional center and a semisimple component isomorphic to $n-1$ copies of $su(2)$. We give an explicit basis for this isomorphism, and a closed-form expression for the variance of the cost function, proving the absence of BPs. For the complete graph we prove that the dimension of the DLA is $O(n^3)$ and give an explicit basis for the DLA.► BibTeX data@article{Allcock2026dynamicallie, doi = {10.22331/q-2026-05-29-2119}, url = {https://doi.org/10.22331/q-2026-05-29-2119}, title = {On the dynamical {L}ie algebras of quantum approximate optimization algorithms}, author = {Allcock, Jonathan and Santha, Miklos and Yuan, Pei and Zhang, Shengyu}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {10}, pages = {2119}, month = may, year = {2026} }► References [1] Marco Cerezo, Andrew Arrasmith, Ryan Babbush, Simon C Benjamin, Suguru Endo, Keisuke Fujii, Jarrod R McClean, Kosuke Mitarai, Xiao Yuan, Lukasz Cincio, et al. ``Variational quantum algorithms''.

Nature Reviews Physics 3, 625–644 (2021). https://doi.org/10.1038/s42254-021-00348-9 [2] Lov K Grover. ``A fast quantum mechanical algorithm for database search''. In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing. Pages 212–219. (1996). https://doi.org/10.1145/237814.237866 [3] Peter W Shor. ``Algorithms for quantum computation: discrete logarithms and factoring''. In Proceedings 35th annual symposium on foundations of computer science. Pages 124–134. IEEE (1994). https://doi.org/10.1109/SFCS.1994.365700 [4] Aram W Harrow, Avinatan Hassidim, and Seth Lloyd. ``Quantum algorithm for linear systems of equations''. Physical review letters 103, 150502 (2009). https://doi.org/10.1103/PhysRevLett.103.150502 [5] Stephen Jordan. ``Quantum algorithm zoo''. https://quantumalgorithmzoo.org/. https://quantumalgorithmzoo.org/. [6] Ryan Babbush, Jarrod R McClean, Michael Newman, Craig Gidney, Sergio Boixo, and Hartmut Neven. ``Focus beyond quadratic speedups for error-corrected quantum advantage''. PRX Quantum 2, 010103 (2021). https://doi.org/10.1103/PRXQuantum.2.010103 [7] Torsten Hoefler, Thomas Häner, and Matthias Troyer. ``Disentangling hype from practicality: On realistically achieving quantum advantage''. Communications of the ACM 66, 82–87 (2023). https://doi.org/10.1145/3571725 [8] Alberto Peruzzo, Jarrod McClean, Peter Shadbolt, Man-Hong Yung, Xiao-Qi Zhou, Peter J Love, Alán Aspuru-Guzik, and Jeremy L O’brien. ``A variational eigenvalue solver on a photonic quantum processor''. Nature Communications 5, 4213 (2014). https://doi.org/10.1038/ncomms5213 [9] Jarrod R McClean, Sergio Boixo, Vadim N Smelyanskiy, Ryan Babbush, and Hartmut Neven. ``Barren plateaus in quantum neural network training landscapes''. Nature Communications 9, 4812 (2018). https://doi.org/10.1038/s41467-018-07090-4 [10] Carlos Ortiz Marrero, Mária Kieferová, and Nathan Wiebe. ``Entanglement-induced barren plateaus''. PRX Quantum 2, 040316 (2021). https://doi.org/10.1103/PRXQuantum.2.040316 [11] Taylor L Patti, Khadijeh Najafi, Xun Gao, and Susanne F Yelin. ``Entanglement devised barren plateau mitigation''.

Physical Review Research 3, 033090 (2021). https://doi.org/10.1103/PhysRevResearch.3.033090 [12] Arthur Pesah, Marco Cerezo, Samson Wang, Tyler Volkoff, Andrew T Sornborger, and Patrick J Coles. ``Absence of barren plateaus in quantum convolutional neural networks''. Physical Review X 11, 041011 (2021). https://doi.org/10.1103/PhysRevX.11.041011 [13] Zoë Holmes, Kunal Sharma, Marco Cerezo, and Patrick J Coles. ``Connecting ansatz expressibility to gradient magnitudes and barren plateaus''. PRX Quantum 3, 010313 (2022). https://doi.org/10.1103/PRXQuantum.3.010313 [14] Martin Larocca, Piotr Czarnik, Kunal Sharma, Gopikrishnan Muraleedharan, Patrick J Coles, and Marco Cerezo. ``Diagnosing barren plateaus with tools from quantum optimal control''. Quantum 6, 824 (2022). https://doi.org/10.22331/q-2022-09-29-824 [15] Kunal Sharma, Marco Cerezo, Lukasz Cincio, and Patrick J Coles. ``Trainability of dissipative perceptron-based quantum neural networks''.

Physical Review Letters 128, 180505 (2022). https://doi.org/10.1103/PhysRevLett.128.180505 [16] Lucas Friedrich and Jonas Maziero. ``Quantum neural network cost function concentration dependency on the parametrization expressivity''. Scientific Reports 13, 9978 (2023). https://doi.org/10.1038/s41598-023-37003-5 [17] Enrique Cervero Martín, Kirill Plekhanov, and Michael Lubasch. ``Barren plateaus in quantum tensor network optimization''. Quantum 7, 974 (2023). https://doi.org/10.22331/q-2023-04-13-974 [18] Marco Cerezo, Akira Sone, Tyler Volkoff, Lukasz Cincio, and Patrick J Coles. ``Cost function dependent barren plateaus in shallow parametrized quantum circuits''. Nature Communications 12, 1791 (2021). https://doi.org/10.1038/s41467-021-21728-w [19] Amira Abbas, David Sutter, Christa Zoufal, Aurélien Lucchi, Alessio Figalli, and Stefan Woerner. ``The power of quantum neural networks''.

Nature Computational Science 1, 403–409 (2021). https://doi.org/10.1038/s43588-021-00084-1 [20] Zoë Holmes, Andrew Arrasmith, Bin Yan, Patrick J Coles, Andreas Albrecht, and Andrew T Sornborger. ``Barren plateaus preclude learning scramblers''.

Physical Review Letters 126, 190501 (2021). https://doi.org/10.1103/PhysRevLett.126.190501 [21] Ruslan Shaydulin and Stefan M Wild. ``Importance of kernel bandwidth in quantum machine learning''. Physical Review A 106, 042407 (2022). https://doi.org/10.1103/PhysRevA.106.042407 [22] Supanut Thanasilp, Samson Wang, Nhat Anh Nghiem, Patrick Coles, and Marco Cerezo. ``Subtleties in the trainability of quantum machine learning models''.

Quantum Machine Intelligence 5, 21 (2023). https://doi.org/10.1007/s42484-023-00103-6 [23] AV Uvarov and Jacob D Biamonte. ``On barren plateaus and cost function locality in variational quantum algorithms''. Journal of Physics A: Mathematical and Theoretical 54, 245301 (2021). https://doi.org/10.1088/1751-8121/abfac7 [24] Muhammad Kashif and Saif Al-Kuwari. ``The impact of cost function globality and locality in hybrid quantum neural networks on NISQ devices''. Machine Learning: Science and Technology 4, 015004 (2023). https://doi.org/10.1088/2632-2153/acb12f [25] Sumeet Khatri, Ryan LaRose, Alexander Poremba, Lukasz Cincio, Andrew T Sornborger, and Patrick J Coles. ``Quantum-assisted quantum compiling''. Quantum 3, 140 (2019). https://doi.org/10.22331/q-2019-05-13-140 [26] Samson Wang, Enrico Fontana, Marco Cerezo, Kunal Sharma, Akira Sone, Lukasz Cincio, and Patrick J Coles. ``Noise-induced barren plateaus in variational quantum algorithms''. Nature Communications 12, 6961 (2021). https://doi.org/10.1038/s41467-021-27045-6 [27] Daniel Stilck França and Raul Garcia-Patron. ``Limitations of optimization algorithms on noisy quantum devices''. Nature Physics 17, 1221–1227 (2021). https://doi.org/10.1038/s41567-021-01356-3 [28] Diego García-Martín, Martín Larocca, and Marco Cerezo. ``Effects of noise on the overparametrization of quantum neural networks''.

Physical Review Research 6, 013295 (2024). https://doi.org/10.1103/PhysRevResearch.6.013295 [29] Michael Ragone, Bojko N Bakalov, Frédéric Sauvage, Alexander F Kemper, Carlos Ortiz Marrero, Martín Larocca, and M Cerezo. ``A lie algebraic theory of barren plateaus for deep parameterized quantum circuits''. Nature Communications 15, 7172 (2024). https://doi.org/10.1038/s41467-024-49909-3 [30] Enrico Fontana, Dylan Herman, Shouvanik Chakrabarti, Niraj Kumar, Romina Yalovetzky, Jamie Heredge, Shree Hari Sureshbabu, and Marco Pistoia. ``Characterizing barren plateaus in quantum ansätze with the adjoint representation''. Nature Communications 15, 7171 (2024). https://doi.org/10.1038/s41467-024-49910-w [31] NL Diaz, Diego García-Martín, Sujay Kazi, Martin Larocca, and M Cerezo. ``Showcasing a barren plateau theory beyond the dynamical Lie algebra'' (2023). arXiv:2310.11505. arXiv:2310.11505 [32] Matthew L. Goh, Martin Larocca, Lukasz Cincio, M. Cerezo, and Frédéric Sauvage. ``Lie-algebraic classical simulations for quantum computing''. Phys. Rev. Res. 7, 033266 (2025). https://doi.org/10.1103/3y65-f5w6 [33] Bingzhi Zhang, Akira Sone, and Quntao Zhuang. ``Quantum computational phase transition in combinatorial problems''. npj Quantum Information 8, 87 (2022). https://doi.org/10.1038/s41534-022-00596-2 [34] Martin Larocca, Nathan Ju, Diego García-Martín, Patrick J Coles, and Marco Cerezo. ``Theory of overparametrization in quantum neural networks''.

Nature Computational Science 3, 542–551 (2023). https://doi.org/10.1038/s43588-023-00467-6 [35] Bobak Toussi Kiani, Seth Lloyd, and Reevu Maity. ``Learning unitaries by gradient descent'' (2020). arXiv:2001.11897. arXiv:2001.11897 [36] Roeland Wiersema, Cunlu Zhou, Yvette de Sereville, Juan Felipe Carrasquilla, Yong Baek Kim, and Henry Yuen. ``Exploring entanglement and optimization within the Hamiltonian variational ansatz''. PRX Quantum 1, 020319 (2020). https://doi.org/10.1103/PRXQuantum.1.020319 [37] Léo Monbroussou, Jonas Landman, Alex B Grilo, Romain Kukla, and Elham Kashefi. ``Trainability and expressivity of Hamming-weight preserving quantum circuits for machine learning'' (2023). arXiv:2309.15547. https://doi.org/10.22331/q-2025-05-15-1745 arXiv:2309.15547 [38] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. ``A quantum approximate optimization algorithm'' (2014). arXiv:1411.4028. arXiv:1411.4028 [39] Kostas Blekos, Dean Brand, Andrea Ceschini, Chiao-Hui Chou, Rui-Hao Li, Komal Pandya, and Alessandro Summer. ``A review on quantum approximate optimization algorithm and its variants''. Physics Reports 1068, 1–66 (2024). https://doi.org/10.1016/j.physrep.2024.03.002 [40] Roeland Wiersema, Efekan Kökcü, Alexander F Kemper, and Bojko N Bakalov. ``Classification of dynamical lie algebras of 2-local spin systems on linear, circular and fully connected topologies''. npj Quantum Information 10, 110 (2024). https://doi.org/10.1038/s41534-024-00900-2 [41] Gerard Aguilar, Simon Cichy, Jens Eisert, and Lennart Bittel. ``Full classification of Pauli lie algebras'' (2024). arXiv:2408.00081. arXiv:2408.00081 [42] Alexandre Choquette, Agustin Di Paolo, Panagiotis Kl Barkoutsos, David Sénéchal, Ivano Tavernelli, and Alexandre Blais. ``Quantum-optimal-control-inspired ansatz for variational quantum algorithms''.

Physical Review Research 3, 023092 (2021). https://doi.org/10.1103/PhysRevResearch.3.023092 [43] Johannes Jakob Meyer, Marian Mularski, Elies Gil-Fuster, Antonio Anna Mele, Francesco Arzani, Alissa Wilms, and Jens Eisert. ``Exploiting symmetry in variational quantum machine learning''. PRX Quantum 4, 010328 (2023). https://doi.org/10.1103/PRXQuantum.4.010328 [44] Seth Lloyd. ``Quantum approximate optimization is computationally universal'' (2018). arXiv:1812.11075. arXiv:1812.11075 [45] Mauro ES Morales, Jacob D Biamonte, and Zoltán Zimborás. ``On the universality of the quantum approximate optimization algorithm''.

Quantum Information Processing 19, 1–26 (2020). https://doi.org/10.1007/s11128-020-02748-9 [46] Francesca Albertini and Domenico D’Alessandro. ``Controllability of symmetric spin networks''. Journal of Mathematical Physics 59 (2018). https://doi.org/10.1063/1.5004652 [47] Sujay Kazi, Martin Larocca, and Marco Cerezo. ``On the universality of Sn-equivariant k-body gates''. New Journal of Physics 26, 053030 (2024). https://doi.org/10.1088/1367-2630/ad4819 [48] Louis Schatzki, Martin Larocca, Quynh T Nguyen, Frederic Sauvage, and Marco Cerezo. ``Theoretical guarantees for permutation-equivariant quantum neural networks''. npj Quantum Information 10, 12 (2024). https://doi.org/10.1038/s41534-024-00804-1 [49] F. Harary. ``Graph theory''. Addison-Wesley. (1969). [50] Oded Regev. ``Quantum computation and lattice problems''. SIAM Journal on Computing 33, 738–760 (2004). https://doi.org/10.1137/S0097539703440678 [51] Dan Boneh and Richard J Lipton. ``Quantum cryptanalysis of hidden linear functions''. In Advances in Cryptology—CRYPT0’95: 15th Annual International Cryptology Conference Santa Barbara, California, USA, August 27–31, 1995 Proceedings 15. Pages 424–437. Springer (1995). https://doi.org/10.1007/3-540-44750-4_34 [52] Robert Beals. ``Quantum computation of Fourier transforms over symmetric groups''. In Proceedings of the twenty-ninth annual ACM symposium on Theory of computing. Pages 48–53. (1997). https://doi.org/10.1145/258533.258548 [53] Mark Ettinger and Peter Hoyer. ``A quantum observable for the graph isomorphism problem'' (1999). arXiv:9901029. https://doi.org/10.48550/arXiv.quant-ph/9901029 arXiv:9901029 [54] Seth Lloyd. ``Almost any quantum logic gate is universal''.

Physical Review Letters 75, 346 (1995). https://doi.org/10.1103/PhysRevLett.75.346 [55] Velimir Jurdjevic. ``Geometric control theory''. Cambridge university press. (1997). [56] Abhinav Kandala, Antonio Mezzacapo, Kristan Temme, Maika Takita, Markus Brink, Jerry M Chow, and Jay M Gambetta. ``Hardware-efficient variational quantum eigensolver for small molecules and quantum magnets''. Nature 549, 242–246 (2017). https://doi.org/10.1038/nature23879 [57] Rebekah Herrman, Phillip C Lotshaw, James Ostrowski, Travis S Humble, and George Siopsis. ``Multi-angle quantum approximate optimization algorithm''. Scientific Reports 12, 6781 (2022). https://doi.org/10.1038/s41598-022-10555-8 [58] Efekan Kökcü, Roeland Wiersema, Alexander F Kemper, and Bojko N Bakalov. ``Classification of dynamical lie algebras generated by spin interactions on undirected graphs''. Journal of Mathematical Physics 67 (2026). https://doi.org/10.1063/5.0283277 [59] Sujay Kazi, Martín Larocca, Marco Farinati, Patrick J. Coles, M. Cerezo, and Robert Zeier. ``Analyzing the quantum approximate optimization algorithm: Ansätze, symmetries, and lie algebras''. PRX Quantum 6, 040345 (2025). https://doi.org/10.1103/yfwq-yqmk [60] Quynh T Nguyen, Louis Schatzki, Paolo Braccia, Michael Ragone, Patrick J Coles, Frederic Sauvage, Martin Larocca, and Marco Cerezo. ``Theory for equivariant quantum neural networks''. PRX Quantum 5, 020328 (2024). https://doi.org/10.1103/PRXQuantum.5.020328 [61] Gabriel Matos, Chris N Self, Zlatko Papić, Konstantinos Meichanetzidis, and Henrik Dreyer. ``Characterization of variational quantum algorithms using free fermions''. Quantum 7, 966 (2023). https://doi.org/10.22331/q-2023-03-30-966 [62] Rui Mao, Pei Yuan, Jonathan Allcock, and Shengyu Zhang. ``QAOA-MaxCut has barren plateaus for almost all graphs'' (2025). arXiv:2512.24577. arXiv:2512.24577 [63] Rebekah Herrman, Lorna Treffert, James Ostrowski, Phillip C Lotshaw, Travis S Humble, and George Siopsis. ``Impact of graph structures for QAOA on MaxCut''.

Quantum Information Processing 20, 289 (2021). https://doi.org/10.1007/s11128-021-03232-8 [64] Ruslan Shaydulin, Stuart Hadfield, Tad Hogg, and Ilya Safro. ``Classical symmetries and the quantum approximate optimization algorithm''.

Quantum Information Processing 20, 359 (2021). https://doi.org/10.1007/s11128-021-03298-4 [65] Anthony W Knapp and Anthony William Knapp. ``Lie groups beyond an introduction''. Volume 140. Springer. (1996). https://doi.org/10.1007/978-1-4757-2453-0 [66] Domenico D'Alessandro and Yasemin Isik. ``Controllability of the periodic quantum ising spin chain'' (2024). arXiv:2405.00898. arXiv:2405.00898 [67] Shi-Xin Zhang, Jonathan Allcock, Zhou-Quan Wan, Shuo Liu, Jiace Sun, Hao Yu, Xing-Han Yang, Jiezhong Qiu, Zhaofeng Ye, Yu-Qin Chen, et al. ``Tensorcircuit: a quantum software framework for the nisq era''. Quantum 7, 912 (2023). https://doi.org/10.22331/q-2023-02-02-912 [68] Brian C. Hall. ``Lie groups, Lie algebras, and representations''. Springer. (2013). https://doi.org/10.1007/978-1-4614-7116-5_16 [69] Eric R Anschuetz, Andreas Bauer, Bobak T Kiani, and Seth Lloyd. ``Efficient classical algorithms for simulating symmetric quantum systems''. Quantum 7, 1189 (2023). https://doi.org/10.22331/q-2023-11-28-1189 [70] Kaushalya Rani Hota. ``Real forms of simple Lie algebras'' (2014). [71] Karin Erdmann and Mark J Wildon. ``Introduction to Lie algebras''. Volume 122. Springer. (2006). https://doi.org/10.1007/1-84628-490-2 [72] Julian Lowell Coolidge. ``A treatise on algebraic plane curves''. Volume 1. Courier Corporation. (2004). [73] Leonid Mirsky. ``An introduction to linear algebra''. Courier Corporation. (2012). [74] Edris Ahmad Rawashdeh. ``A simple method for finding the inverse matrix of Vandermonde matrix''. Matematicki Vesnik 3, 207–213 (2019). url: https://euclid.matf.bg.ac.rs/index.php/vesnik/article/view/mv19303. https://euclid.matf.bg.ac.rs/index.php/vesnik/article/view/mv19303Cited byCould not fetch Crossref cited-by data during last attempt 2026-05-29 07:46:15: Could not fetch cited-by data for 10.22331/q-2026-05-29-2119 from Crossref. This is normal if the DOI was registered recently. Could not fetch ADS cited-by data during last attempt 2026-05-29 07:46:15: Cannot retrieve data from ADS due to rate limitations.This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions. AbstractDynamical Lie algebras (DLAs) have emerged as a valuable tool in the study of parameterized quantum circuits, helping to characterize both their expressiveness and trainability. In particular, the absence or presence of barren plateaus (BPs) – flat regions in parameter space that prevent the efficient training of variational quantum algorithms – has recently been shown to be intimately related to quantities derived from the associated DLA. In this work, we investigate DLAs for the quantum approximate optimization algorithm (QAOA), one of the most studied variational quantum algorithms for solving graph MaxCut and other combinatorial optimization problems. While DLAs for QAOA circuits have been studied before, existing results have either been based on numerical evidence, or else correspond to DLA generators specifically chosen to be universal for quantum computation on a subspace of states. We initiate an analytical study of barren plateaus and other statistics of QAOA algorithms, and give bounds on the dimensions of the corresponding DLAs and their centers for general graphs. We then focus on the $n$-vertex cycle and complete graphs. For the cycle graph we give an explicit basis, identify its decomposition into the direct sum of a $2$-dimensional center and a semisimple component isomorphic to $n-1$ copies of $su(2)$. We give an explicit basis for this isomorphism, and a closed-form expression for the variance of the cost function, proving the absence of BPs. For the complete graph we prove that the dimension of the DLA is $O(n^3)$ and give an explicit basis for the DLA.► BibTeX data@article{Allcock2026dynamicallie, doi = {10.22331/q-2026-05-29-2119}, url = {https://doi.org/10.22331/q-2026-05-29-2119}, title = {On the dynamical {L}ie algebras of quantum approximate optimization algorithms}, author = {Allcock, Jonathan and Santha, Miklos and Yuan, Pei and Zhang, Shengyu}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {10}, pages = {2119}, month = may, year = {2026} }► References [1] Marco Cerezo, Andrew Arrasmith, Ryan Babbush, Simon C Benjamin, Suguru Endo, Keisuke Fujii, Jarrod R McClean, Kosuke Mitarai, Xiao Yuan, Lukasz Cincio, et al. ``Variational quantum algorithms''.

Read Original

Source Information

Source: Quantum Journal

Website: https://quantum-journal.org/feed/

On the dynamical Lie algebras of quantum approximate optimization algorithms

Tags

Source Information