Journal Article

FZJ-2025-04200

http://join2-wiki.gsi.de/foswiki/pub/Main/Artwork/join2_logo100x88.png Analyzing the Quantum Approximate Optimization Algorithm: Ansätze, Symmetries, and Lie Algebras

Kazi, S. ; Larocca, M. ; Farinati, M. ; Coles, P. J. ; Cerezo, M. ; Zeier, R. (Corresponding author)FZJ*

2025
American Physical Society College Park, MD

This record in other databases:  

Please use a persistent id in citations: doi:10.1103/yfwq-yqmk  doi:10.34734/FZJ-2025-04200

Abstract: The quantum approximate optimization algorithm (QAOA) has been proposed as a method to obtain approximate solutions for combinatorial optimization tasks. In this work, we study the underlying algebraic properties of three QAOA ansätze for the maximum-cut problem on connected graphs, while focusing on the generated Lie algebras as well as their invariant subspaces. Specifically, we analyze the standard QAOA ansatz as well as the orbit and multiangle ansätze. We are able to fully characterize the Lie algebras of the multiangle ansatz across arbitrary connected graphs, finding that they only fall into one of just six families. Aside from the cycle and path graphs, the Lie dimensions for every graph are exponentially large in the system size, meaning that multiangle ansätze are extremely prone to exhibiting barren plateaus. Then, a similar quasi-graph-independent Lie-algebraic characterization beyond the multiangle ansatz is impeded as the circuit exhibits additional “hidden” symmetries besides those naturally arising from a certain parity-superselection operator and all automorphisms of the considered graph. Disregarding the “hidden” symmetries, we can upper bound the dimensions of the orbit and the standard Lie algebras, and the dimensions of the associated invariant subspaces are determined via explicit character formulas. To finish, we conjecture that (for most graphs) the standard Lie algebras have only components that are either exponential or that grow, at most, polynomially with the system size. This would imply that the QAOA is either prone to barren plateaus or classically simulable. More generally, our work provides a symmetry framework and tools to analyze any desired variational quantum algorithm.

---

Contributing Institute(s):

1. Quantum Control (PGI-8)

Research Program(s):

1. 5221 - Advanced Solid-State Qubits and Qubit Systems (POF4-522) (POF4-522)
2. PASQuanS2.1 - Programmable Atomic Large-scale Quantum Simulation 2 - SGA1 (101113690) (101113690)
3. HPCQS - High Performance Computer and Quantum Simulator hybrid (101018180) (101018180)

Appears in the scientific report 2025

---

Database coverage:
; ; ; ; Article Processing Charges ; Clarivate Analytics Master Journal List ; Current Contents - Physical, Chemical and Earth Sciences ; DOAJ Seal ; Essential Science Indicators ; Fees ; IF >= 5 ; JCR ; SCOPUS ; Science Citation Index Expanded ; Web of Science Core Collection

---