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:2312.06181 · Physical Review A

Multiscale quantum approximate optimization algorithm

Ping Zou

Published Jan 17, 2025• 2 citations
arXivHTMLPDF

Abstract

The quantum approximate optimization algorithm (QAOA) is one of the canonical algorithms designed to find approximate solutions for combinatorial optimization problems on current noisy intermediate-scale quantum (NISQ) devices. The primary focus of ongoing research is to exhibit its speed advantage over classical algorithms. However, the performance of QAOA is restricted at lower depths, while higher depths are limited by current experimental techniques. We propose an algorithm that amalgamates the capabilities of QAOA and the real-space renormalization group transformation. Numerical simulations indicate that our proposed algorithm can deliver precise solutions for specific randomly generated instances using QAOA at shallow depths, even at the lowest depth. This algorithm is particularly suitable for current NISQ devices, offering the potential to demonstrate a quantum advantage.

DOI
10.1103/physreva.111.012427

Related papers

Enhanced multiscale quantum approximate optimization algorithm in multibody combinatorial optimization problems

Leilei Chen, Ping Zou, Ya‐Fei Yu

Abstract At present, the quantum approximate optimization algorithm (QAOA) faces scalability challenges in high-dimensional combinatorial optimization problems due to exponentially growing computational costs and reachability deficits for noisy intermediate-scale quantum (NISQ) devices. This study focuses on the multiscale quantum approximate optimization algorithm (MQAOA), which integrates renormalization group (RG) transformations with QAOA to address these limitations. Based on the connections between the variables in the problem to be solved, the weighted maximal matching method is employed to generate a variable partitioning strategy guiding the RG transformation. This approach not only extends the applicability of MQAOA to satisfiability (SAT) problems — including those with three-body and higher-order interactions in the problem Hamiltonian — but also eliminates the algorithm’s sensitivity to problem density. Validations conducted on quantum simulators show that, after running two-round MQAOA, its capability is enhanced to identify optimal solutions with approximately 97% success probability as defined by the ground-state overlap for Max-2-SAT problems (78% success probability for Max-3-SAT problems). The results confirm the feasibility of MQAOA and establish it as a resource-efficient framework for complex combinatorial optimization problems, providing a pathway for NISQ-era deployment.

Chinese Physics B•Dec 9, 2025•0 citations

Design-Space Exploration of Quantum Approximate Optimization Algorithm under Noise

Mahabubul Alam, Abdullah Ash Saki, Swaroop Ghosh

Quantum approximate optimization algorithm (QAOA) is a promising quantum-classical hybrid technique to solve NP-hard problems in near-term gate-based noisy quantum devices. In QAOA, the gate parameters of a parameterized quantum circuit (PQC) are varied by a classical optimizer to generate a quantum state with a significant support to the optimal solution. The existing analysis fails to consider nonidealities in the qubit quality i.e., short lifetime and imperfect gate operations in a realistic quantum hardware. In this article, we study the impact of various noise sources on the performance of QAOA both in simulation and on a real quantum computer from IBM. Our analysis indicates that QAOA performance is noise-sensitive (especially higher-depth QAOA instances). Therefore, the optimal number of stages (p-value) for any QAOA instance is limited by the noise in the target hardware as opposed to the current perception that QAOA will provide monotonically better performance with higher-depth. We show that the two-qubit gate error has to be decreased by more than 75% of the current state-of-the-art levels to attain a performance within 10% of the maximum value for the lowest-depth QAOA.

Custom Integrated Circuits Conference•Mar 1, 2020•28 citations

Analysis of Quantum Approximate Optimization Algorithm under Realistic Noise in Superconducting Qubits

Mahabubul Alam, Abdullah Ash Saki, Swaroop Ghosh

The quantum approximate optimization algorithm (QAOA) is a promising quantum-classical hybrid technique to solve combinatorial optimization problems in near-term gate-based noisy quantum devices. In QAOA, the objective is a function of the quantum state, which itself is a function of the gate parameters of a multi-level parameterized quantum circuit (PQC). A classical optimizer varies the continuous gate parameters to generate distributions (quantum state) with significant support to the optimal solution. Even at the lowest circuit depth, QAOA offers non-trivial provable performance guarantee which is expected to increase with the circuit depth. However, the existing analysis fails to consider non-idealities in the qubit quality i.e., short lifetime and imperfect gate operations in realistic quantum hardware. In this article, we investigate the impact of various noise sources on the performance of QAOA both in simulation and on a real quantum computer from IBM. Our analyses indicate that the optimal number of stages (p-value) for any QAOA instance is limited by the noise characteristics (gate error, coherence time, etc.) of the target hardware as opposed to the current perception that higher-depth QAOA will provide monotonically better performance for a given problem compared to the low-depth implementations.

