The Landscape of Max-Cut QAOA Lie Algebras

It is conjectured that the existence of barren plateaus in the cost function for deep variational quantum algorithms is closely tied to the dimension of the dynamical Lie algebra (DLA) obtained from the set of generators of the ansatz. To this end, given a simple graph G = (V, E), we study the DLAs of different circuit ansatzes aimed at generating the ground state of $H_p$, the Hamiltonian whose ground states are solutions to the Max-Cut problem on G, including but not limited to circuit ansatzes based on automorphism orbits and subsets of common degree, which naturally incorporate symmetries coming from parity and automorphisms of G. We investigate a variety of salient features of these DLAs, such as their linear symmetries, quadratic symmetries, decomposition into simple Lie algebras, and irreducible representation structure. We find that there are many cases of symmetries that cannot be explained by parity and automorphisms alone, and there are additionally many cases of failure of subspace controllability. However, we also present numerical evidence that these effects, while quite complex, become proportionally less frequent as the graph size increases, even for fairly small graphs, making it very likely that the vast majority of graphs have Max-Cut DLA dimensions that scale exponentially with the number of vertices.