Equivariant Quantum Approximate Optimization Algorithm

Constructing effective mixer Hamiltonians is essential for enhancing the performance of the quantum approximate optimization algorithm (QAOA) in solving combinatorial optimization problems. In this work, we develop a systematic methodology for designing QAOA mixers that align with the symmetries of the classical objective function, with the goal of achieving values (mean, median, and minimum over multiple runs) that are closer to the true optimum. Our main idea is to design QAOA operators that are explicitly adapted to the action of symmetry groups on the Hilbert space. We focus on subgroups of the symmetric group <inline-formula><tex-math notation="LaTeX">S_d</tex-math></inline-formula>, where <inline-formula><tex-math notation="LaTeX">d = 2^ell</tex-math></inline-formula>, to ensure compatibility with qudit-based quantum architectures. In particular, we construct QAOA mixers invariant under the full symmetric group <inline-formula><tex-math notation="LaTeX">S_d</tex-math></inline-formula> as well as its cyclic subgroup <inline-formula><tex-math notation="LaTeX">mathbb {Z}_d subset S_d</tex-math></inline-formula>. These constructions are natural in that they respect the decomposition of the Hilbert space into isotypic components under the symmetry group action. Notably, to the best of the authors&#x2019; knowledge, the QAOA algorithm based on the <inline-formula><tex-math notation="LaTeX">mathbb {Z}_d</tex-math></inline-formula>-invariant mixer provides the first example of a QAOA protocol whose dynamics (up to final measurement) are confined entirely within a nontrivial irreducible representation of a symmetry group of the objective function. Although our work does not investigate the benefits of exploiting such subspaces as computational resources, we think that the very realization of a variational algorithm whose evolution is restricted to a nontrivial symmetry-adapted subspace is of fundamental conceptual interest. We provide closed-form expressions for these mixers, together with explicit quantum circuit implementations. To empirically evaluate our approach, we compare QAOA variants employing the standard mixer <inline-formula><tex-math notation="LaTeX">B = sum X_i</tex-math></inline-formula> with those using our proposed Hamiltonians <inline-formula><tex-math notation="LaTeX">H_M</tex-math></inline-formula> and <inline-formula><tex-math notation="LaTeX">H_χ</tex-math></inline-formula> on edge coloring and graph partitioning problems. Across multiple graph instances, our symmetry-adapted mixers consistently yield objective values closer to the optimum, demonstrating statistically significant improvements over classical baselines.