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:2209.11839 · IEEE/ACM Symposium on Edge Computing (SEC)

Multiangle QAOA Does Not Always Need All Its Angles

Kaiyan Shi, Rebekah Herrman, Ruslan Shaydulin, Shouvanik Chakrabarti, Marco Pistoia, Jeffrey M. Larson

Published Dec 1, 2022• 16 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1109/sec54971.2022.00062

Related papers

Improved Performance of Multi-Angle Quantum Approximate Optimization Algorithm (ma-QAOA) Compared to QAOA On Simulation and Experimental Hardware Platforms

Vandit Srivastava, P Rohith, Sanyam Singhal +1 more

Multi-angle quantum approximate optimization algorithm (ma-QAOA) has been proposed as an alternative to regular QAOA for solving optimization problems using noisy intermediate scale quantum (NISQ) hardware. Here, we first implement QAOA and ma-QAOA algorithms to solve MaxCut on weighted and unweighted versions of the Erdős–Rényi (ER) and random cubic (RC) graphs of 6 and 10 nodes. Quantum circuit parameters are updated iteratively through classical feedback with the quantum circuit for forward pass modelled on Qiskit simulator without noise models. Then, the quantum circuit for the final run with updated parameters is implemented on Qiskit simulator without noise models, Qiskit simulator with experimentally benchmarked noise models (fake back-end), and also on actual experimental quantum hardware (IBM’s 127-qubit quantum processor ibm brisbane). We show that for most graph instances, ma-QAOA performs better than QAOA (in terms of approximation ratio (AR)) and needs less stages in the quantum circuit for all three aforementioned methods. Finally, we extend our results up to 14-node RC graphs while restricting ourselves to Qiskit simulation without noise (both for parameter update and final run) and show that for most instances, ma-QAOA again needs much less stages compared to QAOA to obtain reasonable AR.

•Jan 6, 2025•3 citations

Multi-angle quantum approximate optimization algorithm

Rebekah Herrman, Phillip C. Lotshaw, James Ostrowski +2 more

The quantum approximate optimization algorithm (QAOA) generates an approximate solution to combinatorial optimization problems using a variational ansatz circuit defined by parameterized layers of quantum evolution. In theory, the approximation improves with increasing ansatz depth but gate noise and circuit complexity undermine performance in practice. Here, we investigate a multi-angle ansatz for QAOA that reduces circuit depth and improves the approximation ratio by increasing the number of classical parameters. Even though the number of parameters increases, our results indicate that good parameters can be found in polynomial time for a test dataset we consider. This new ansatz gives a 33% increase in the approximation ratio for an infinite family of MaxCut instances over QAOA. The optimal performance is lower bounded by the conventional ansatz, and we present empirical results for graphs on eight vertices that one layer of the multi-angle anstaz is comparable to three layers of the traditional ansatz on MaxCut problems. Similarly, multi-angle QAOA yields a higher approximation ratio than QAOA at the same depth on a collection of MaxCut instances on fifty and one-hundred vertex graphs. Many of the optimized parameters are found to be zero, so their associated gates can be removed from the circuit, further decreasing the circuit depth. These results indicate that multi-angle QAOA requires shallower circuits to solve problems than QAOA, making it more viable for near-term intermediate-scale quantum devices.

arXiv:2109.11455•Scientific Reports•Apr 26, 2022•117 citations

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

The Symmetry‐Based Expressive QAOA for the MaxCut Problem

Zhao Xiumei, Yongmei Li, Guanghui Li +3 more

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.

Advanced Quantum Technologies•May 28, 2025•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

Classical symmetries and QAOA

Ruslan Shaydulin, Stuart Hadfield, Tad Hogg +1 more

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.

•Dec 8, 2020•14 citations
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.
Multi-angle quantum approximate optimization algorithm (ma-QAOA) has been proposed as an alternative to regular QAOA for solving optimization problems using noisy intermediate scale quantum (NISQ) hardware. Here, we first implement QAOA and ma-QAOA algorithms to solve MaxCut on weighted and unweighted versions of the Erdős–Rényi (ER) and random cubic (RC) graphs of 6 and 10 nodes. Quantum circuit parameters are updated iteratively through classical feedback with the quantum circuit for forward pass modelled on Qiskit simulator without noise models. Then, the quantum circuit for the final run with updated parameters is implemented on Qiskit simulator without noise models, Qiskit simulator with experimentally benchmarked noise models (fake back-end), and also on actual experimental quantum hardware (IBM’s 127-qubit quantum processor ibm brisbane). We show that for most graph instances, ma-QAOA performs better than QAOA (in terms of approximation ratio (AR)) and needs less stages in the quantum circuit for all three aforementioned methods. Finally, we extend our results up to 14-node RC graphs while restricting ourselves to Qiskit simulation without noise (both for parameter update and final run) and show that for most instances, ma-QAOA again needs much less stages compared to QAOA to obtain reasonable AR.
The quantum approximate optimization algorithm (QAOA) generates an approximate solution to combinatorial optimization problems using a variational ansatz circuit defined by parameterized layers of quantum evolution. In theory, the approximation improves with increasing ansatz depth but gate noise and circuit complexity undermine performance in practice. Here, we investigate a multi-angle ansatz for QAOA that reduces circuit depth and improves the approximation ratio by increasing the number of classical parameters. Even though the number of parameters increases, our results indicate that good parameters can be found in polynomial time for a test dataset we consider. This new ansatz gives a 33% increase in the approximation ratio for an infinite family of MaxCut instances over QAOA. The optimal performance is lower bounded by the conventional ansatz, and we present empirical results for graphs on eight vertices that one layer of the multi-angle anstaz is comparable to three layers of the traditional ansatz on MaxCut problems. Similarly, multi-angle QAOA yields a higher approximation ratio than QAOA at the same depth on a collection of MaxCut instances on fifty and one-hundred vertex graphs. Many of the optimized parameters are found to be zero, so their associated gates can be removed from the circuit, further decreasing the circuit depth. These results indicate that multi-angle QAOA requires shallower circuits to solve problems than QAOA, making it more viable for near-term intermediate-scale quantum devices.
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.
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.
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.
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.