We study the relationship between the Quantum Approximate Optimization Algorithm (QAOA) and the underlying symmetries of the objective function to be optimized. Our approach formalizes the connection between quantum symmetry properties of the QAOA dynamics and the group of classical symmetries of the objective function. The connection is general and includes but is not limited to problems defined on graphs. We show a series of results exploring the connection and highlight examples of hard problem classes where a nontrivial symmetry subgroup can be obtained efficiently. In particular we show how classical objective function symmetries lead to invariant measurement outcome probabilities across states connected by such symmetries, independent of the choice of algorithm parameters or number of layers. To illustrate the power of the developed connection, we apply machine learning techniques towards predicting QAOA performance based on symmetry considerations. We provide numerical evidence that a small set of graph symmetry properties suffices to predict the minimum QAOA depth required to achieve a target approximation ratio on the MaxCut problem, in a practically important setting where QAOA parameter schedules are constrained to be linear and hence easier to optimize.
We investigate the Maximum Cut (MaxCut) problem on different graph classes with the quantum approximate optimization algorithm (QAOA) using symmetries. In particular, heuristics on the relationship between graph symmetries and the approximation ratio achieved by a QAOA simulation are considered. To do so, we first solve the MaxCut problem on well-known graphs, then we consider simple and controllable perturbations of the graph and find again the approximate MaxCut with the QAOA. Through an analysis of the spectrum of the graphs and their perturbations, as well as a careful study of the associated automorphism groups, we aim to extract valuable insight into how symmetry impacts the performance of QAOA. These insights can then be leveraged to heuristically reduce the quantum circuit complexity, the number of training steps, or the number of parameters involved, thus enhancing the efficiency and effectiveness of QAOA-based solutions.
Introducing additional tunable parameters to quantum circuits is a powerful way of improving per-formance without increasing hardware requirements. A recently introduced multiangle extension of the quantum approximate optimization algorithm (ma-QAOA) signifi-cantly improves the solution quality compared with QAOA by allowing the parameters for each term in the Hamilto-nian to vary independently. Prior results suggest, however, considerable redundancy in parameters, the removal of which would reduce the cost of parameter optimization. In this work we show numerically the connection between the problem symmetries and the parameter redundancy by demonstrating that symmetries can be used to reduce the number of parameters used by ma-QAOA without decreasing the solution quality. We study Max-Cut on all 7,565 connected, non-isomorphic 8-node graphs with a nontrivial symmetry group and show numerically that in 67.4% of these graphs, symmetry can be used to reduce the number of parameters with no decrease in the objective, with the average ratio of parameters reduced by 28.1%. Moreover, we show that in 35.9% of the graphs this reduction can be achieved by simply using the largest symmetry. For the graphs where reducing the number of parameters leads to a decrease in the objective, the largest symmetry can be used to reduce the parameter count by 37.1% at the cost of only a 6.1% decrease in the objective. We demonstrate the central role of symmetries by showing that a random parameter reduction strategy leads to much worse performance.
Recent results on the Quantum Approximate Optimization Algorithm (QAOA) have cast pessimism on its potential to exhibit practical quantum speedups. For instance, QAOA’s locality limits its performance on tasks such as coloring bipartite graphs—which is easy for classical methods. Motivated by these limitations, the Recursive QAOA was introduced to overcome the locality and symmetry of QAOA. Despite being more powerful than QAOA, RQAOA is fully classically simulable at level-1 depth (p = 1). We report results on RQAOA in this classically simulable regime, benchmarked on random Quantum Unconstrainted Binary Optimization (QUBO) problems with up to 100 variables. We find that RQAOA generally matches the performance of classical simulated annealing and significantly outperforms ordinary QAOA.
Abstract The eXpressive Quantum Approximate Optimization Algorithm (XQAOA), a recently developed variant of QAOA for the MaxCut problem, can enhance approximation ratios at low circuit depths by assigning more classical parameters to the ansatz. Although XQAOA improves the performance of the circuit model, the introduction of a large number of additional parameters increases the cost of parameter optimization. Whether it is possible to reduce the number of parameters while maintaining the performance of the quantum circuit remains an intriguing research topic. Building spatial symmetry into parameterized quantum circuits is an effective approach to addressing parameter redundancy. In this study, the direct application of the symmetry in XQAOA is investigated and it was found that this application leads to a decrease in the approximation ratio. To address this issue, an improved symmetry‐based XQAOA is proposed, where two‐qubit gates for edges in the same orbit share parameters, while single‐qubit gates have independent parameters. Numerical simulations demonstrate that this approach maintains a comparable approximation ratio while decreasing the number of function evaluations, thereby reducing the cost of training XQAOA. In addition, observations reveal that the smaller the number of edge orbits, the more significant the acceleration in training.
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
HC=21∑(i,j)∈E(1−σz(i)σz(j)), the cost expectation aggregation costs
O(∣E∣⋅2n) wall time on a statevector estimator. We show that on the Aut
(G)-symmetric state prepared by the standard QAOA ansatz, replacing
HC with an orbit-reduced observable
Hred, retaining one representative ZZ term per edge orbit weighted by orbit size, satisfies
⟨Hred⟩=⟨HC⟩ exactly, dropping the aggregation cost to
O(∣orbits∣⋅2n) 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
Kn, the star graph, and random 3-regular graphs, as controlled diagnostics that isolate the mechanism. The complete graph
K16 at
p=1 shows an
8× 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
Rred≈Rfull 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.