arXiv:1907.09631•Jul 13, 2019•33 citations

Efficient Classical Computation of Quantum Mean Values for Shallow QAOA Circuits

Wei-Feng Zhuang, Ya-Nan Pu, Hong-Ze Xu +9 more

The Quantum Approximate Optimization Algorithm (QAOA), which is a variational quantum algorithm, aims to give sub-optimal solutions of combinatorial optimization problems. It is widely believed that QAOA has the potential to demonstrate application-level quantum advantages in the noisy intermediate-scale quantum(NISQ) processors with shallow circuit depth. Since the core of QAOA is the computation of expectation values of the problem Hamiltonian, an important practical question is whether we can find an efficient classical algorithm to solve quantum mean value in the case of general shallow quantum circuits. Here, we present a novel graph decomposition based classical algorithm that scales linearly with the number of qubits for the shallow QAOA circuits in most optimization problems except for complete graph case. Numerical tests in Max-cut, graph coloring and Sherrington-Kirkpatrick model problems, compared to the state-of-the-art method, shows orders of magnitude performance improvement. Our results are not only important for the exploration of quantum advantages with QAOA, but also useful for the benchmarking of NISQ processors.

arXiv:2112.11151•Dec 21, 2021•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

Quantum approximate optimization and k-means algorithms for data clustering

Jirawat Saiphet, Sujin Suwanna, Thiparat Chotibut +1 more

Abstract Noisy intermediate-scale quantum (NISQ) devices are cutting-edge technology expected to demonstrate potential and advantages of quantum computing over classical computing. Its low number of qubits and imperfection from noises restrict running full-scale quantum algorithms on such devices; however, quantum advantages can still be obtained. To achieve quantum advantages from NISQ devices, the hybrid quantum-classical algorithms were introduced. Quantum approximate optimization algorithm (QAOA) is a variational hybrid algorithm, which utilizes a NISQ device as a sub-unit for specific tasks and performs most calculations on a classical computer. QAOA provides an approximate solution, with arbitrary precision as the number of operations increases, for optimization problems. In this work we investigate the possibility of applying QAOA to a clustering problem and compare its performance with the classical k-means algorithm. It turns out that the weights in graph connectivity can degrade the algorithm operation and make it more difficult to approximate the solution. We also benchmark the QAOA by comparing the approximated solutions with the exact one obtained from a classical clustering algorithm.

