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.
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.
Abstract The quantum approximate optimisation algorithm (QAOA) is a hybrid quantum–classical algorithm used to approximately solve combinatorial optimisation problems. It involves multiple iterations of a parameterised ansatz that consists of a problem and mixer Hamiltonian, with the parameters being classically optimised. While QAOA can be implemented on near-term quantum hardware, physical limitations such as gate noise, restricted qubit connectivity, and state-preparation-and-measurement (SPAM) errors can limit circuit depth and decrease performance. To address these limitations, this work introduces the eXpressive QAOA (XQAOA), an overparameterised variant of QAOA that assigns more classical parameters to the ansatz to improve its performance at low depths. XQAOA also introduces an additional Pauli-Y component in the mixer Hamiltonian, allowing the mixer to implement arbitrary unitary transformations on each qubit. To benchmark the performance of XQAOA at unit depth, we derive its closed-form expression for the MaxCut problem and compare it to QAOA, Multi-Angle QAOA (MA-QAOA) (Herrman et al 2022 Sci. Rep. 12 6781), a classical-relaxed algorithm, and the state-of-the-art Goemans–Williamson algorithm on a set of unweighted regular graphs with 128 and 256 nodes for degrees ranging from 3 to 10. Our results indicate that at unit depth, XQAOA has benign loss landscapes with local minima concentrated near the global optimum, allowing it to consistently outperform QAOA, MA-QAOA, and the classical-relaxed algorithm on all graph instances and the Goemans–Williamson algorithm on graph instances with degrees greater than 4. Small-scale simulations also reveal that unit-depth XQAOA invariably surpasses both QAOA and MA-QAOA on all tested depths up to five. Additionally, we find an infinite family of graphs for which XQAOA solves MaxCut exactly and analytically show that for some graphs in this family, special cases of XQAOA are capable of achieving a much larger approximation ratio than QAOA. Overall, XQAOA is a more viable choice for variational quantum optimisation on near-term quantum devices, offering competitive performance at low depths.
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.
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.
The Quantum Approximate Optimization Algorithm (QAOA) is a leading variational approach for combinatorial problems, yet its performance on NISQ hardware is limited depthbounds and challenging parameter landscapes. We propose Enhanced QAOA (EQAOA), a modified ansatz that appends a compact multi-parameter layer and uses a blockwise optimization scheme. This design preserves the QAOA evolution while broadening the candidate solution space and easing solution exploration. Applied to the MaxCut problem across diverse graph families, EQAOA achieves, with an order of magnitude smaller circuit depth, approximation ratios comparable to QAOA, using a single cost–mixer layer, thus reducing gate counts by up to fivefold, as supported by experiments. Moreover, ablation studies prove that blockwise fine-tuning is crucial to deliver higher-quality solutions at shallower depth, offering a practical, quantum hardware-efficient alternative for signal processing applications.
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.
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=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.