Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2410.22247

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

Prakash, Vaibhav. N

Published Oct 29, 2024• 0 citations
arXivHTMLPDF

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 = \tfrac{1}{2}\sum_{(i,j)\in E}(1-σ_z^{(i)}σ_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 $\langle H_{\mathrm{red}}\rangle = \langle H_C\rangle$ 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.

DOI
10.48550/arxiv.2410.22247

Related papers

Exploiting Symmetry Reduces the Cost of Training QAOA

Ruslan Shaydulin, Stefan M. Wild

A promising approach to the practical application of the quantum approximate optimization algorithm (QAOA) is finding QAOA parameters classically in simulation and sampling the solutions from QAOA with optimized parameters on a quantum computer. Doing so requires repeated evaluations of QAOA energy in simulation. In this article, we propose a novel approach for accelerating the evaluation of QAOA energy by leveraging the symmetry of the problem. We show a connection between classical symmetries of the objective function and the symmetries of the terms of the cost Hamiltonian with respect to the QAOA energy. We show how by considering only the terms that are not connected by symmetry, we can significantly reduce the cost of evaluating the QAOA energy. Our approach is general and applies to any known subgroup of symmetries and is not limited to graph problems. Our results are directly applicable to nonlocal QAOA generalization recursive QAOA. We outline how available fast graph automorphism solvers can be leveraged for computing the symmetries of the problem in practice. We implement the proposed approach on the MaxCut problem using a state-of-the-art tensor network simulator and a graph automorphism solver on a benchmark of 48 graphs with up to 10 000 nodes. Our approach provides an improvement for$p=1$on 71.7% of the graphs considered, with a median speedup of 4.06, on a benchmark, where 62.5% of the graphs are known to be hard for automorphism solvers.

arXiv:2101.10296•IEEE Transactions on Quantum Engineering•Jan 1, 2021•39 citations

Efficient Estimation of Reduced QAOA Expressibility on Acyclic Graphs

Bao Bach, Boris Tsvelikhovskiy, Jose Falla +1 more

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.

quant-pharXiv:2609.03317•Sep 4, 2026•0 citations

Dealing with locality in QAOA

Mithilesh Kumar, Yusuf Tahir

Shallow-depth QAOA on sparse, high-diameter MaxCut instances faces a locality bottleneck: at depth \(p\), local observables can depend only on a bounded neighborhood of the circuit interaction graph. We propose a transport-augmented QAOA that keeps the MaxCut cost Hamiltonian unchanged but enriches the mixer with optimized, unweighted shortcut couplings (scheduled \(XX+YY\)) to collapse the effective interaction-graph diameter. Using exact finite-depth support recursions, we relate optimal shortcut placement to bounded-diameter graph augmentation, and show in benchmarks that (unlike ma-QAOA) performance becomes effectively size-invariant once the diameter is reduced. For bipartite families (base diameter 4), reducing the interaction path to \(d=1\) raises the ensemble-averaged approximation ratio from 0.7378 (ma-QAOA) to 0.9767 at \(p=1\) (\(σ=0.0251\), nine system sizes); on random trees (base diameter 10), at \(p=2\) it improves from 0.9226 to 0.9997 (\(σ=0.0001\)).

quant-pharXiv:2606.14447•Jun 15, 2026•0 citations

Strategies for running the QAOA at hundreds of qubits

Brandon Augustino, Madelyn Cain, Edward Farhi +5 more

We explore strategies aimed at reducing the amount of computation, both quantum and classical, required to run the Quantum Approximate Optimization Algorithm (QAOA). First, following Wurtz et al. [Phys.Rev A 104:052419], we consider the standard QAOA with instance-independent "tree" parameters chosen in advance. These tree parameters are chosen to optimize the MaxCut expectation for large girth graphs. We provide extensive numerical evidence supporting the performance guarantee for tree parameters conjectured in [Phys.Rev A 103:042612] and see that the approximation ratios obtained with tree parameters are typically well beyond the conjectured lower bounds, often comparable to performing a full optimization. This suggests that in practice, the QAOA can achieve near-optimal performance without the need for parameter optimization. Next, we modify the warm-start QAOA of Tate et al. [Quantum 7:1121]. The starting state for the QAOA is now an optimized product state associated with a solution of the Goemans-Williamson (GW) algorithm. Surprisingly, the tree parameters continue to perform well for the warm-start QAOA. We find that for random 3-regular graphs with hundreds of vertices, the expected cut obtained by the warm-start QAOA at depth $p \gtrsim 3$ is comparable to that of the standard GW algorithm. Our numerics on random instances do not provide general performance guarantees but do provide substantial evidence that there exists a regime of instance sizes in which the QAOA finds good solutions at low depth without the need for parameter optimization. For each instance studied, we classically compute the expected size of the QAOA distribution of cuts; producing the actual cuts requires running on a quantum computer.

arXiv:2410.03015•Oct 3, 2024•1 citation

Structured Parameterization and Non-Stabilizerness in Hypergraph QAOA

Evan Camilleri, André Xuereb, Tony J. G. Apollaro +1 more

The quantum approximate optimization algorithm (QAOA) has emerged as a promising candidate for demonstrating quantum advantage on noisy intermediate-scale quantum (NISQ) devices. While various QAOA parameterization schemes exist, ranging from the original single-angle approach to the more expressive multi-angle quantum approximate optimization algorithm (MA-QAOA) and automorphic-angle quantum approximate optimization algorithm (AA-QAOA), each presents distinct trade-offs between expressiveness and classical optimization complexity. In this work, we introduce the $k$-interaction-angle quantum approximate optimization algorithm ($k$A-QAOA), a parameterization scheme that groups cost function terms by their $k$-body interaction order, providing a natural middle ground between parameter efficiency and solution quality. This approach is particularly well-suited for combinatorial optimization problems defined on hypergraphs, where multi-body interactions naturally arise in applications such as Boolean satisfiability and resource allocation with multi-party constraints. We benchmark $k$A-QAOA against standard single-angle quantum approximate optimization algorithm (SA-QAOA), MA-QAOA, and AA-QAOA on two problem classes: 3-uniform cyclic sign-alternating hypergraphs and random coefficient hypergraphs. Our results demonstrate that $k$A-QAOA achieves approximation ratios comparable to MA-QAOA while requiring significantly fewer function evaluations, thereby reducing quantum resource consumption.

quant-pharXiv:2605.01620•May 5, 2026•0 citations

A Unified Complexity-Algorithm Account of Constant-Round QAOA Expectation Computation

Jingheng Wang, Shengminjie Chen, Xiaoming Sun +1 more

The Quantum Approximate Optimization Algorithm (QAOA) is widely studied for combinatorial optimization and has achieved significant advances both in theoretical guarantees and practical performance, yet for general combinatorial optimization problems the expected performance and classical simulability of fixed-round QAOA remain unclear. Focusing on Max-Cut, we first show that for general graphs and any fixed round $p\ge2$, exactly evaluating the expectation of fixed-round QAOA at prescribed angles is $\mathrm{NP}$-hard, and that approximating this expectation within additive error $2^{-O(n)}$ in the number $n$ of vertices is already $\mathrm{NP}$-hard. To evaluate the expected performance of QAOA, we propose a dynamic programming algorithm leveraging tree decomposition. As a byproduct, when the $p$-local treewidth grows at most logarithmically with the number of vertices, this yields a polynomial-time \emph{exact} evaluation algorithm in the graph size $n$. Beyond Max-Cut, we extend the framework to general Binary Unconstrained Combinatorial Optimization (BUCO). Finally, we provide reproducible evaluations for rounds up to $p=3$ on representative structured families, including the generalized Petersen graph $GP(15,2)$, double-layer triangular 2-lifts, and the truncated icosahedron graph $C_{60}$, and report cut ratios while benchmarking against locality-matched classical baselines.

quant-pharXiv:2511.20212•Nov 26, 2025•0 citations
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=12∑(i,j)∈E(1−σz(i)σz(j))H_C = \tfrac{1}{2}\sum_{(i,j)\in E}(1-σ_z^{(i)}σ_z^{(j)})HC​=21​∑(i,j)∈E​(1−σz(i)​σz(j)​), the cost expectation aggregation costs O(∣E∣⋅2n)\mathcal{O}(|E|\cdot 2^n)O(∣E∣⋅2n) wall time on a statevector estimator. We show that on the Aut(G)(G)(G)-symmetric state prepared by the standard QAOA ansatz, replacing HCH_CHC​ with an orbit-reduced observable HredH_{\mathrm{red}}Hred​, retaining one representative ZZ term per edge orbit weighted by orbit size, satisfies ⟨Hred⟩=⟨HC⟩\langle H_{\mathrm{red}}\rangle = \langle H_C\rangle⟨Hred​⟩=⟨HC​⟩ exactly, dropping the aggregation cost to O(∣orbits∣⋅2n)\mathcal{O}(|\mathrm{orbits}|\cdot 2^n)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 KnK_nKn​, the star graph, and random 3-regular graphs, as controlled diagnostics that isolate the mechanism. The complete graph K16K_{16}K16​ at p=1p=1p=1 shows an 8×8\times8× 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≈RfullR_{\mathrm{red}}\approx R_{\mathrm{full}}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.
A promising approach to the practical application of the quantum approximate optimization algorithm (QAOA) is finding QAOA parameters classically in simulation and sampling the solutions from QAOA with optimized parameters on a quantum computer. Doing so requires repeated evaluations of QAOA energy in simulation. In this article, we propose a novel approach for accelerating the evaluation of QAOA energy by leveraging the symmetry of the problem. We show a connection between classical symmetries of the objective function and the symmetries of the terms of the cost Hamiltonian with respect to the QAOA energy. We show how by considering only the terms that are not connected by symmetry, we can significantly reduce the cost of evaluating the QAOA energy. Our approach is general and applies to any known subgroup of symmetries and is not limited to graph problems. Our results are directly applicable to nonlocal QAOA generalization recursive QAOA. We outline how available fast graph automorphism solvers can be leveraged for computing the symmetries of the problem in practice. We implement the proposed approach on the MaxCut problem using a state-of-the-art tensor network simulator and a graph automorphism solver on a benchmark of 48 graphs with up to 10 000 nodes. Our approach provides an improvement forp=1p=1p=1on 71.7% of the graphs considered, with a median speedup of 4.06, on a benchmark, where 62.5% of the graphs are known to be hard for automorphism solvers.
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.
Shallow-depth QAOA on sparse, high-diameter MaxCut instances faces a locality bottleneck: at depth ppp, local observables can depend only on a bounded neighborhood of the circuit interaction graph. We propose a transport-augmented QAOA that keeps the MaxCut cost Hamiltonian unchanged but enriches the mixer with optimized, unweighted shortcut couplings (scheduled XX+YYXX+YYXX+YY) to collapse the effective interaction-graph diameter. Using exact finite-depth support recursions, we relate optimal shortcut placement to bounded-diameter graph augmentation, and show in benchmarks that (unlike ma-QAOA) performance becomes effectively size-invariant once the diameter is reduced. For bipartite families (base diameter 4), reducing the interaction path to d=1d=1d=1 raises the ensemble-averaged approximation ratio from 0.7378 (ma-QAOA) to 0.9767 at p=1p=1p=1 (σ=0.0251σ=0.0251σ=0.0251, nine system sizes); on random trees (base diameter 10), at p=2p=2p=2 it improves from 0.9226 to 0.9997 (σ=0.0001σ=0.0001σ=0.0001).
We explore strategies aimed at reducing the amount of computation, both quantum and classical, required to run the Quantum Approximate Optimization Algorithm (QAOA). First, following Wurtz et al. [Phys.Rev A 104:052419], we consider the standard QAOA with instance-independent "tree" parameters chosen in advance. These tree parameters are chosen to optimize the MaxCut expectation for large girth graphs. We provide extensive numerical evidence supporting the performance guarantee for tree parameters conjectured in [Phys.Rev A 103:042612] and see that the approximation ratios obtained with tree parameters are typically well beyond the conjectured lower bounds, often comparable to performing a full optimization. This suggests that in practice, the QAOA can achieve near-optimal performance without the need for parameter optimization. Next, we modify the warm-start QAOA of Tate et al. [Quantum 7:1121]. The starting state for the QAOA is now an optimized product state associated with a solution of the Goemans-Williamson (GW) algorithm. Surprisingly, the tree parameters continue to perform well for the warm-start QAOA. We find that for random 3-regular graphs with hundreds of vertices, the expected cut obtained by the warm-start QAOA at depth p≳3p \gtrsim 3p≳3 is comparable to that of the standard GW algorithm. Our numerics on random instances do not provide general performance guarantees but do provide substantial evidence that there exists a regime of instance sizes in which the QAOA finds good solutions at low depth without the need for parameter optimization. For each instance studied, we classically compute the expected size of the QAOA distribution of cuts; producing the actual cuts requires running on a quantum computer.
The quantum approximate optimization algorithm (QAOA) has emerged as a promising candidate for demonstrating quantum advantage on noisy intermediate-scale quantum (NISQ) devices. While various QAOA parameterization schemes exist, ranging from the original single-angle approach to the more expressive multi-angle quantum approximate optimization algorithm (MA-QAOA) and automorphic-angle quantum approximate optimization algorithm (AA-QAOA), each presents distinct trade-offs between expressiveness and classical optimization complexity. In this work, we introduce the kkk-interaction-angle quantum approximate optimization algorithm (kkkA-QAOA), a parameterization scheme that groups cost function terms by their kkk-body interaction order, providing a natural middle ground between parameter efficiency and solution quality. This approach is particularly well-suited for combinatorial optimization problems defined on hypergraphs, where multi-body interactions naturally arise in applications such as Boolean satisfiability and resource allocation with multi-party constraints. We benchmark kkkA-QAOA against standard single-angle quantum approximate optimization algorithm (SA-QAOA), MA-QAOA, and AA-QAOA on two problem classes: 3-uniform cyclic sign-alternating hypergraphs and random coefficient hypergraphs. Our results demonstrate that kkkA-QAOA achieves approximation ratios comparable to MA-QAOA while requiring significantly fewer function evaluations, thereby reducing quantum resource consumption.
The Quantum Approximate Optimization Algorithm (QAOA) is widely studied for combinatorial optimization and has achieved significant advances both in theoretical guarantees and practical performance, yet for general combinatorial optimization problems the expected performance and classical simulability of fixed-round QAOA remain unclear. Focusing on Max-Cut, we first show that for general graphs and any fixed round p≥2p\ge2p≥2, exactly evaluating the expectation of fixed-round QAOA at prescribed angles is NP\mathrm{NP}NP-hard, and that approximating this expectation within additive error 2−O(n)2^{-O(n)}2−O(n) in the number nnn of vertices is already NP\mathrm{NP}NP-hard. To evaluate the expected performance of QAOA, we propose a dynamic programming algorithm leveraging tree decomposition. As a byproduct, when the ppp-local treewidth grows at most logarithmically with the number of vertices, this yields a polynomial-time \emph{exact} evaluation algorithm in the graph size nnn. Beyond Max-Cut, we extend the framework to general Binary Unconstrained Combinatorial Optimization (BUCO). Finally, we provide reproducible evaluations for rounds up to p=3p=3p=3 on representative structured families, including the generalized Petersen graph GP(15,2)GP(15,2)GP(15,2), double-layer triangular 2-lifts, and the truncated icosahedron graph C60C_{60}C60​, and report cut ratios while benchmarking against locality-matched classical baselines.