Analyzing the quantum approximate optimization algorithm: ansätze, symmetries, and Lie algebras

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 (maxcut) 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 the multi-angle ansätze. We are able to fully characterize the Lie algebras of the multi-angle ansatz across arbitrary connected graphs, finding that they only fall into one of just six families. Besides the cycle and the path graphs, the Lie dimensions for every graph are exponentially large in the system size, meaning that multi-angle ansätze are extremely prone to exhibiting barren plateaus. Then, a similar quasi-graph-independent Lie-algebraic characterization beyond the multi-angle 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.

18+25 pages, 9+8 figures, 4+4 tables; expanded discussion and references, further data on asymmetric graphs

References in corpus (78)

• Quantum Machine Learning
• Variational Quantum Algorithms
• Hardware-efficient Variational Quantum Eigensolver for Small Molecules and Quantum Magnets
• Barren plateaus in quantum neural network training landscapes
• Noisy intermediate-scale quantum (NISQ) algorithms
• An introduction to quantum machine learning
• Cost Function Dependent Barren Plateaus in Shallow Parametrized Quantum Circuits
• Two-Bit Gates are Universal for Quantum Computation
• Quantum many-body scars
• From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
• Challenges and Opportunities in Quantum Machine Learning
• Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices
• Connecting ansatz expressibility to gradient magnitudes and barren plateaus
• Quantum Many-Body Scars and Weak Breaking of Ergodicity
• Hybrid quantum-classical algorithms and quantum error mitigation
• Quantum Approximate Optimization of Non-Planar Graph Problems on a Planar Superconducting Processor
• Ergodicity-breaking arising from Hilbert space fragmentation in dipole-conserving Hamiltonians
• Training variational quantum algorithms is NP-hard
• A Review on Quantum Approximate Optimization Algorithm and its Variants
• Random Quantum Circuits are Approximate 2-designs
• Local random quantum circuits are approximate polynomial-designs
• Obstacles to State Preparation and Variational Optimization from Symmetry Protection
• The Quantum Approximate Optimization Algorithm and the Sherrington-Kirkpatrick Model at Infinite Size
• Beyond Barren Plateaus: Quantum Variational Algorithms Are Swamped With Traps
• Diagnosing Barren Plateaus with Tools from Quantum Optimal Control
• Barren Plateaus in Variational Quantum Computing
• Eta-Pairing in Hubbard Models: From Spectrum Generating Algebras to Quantum Many-Body Scars
• Theory of overparametrization in quantum neural networks
• Group-Invariant Quantum Machine Learning
• Entanglement in fermionic systems
• Reachability Deficits in Quantum Approximate Optimization
• A Lie Algebraic Theory of Barren Plateaus for Deep Parameterized Quantum Circuits
• Many Body Scars as a Group Invariant Sector of Hilbert Space
• Approximate unitary $t$-designs by short random quantum circuits using nearest-neighbor and long-range gates
• Models of quantum complexity growth
• Quantum scars as embeddings of weakly "broken" Lie algebra representations
• Extremal Cuts of Sparse Random Graphs
• Convergence rates for arbitrary statistical moments of random quantum circuits
• Theoretical Guarantees for Permutation-Equivariant Quantum Neural Networks
• Random quantum circuits are approximate unitary $t$-designs in depth $O\left(n{t}^{5+o(1)}\right)$
• Symmetry Principles in Quantum Systems Theory
• On the Universality of the Quantum Approximate Optimization Algorithm
• Does provable absence of barren plateaus imply classical simulability?
• Group theoretic approach to many-body scar states in fermionic lattice models
• Restrictions on realizable unitary operations imposed by symmetry and locality
• The Adjoint Is All You Need: Characterizing Barren Plateaus in Quantum Ansätze
• Fixed Depth Hamiltonian Simulation via Cartan Decomposition
• Classical symmetries and the Quantum Approximate Optimization Algorithm
• Building spatial symmetries into parameterized quantum circuits for faster training
• Challenges of variational quantum optimization with measurement shot noise
• Characterization of solvable spin models via graph invariants
• Symmetry criteria for quantum simulability of effective interactions
• Exploiting Symmetry Reduces the Cost of Training QAOA
• A Dynamic Systems Approach to Fermions and Their Relation to Spins
• Performance of a Quantum Annealer for Ising Ground State Computations on Chimera Graphs
• An Expressive Ansatz for Low-Depth Quantum Approximate Optimisation
• Non-trivial symmetries in quantum landscapes and their resilience to quantum noise
• Improved spectral gaps for random quantum circuits: large local dimensions and all-to-all interactions
• Classification of dynamical Lie algebras for translation-invariant 2-local spin systems in one dimension
• Performance and limitations of the QAOA at constant levels on large sparse hypergraphs and spin glass models
• Exhaustive Characterization of Quantum Many-Body Scars using Commutant Algebras
• Controllability of Symmetric Spin Networks
• Mean-Field Approximate Optimization Algorithm
• Quantum simulations under translational symmetry
• Lie-algebraic classical simulations for quantum computing
• Numerical Methods for Detecting Symmetries and Commutant Algebras
• Multi-Angle QAOA Does Not Always Need All Its Angles
• On squares of representations of compact Lie algebras
• On the universality of $S_n$-equivariant $k$-body gates
• Performance Analysis of Multi-Angle QAOA for p > 1
• Rotationally-Invariant Circuits: Universality with the exchange interaction and two ancilla qubits
• Improving Gradient Methods via Coordinate Transformations: Applications to Quantum Machine Learning
• Low-depth Clifford circuits approximately solve MaxCut
• Trainability Barriers in Low-Depth QAOA Landscapes
• Theory of Quantum Circuits with Abelian Symmetries
• A Computational Study of Exact Subgraph Based SDP Bounds for Max-Cut, Stable Set and Coloring
• Deep-Circuit QAOA
• Scaling of symmetry-restricted quantum circuits

Cited by in corpus (2)

• Quantum simulation of massive Thirring and Gross--Neveu models for arbitrary number of flavors
• Variational decision diagrams for quantum-inspired machine learning applications