Automorphism-Assisted QAOA: A Classical-Estimator Speedup for QAOA Simulation on Graphs with Non-Trivial Symmetry

Abstract

We present Automorphism-Assisted QAOA (AA-QAOA), an observable-substitution method that accelerates the classical statevector simulation of QAOA on graphs whose automorphism group is non-trivial. For the unweighted MaxCut Hamiltonian $H_C=\frac{1}{2}{\sum }_{(i,j)\in E}(1-{\sigma }_z^{(i)}{\sigma }_z^{(j)})$, the cost expectation aggregation costs $\mathcal{O}(|E|\cdot 2^n)$ wall time on a statevector estimator. We show that on the Aut$(G)$-symmetric state prepared by the standard QAOA ansatz, replacing $H_C$ with an orbit-reduced observable $H_{\mathrm{red}}$, retaining one representative ZZ term per edge orbit weighted by orbit size, satisfies $⟨H_{\mathrm{red}}⟩=⟨H_C⟩$ exactly, dropping the aggregation cost to $\mathcal{O}(|\mathrm{orbits}|\cdot 2^n)$ with no change to the prepared state, optimization landscape, or approximation ratio. We benchmark AA-QAOA on tree-structured graphs up to 34 vertices and on six non-tree families, including the complete graph $K_n$, the star graph, and random 3-regular graphs, as controlled diagnostics that isolate the mechanism. The complete graph $K_{16}$ at $p=1$ shows an $8\times$ wall-time reduction despite spanning every qubit in the causal cone of its single representative edge, showing that the saving tracks orbit count rather than the qubit span of the representative reverse causal cones. A CPU/GPU control reproduces the speedup on both backends, confirming an architecture-independent, classical-aggregation origin. Approximation ratios satisfy $R_{\mathrm{red}}\approx R_{\mathrm{full}}$ throughout. We are explicit about scope: this is a speedup for classical-simulation pipelines, with no benefit on a quantum processor, where the full circuit executes regardless of the measured observable. The method is therefore of direct use to research groups running QAOA simulation at scale without QPU access.

28 pages, 6 figures