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, Debanjan Bhowmik
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.
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.
We implement Quantum Approximate Optimization Algorithm (QAOA) on NP-Hard problem MaxCut (for 3-chain and 4-node chain graphs, and 4-node and 6node Mobius Ladder graphs) on a quantum simulator without noise, a simulator with experimentally bench-marked noise (fake back-end), and 5-qubit and 7-qubit processors. We use the following modes of operation: QAOA parameters updated through forward pass on the quantum circuit, modelled by the noiseless simulator as well as fake back-end, and the quantum circuit for final run with updated parameters implemented on the noiseless simulator, fake back-end, and real quantum processors. While QAOA yields higher approximation ratio compared to random guess for almost all graph instances, we also conclude that given the noise in existing quantum hardware, a quantum circuit with more than two stages is not suitable for experimental implementation of QAOA currently.
The standard quantum approximate optimization algorithm (QAOA) has a limited expressive power in shallow circuits, whereas naively increasing the number of layers leads to greater quantum circuit depth and higher noise sensitivity. To address this trade-off, based on the ideas of the multi-angle quantum approximate optimization algorithm (MA-QAOA) and the RY-layer-assisted quantum approximate optimization algorithm (RY-QAOA), this paper proposes an improved algorithm, i.e., MA-RY-QAOA, which integrates parameter multangularization and RY-assisted architecture. In MA-RY-QAOA, the problem block incorporates edge parameter multangularization together with RY extension, while the mixer block implements qubit parameter multangularization. For layer number p=1 and node size n=4~12 , we conduct 50 simulation trials on maximum cut problem respectively for random graph with edge probability of 0.8, complete graph, 2-regular graph and 4-regular graph, by using the average approximation ratio as the evaluation metric. The simulation trial results show that, across these four class graphs, the average approximation ratio of MA-RY-QAOA and MA-QAOA significantly outperforms standard QAOA, RY-QAOA, and QAOA+ for overwhelming majority of node sizes; with respect to complete graph, the average approximation ratio of MA-QAOA outperforms that of MA-RY-QAOA for all node sizes; with regard to 2-regular graph, the average approximation ratio of MA-RY-QAOA exceeds that of MA-QAOA for all node sizes; with regard to 4-regular graph, the average approximation ratio of MA-RY-QAOA takes advantage over that of MA-QAOA for overwhelming majority of node sizes; concerning random graph, the average approximation ratio of MA-RY-QAOA is superior to that of MA-QAOA for both small node sizes and large node sizes, but is inferior to that of MA-QAOA for medium node sizes. Therefore, MA-RY-QAOA provides a useful reference for the structure design of shallow-layer QAOA on noisy intermediate-scale quantum (NISQ) devices.
To address the limited expressive capability of the standard quantum approximate optimization algorithm (QAOA) in shallow circuits and the increased noise sensitivity caused by deeper quantum circuits, an improved QAOA, termed MA-RY-QAOA, was proposed by integrating parameter multi-angleization and an RY-assisted structure. In the proposed algorithm, edge-parameter multi-angleization and RY expansion were incorporated into the problem layer, while qubit-parameter multi-angleization was introduced into the mixing layer. Simulation experiments were conducted on the Max-cut problem of random graphs, complete graphs, 2-regular graphs, and 4-regular graphs with circuit depth ( p=1 <?fx-imagestate width="7.45066643" height="2.87866688"?> <?fx-imagestate width="7.45066643" height="2.87866688"?> ) and node sizes ranging from 4 to 12. The average approximation ratio was adopted as the evaluation metric. The results showed that the average approximation ratios achieved by MA-RY-QAOA and MA-QAOA were generally superior to those obtained by the standard QAOA, RY-QAOA, and QAOA+ algorithms. In particular, MA-RY-QAOA exhibited better performance on 2-regular and 4-regular graphs and achieved higher approximation ratios for certain scales of random graphs. These findings indicate that MA-RY-QAOA improves optimization performance while maintaining a shallow circuit structure and provides a useful reference for the design of QAOA variants on noisy intermediate-scale quantum (NISQ) devices.
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.
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.
The max-cut problem (MCP) is a classic problem in the field of combinatorial optimization and has important applications in various fields, including statistical physics and image processing. However, except for some special cases, the MCP still encounters a non-deterministic polynomial complete problem (an NP-complete problem), and there is currently no known efficient classical algorithm that can solve it in polynomial time. The quantum approximate optimization algorithm (QAOA), as a pivotal algorithm in the noisy intermediate-scale quantum (NISQ) computing era, has shown significant potential for solving the MCP. However, due to the lack of quantum error correction, the reliability of computations in NISQ systems sharply declines as the circuit depth of the algorithm increases. Therefore, designing an efficient, shallow-depth, and low-complexity QAOA for the MCP is a critical challenge in demonstrating the advantages of quantum computing in the NISQ era.In this paper, according to the standard QAOA algorithm, we introduce Pauli Y rotation gates into the target Hamiltonian circuit for the MCP. By enhancing the flexibility of quantum trial functions and improving the efficiency of Hilbert space exploration within a single iteration, we significantly improve the performance of QAOA on the MCP.We conduct extensive numerical simulations using the MindSpore quantum platform, and compare the proposed RY-layer-assisted QAOA with standard QAOA and its existing variants, including MA-QAOA and QAOA+. The experiments are performed on various graph types, including complete graphs, 3-regular graphs, 4-regular graphs, and random graphs with edge probabilities between 0.3 and 0.5. Our results show that the RY-layer-assisted QAOA achieves higher approximation ratios in all graph types, particularly in regular and random graphs, where traditional QAOA variants are difficult to implement. Moreover, the proposed method exhibits strong robustness as the graph size increases, and can maintain high performance even for larger graphs. Importantly, the RY-layer-assisted QAOA requires fewer CNOT gates and has a lower circuit depth than the standard QAOA and its variants, making it more suitable for NISQ devices with limited coherence times and high error rates.In conclusion, the RY-layer-assisted QAOA provides a promising approach for solving MCP in the NISQ era. By improving the approximation ratio while reducing circuit complexity, this method demonstrates significant potential for practical quantum computing applications, thus paving the way for developing more efficient and reliable quantum optimization algorithms.