Journal of Physics Conference Series•Jan 1, 2021•3 citations
The quantum approximate optimization algorithm (QAOA) is one of the canonical algorithms designed to find approximate solutions for combinatorial optimization problems on current noisy intermediate-scale quantum (NISQ) devices. The primary focus of ongoing research is to exhibit its speed advantage over classical algorithms. However, the performance of QAOA is restricted at lower depths, while higher depths are limited by current experimental techniques. We propose an algorithm that amalgamates the capabilities of QAOA and the real-space renormalization group transformation. Numerical simulations indicate that our proposed algorithm can deliver precise solutions for specific randomly generated instances using QAOA at shallow depths, even at the lowest depth. This algorithm is particularly suitable for current NISQ devices, offering the potential to demonstrate a quantum advantage.
Abstract At present, the quantum approximate optimization algorithm (QAOA) faces scalability challenges in high-dimensional combinatorial optimization problems due to exponentially growing computational costs and reachability deficits for noisy intermediate-scale quantum (NISQ) devices. This study focuses on the multiscale quantum approximate optimization algorithm (MQAOA), which integrates renormalization group (RG) transformations with QAOA to address these limitations. Based on the connections between the variables in the problem to be solved, the weighted maximal matching method is employed to generate a variable partitioning strategy guiding the RG transformation. This approach not only extends the applicability of MQAOA to satisfiability (SAT) problems — including those with three-body and higher-order interactions in the problem Hamiltonian — but also eliminates the algorithm’s sensitivity to problem density. Validations conducted on quantum simulators show that, after running two-round MQAOA, its capability is enhanced to identify optimal solutions with approximately 97% success probability as defined by the ground-state overlap for Max-2-SAT problems (78% success probability for Max-3-SAT problems). The results confirm the feasibility of MQAOA and establish it as a resource-efficient framework for complex combinatorial optimization problems, providing a pathway for NISQ-era deployment.
Quantum approximate optimization algorithm (QAOA) is a promising quantum-classical hybrid technique to solve NP-hard problems in near-term gate-based noisy quantum devices. In QAOA, the gate parameters of a parameterized quantum circuit (PQC) are varied by a classical optimizer to generate a quantum state with a significant support to the optimal solution. The existing analysis fails to consider nonidealities in the qubit quality i.e., short lifetime and imperfect gate operations in a realistic quantum hardware. In this article, we study the impact of various noise sources on the performance of QAOA both in simulation and on a real quantum computer from IBM. Our analysis indicates that QAOA performance is noise-sensitive (especially higher-depth QAOA instances). Therefore, the optimal number of stages (p-value) for any QAOA instance is limited by the noise in the target hardware as opposed to the current perception that QAOA will provide monotonically better performance with higher-depth. We show that the two-qubit gate error has to be decreased by more than 75% of the current state-of-the-art levels to attain a performance within 10% of the maximum value for the lowest-depth QAOA.
The quantum approximate optimization algorithm (QAOA) is a promising quantum-classical hybrid technique to solve combinatorial optimization problems in near-term gate-based noisy quantum devices. In QAOA, the objective is a function of the quantum state, which itself is a function of the gate parameters of a multi-level parameterized quantum circuit (PQC). A classical optimizer varies the continuous gate parameters to generate distributions (quantum state) with significant support to the optimal solution. Even at the lowest circuit depth, QAOA offers non-trivial provable performance guarantee which is expected to increase with the circuit depth. However, the existing analysis fails to consider non-idealities in the qubit quality i.e., short lifetime and imperfect gate operations in realistic quantum hardware. In this article, we investigate the impact of various noise sources on the performance of QAOA both in simulation and on a real quantum computer from IBM. Our analyses indicate that the optimal number of stages (p-value) for any QAOA instance is limited by the noise characteristics (gate error, coherence time, etc.) of the target hardware as opposed to the current perception that higher-depth QAOA will provide monotonically better performance for a given problem compared to the low-depth implementations.
The Quantum Approximate Optimization Algorithm (QAOA), which is a variational quantum algorithm, aims to give sub-optimal solutions of combinatorial optimization problems. It is widely believed that QAOA has the potential to demonstrate application-level quantum advantages in the noisy intermediate-scale quantum(NISQ) processors with shallow circuit depth. Since the core of QAOA is the computation of expectation values of the problem Hamiltonian, an important practical question is whether we can find an efficient classical algorithm to solve quantum mean value in the case of general shallow quantum circuits. Here, we present a novel graph decomposition based classical algorithm that scales linearly with the number of qubits for the shallow QAOA circuits in most optimization problems except for complete graph case. Numerical tests in Max-cut, graph coloring and Sherrington-Kirkpatrick model problems, compared to the state-of-the-art method, shows orders of magnitude performance improvement. Our results are not only important for the exploration of quantum advantages with QAOA, but also useful for the benchmarking of NISQ processors.
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 Noisy intermediate-scale quantum (NISQ) devices are cutting-edge technology expected to demonstrate potential and advantages of quantum computing over classical computing. Its low number of qubits and imperfection from noises restrict running full-scale quantum algorithms on such devices; however, quantum advantages can still be obtained. To achieve quantum advantages from NISQ devices, the hybrid quantum-classical algorithms were introduced. Quantum approximate optimization algorithm (QAOA) is a variational hybrid algorithm, which utilizes a NISQ device as a sub-unit for specific tasks and performs most calculations on a classical computer. QAOA provides an approximate solution, with arbitrary precision as the number of operations increases, for optimization problems. In this work we investigate the possibility of applying QAOA to a clustering problem and compare its performance with the classical k-means algorithm. It turns out that the weights in graph connectivity can degrade the algorithm operation and make it more difficult to approximate the solution. We also benchmark the QAOA by comparing the approximated solutions with the exact one obtained from a classical clustering algorithm.