Classically equivalent formulations of an optimization problem need not lead to equivalent quantum algorithms. For MaxCut, fixing the value of a single vertex removes a simple global symmetry without changing the underlying optimization problem, yet it can substantially alter the quantum dynamics generated by the Quantum Approximate Optimization Algorithm (QAOA). These dynamics are captured by the circuit's dynamical Lie algebra (DLA), whose direct construction can become exponentially expensive. Here we show that, for symmetry-reduced QAOA on trees, substantial information about the reduced DLA can instead be obtained efficiently from the graph alone. We introduce a polynomial classical algorithm that recursively distinguishes vertices using shortest path structure and degree parity. When all vertices are resolved individually, the method determines the complete reduced DLA and, under the corresponding graph conditions, certifies maximal expressibility of the reduced QAOA ansatz. Even when full resolution is not achieved, the algorithm identifies embedded subalgebras, provides rigorous lower bounds on DLA dimension, and certifies controllable subsystems. Our theoretical and experimental results show how classical graph structure can be used to diagnose and potentially guide the quantum dynamics of variational algorithms before running them on quantum hardware.
Classically equivalent formulations of an optimization problem need not lead to equivalent quantum algorithms. For MaxCut, fixing the value of a single vertex removes a simple global symmetry without changing the underlying optimization problem, yet it can substantially alter the quantum dynamics generated by the Quantum Approximate Optimization Algorithm (QAOA). These dynamics are captured by the circuit's dynamical Lie algebra (DLA), whose direct construction can become exponentially expensive. Here we show that, for symmetry-reduced QAOA on trees, substantial information about the reduced DLA can instead be obtained efficiently from the graph alone. We introduce a polynomial classical algorithm that recursively distinguishes vertices using shortest path structure and degree parity. When all vertices are resolved individually, the method determines the complete reduced DLA and, under the corresponding graph conditions, certifies maximal expressibility of the reduced QAOA ansatz. Even when full resolution is not achieved, the algorithm identifies embedded subalgebras, provides rigorous lower bounds on DLA dimension, and certifies controllable subsystems. Our theoretical and experimental results show how classical graph structure can be used to diagnose and potentially guide the quantum dynamics of variational algorithms before running them on quantum hardware.
The performance of the Quantum Approximate Optimization Algorithm (QAOA) is closely tied to the structure of the dynamical Lie algebra (DLA) generated by its Hamiltonians, which determines both its expressivity and trainability. In this work, we show that classical symmetries can be systematically exploited as a design principle for QAOA. Focusing on the MaxCut problem with global bit-flip symmetry, we analyze reduced QAOA instances obtained by fixing a single variable and study how this choice affects the associated DLAs. We show that the structure of the DLAs can change dramatically depending on which variable is held fixed. In particular, we construct explicit examples where the dimension collapses from exponential to quadratic, uncovering phenomena that do not appear in the original formulation.
Numerical experiments on asymmetric graphs indicate that such reductions often produce DLAs of much smaller dimension, suggesting improved trainability. We also prove that any graph can be embedded into a slightly larger one (requiring only quadratic overhead) such that the standard reduced DLA coincides with the free reduced DLA, in most cases implying exponential dimension and irreducibility on the Hilbert space for reduced QAOA instances. These results establish symmetry-aware reduction as a principled tool for designing expressive and potentially trainable QAOA circuits.
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.
The QAOA has been the subject of intense study over recent years, yet the corresponding Dynamical Lie Algebra (DLA)--a key indicator of the expressivity and trainability of VQAs--remains poorly understood beyond highly symmetric instances. An exponentially scaling DLA dimension is associated with the presence of so-called barren plateaus (BP) in the optimization landscape, which renders training intractable. In this work, we investigate the DLA of QAOA applied to the canonical MaxCut, for both weighted and unweighted graphs. For weighted graphs, we show that when the weights are drawn from a continuous distribution, the DLA dimension grows as Θ(4n) almost surely for all connected graphs except paths and cycles. In the more common unweighted setting, we show that asymptotically all but an exponentially vanishing fraction of graphs have Θ(4n) large DLA dimension. The entire simple Lie algebra decomposition of the corresponding DLAs is also identified, from which we prove that the variance of the loss function is O(1/2n), implying that QAOA on these weighted and unweighted graphs all suffers from BP. Moreover, we give explicit constructions for families of graphs whose DLAs have exponential dimension, including cases whose MaxCut is in P. Our proof of the unweighted case is based on a number of splitting lemmas and DLA-freeness conditions that allow one to convert prohibitively complicated Lie algebraic problems into amenable graph theoretic problems. These form the basis for a new algorithm that computes such DLAs orders of magnitude faster than previous methods, reducing runtimes from days to seconds on standard hardware. We apply this algorithm to MQLib, a classical MaxCut benchmark suite covering over 3,500 instances with up to 53,130 vertices, and find that, ignoring edge weights, at least 75% of the instances possess a DLA of dimension at least 2128.
Dynamical 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 s u ( 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.
Variational quantum optimization provides a useful setting for examining how circuit structure, parameterization, and trainability interact in practice. Objectives: Among the most promising variational quantum algorithms, the Quantum Approximate Optimization Algorithm (QAOA) depends critically on circuit architecture, but greater circuit complexity does not necessarily lead to easier optimization or better solutions. Using the Maximum Cut (MaxCut) problem on graphs as a controlled setting, we investigate how variational behavior changes as problem-specific QAOA structure is progressively removed, with particular attention to representational capacity, optimization geometry, and finite-budget trainability. Methods: We analytically characterize a graph-agnostic product-state formulation of MaxCut and derive exact equivalences, redundancies, and local-landscape properties. These results motivate a controlled comparison among separable product ansätze, a representative graphagnostic entangling circuit, and graph-structured QAOA at several depths, including a parameter-count-matched control. The numerical benchmark comprises 95 small unweighted graph instances optimized under a common objective-evaluation budget. Results: The product-state formulation preserves the exact discrete MaxCut optimum, while its strict local maxima correspond to classical cuts that are stable under singlevertex flips. Redundant phase parameters increase optimization effort without enlarging the objective-relevant family. Under the prescribed optimization budget, the productstate ansatz attains higher average solution quality than the tested QAOA depths while requiring substantially fewer objective evaluations. The graph-agnostic entangling comparator provides no consistent advantage over the separable baseline, and a simple classical local-search method remains highly competitive. Conclusion: In the regime considered here, objective-relevant parameterization and optimization geometry can be as important as circuit richness.
The graph isomorphism problem asks whether two graphs are equivalent up to a permutation of their vertices. Its precise computational complexity remains unresolved, and it is still unknown whether a polynomial-time algorithm exists. We investigate whether simple graph-dependent Instantaneous Quantum Polynomial-time (IQP) and Quantum Approximate Optimisation Algorithm (QAOA) circuits can distinguish non-isomorphic graphs. We first show that suitable IQP and QAOA constructions allow the underlying graph to be reconstructed using a polynomial number of samples. Building on previous work using the QAOA energy, we show that Hamming weight distributions can distinguish graph pairs at circuit depths for which the numerically computed energy gap is zero. We then apply graph invariants to the matrix of ZZ correlators on the output distribution. For the specific case of the graph spectrum, at QAOA depth p=2, this invariant numerically distinguishes all 10,486 cospectral regular graph pairs tested on up to 18 vertices. For IQP circuits, we introduce a finer invariant based on probability multiplicities within Hamming weight sectors, which distinguishes every non-isomorphic graph pair tested numerically. Finally, we derive exact graph-theoretic characterisations of the IQP output distribution at θ=π/2 and θ=π/4. These results show that simple graph-dependent quantum circuits encode substantial structural information, while leaving open whether this information can be extracted efficiently for general graph isomorphism.