Among quantum algorithms, the quantum approximation optimization algorithm (QAOA) is an algorithm that finds approximate solutions. Recursive QAOA is proposed to overcome the limitation that QAOA has lower performance than Goemans-Williamson algorithm in the MAX-CUT problem [Physical Review Letter, 125, 260504, 2020]. In this paper, we introduce a method with lower complexity than RQAOA and compare its numerical results in the MAX-CUT problem. At the same level, the performance of the proposed method is lower than that of RQAOA, but the number of computations of quantum and classical parts is very small.
Among quantum algorithms, the quantum approximation optimization algorithm (QAOA) is an algorithm that finds approximate solutions. Recursive QAOA is proposed to overcome the limitation that QAOA has lower performance than Goemans-Williamson algorithm in the MAX-CUT problem [Physical Review Letter, 125, 260504, 2020]. In this paper, we introduce a method with lower complexity than RQAOA and compare its numerical results in the MAX-CUT problem. At the same level, the performance of the proposed method is lower than that of RQAOA, but the number of computations of quantum and classical parts is very small.
Abstract Quantum approximate optimization algorithm (QAOA) is a quantum–classical hybrid algorithm proposed with the goal of approximately solving combinatorial optimization problems such as the MAX-CUT problem. It has been considered a potential candidate for achieving quantum advantage in the noisy intermediate-scale quantum era and has been extensively studied. However, the performance limitations of low-level QAOA have also been demonstrated across various instances. In this work, we first analytically prove the performance limitations of the standard level-1 QAOA in solving the MAX-CUT problem on bipartite graphs. To this end, we derive an upper bound for the approximation ratio based on the average degree of bipartite graphs. Second, we demonstrate that recursive QAOA (RQAOA), which recursively reduces graph size using QAOA as a subroutine, outperforms the standard level-1 QAOA. However, the performance of RQAOA exhibits limitations as the graph size increases. Finally, we show that RQAOA with a restricted parameter regime can fully address these limitations. Surprisingly, this modified RQAOA always finds the exact maximum cut for any bipartite graphs and even for a more general graph with parity-signed weights.
Recent results on the Quantum Approximate Optimization Algorithm (QAOA) have cast pessimism on its potential to exhibit practical quantum speedups. For instance, QAOA’s locality limits its performance on tasks such as coloring bipartite graphs—which is easy for classical methods. Motivated by these limitations, the Recursive QAOA was introduced to overcome the locality and symmetry of QAOA. Despite being more powerful than QAOA, RQAOA is fully classically simulable at level-1 depth (p = 1). We report results on RQAOA in this classically simulable regime, benchmarked on random Quantum Unconstrainted Binary Optimization (QUBO) problems with up to 100 variables. We find that RQAOA generally matches the performance of classical simulated annealing and significantly outperforms ordinary QAOA.
The Quantum Approximate Optimization Algorithm (QAOA) is one of the promising near-term algorithms designed to find approximate solutions for combinatorial optimization problems. The algorithm prepares a parametrized state that is aimed to maximize the expectation value of the objective function of the problem. The circuit for QAOA consists of p layers, and it depends on 2p parameters, the determination of which can be carried out using a variational quantum eigensolver (VQE) subroutine. This is a variational approach for finding optimal parameters, where the quantum state is prepared with a quantum computer, and a classical computer is used for calculating the corresponding objective function value and performing an outer loop optimization routine in order to find optimal parameters. Earlier work on the algorithm has shown that QAOA is closely related to the Quantum Adiabatic Algorithm, which results in noticeable patterns in the optimal parameters. To this purpose, two methods, INTERP and FOURIER, were proposed to exploit this structure by Zhou et al. (2018). In this thesis, I extend upon these results by examining the effectiveness of one of their methods, the INTERP method, on the Max-Cut problem from graph theory. The performance of QAOA using this method was studied on several classes of graphs and benchmarked against the currently best-known classical algorithm Goemans-Williamson, which achieves an approximation ratio of ρ ≈ 0.878 on arbitrary graphs. The classes of graphs examined include cyclic, weighted and unweighted 3-regular, and Erdős–Rényi graphs with edge probabilities of 0.5 and 0.75 and graph sizes ranging from 4 to 16. Moreover, it was investigated if the INTERP method offers an advantage compared to random initialization of parameters and whether or not the method is polynomial in p. It was found that different graph classes lead to similar but different parameter patterns. Furthermore, the performance of QAOA using the INTERP method was dependent on the graph class considered. For the small graphs investigated it was found that QAOA outperforms Goemans-Williamson on ER-0.50, ER-0.75 and weighted 3-regular graphs from p=7 and beyond with respect to how well the expectation of the objective function approximates the optimal value, while for unweighted 3-regular graphs p=6 suffices. However, the calculation of the parameters is costly and requires a number of function evaluations that is on the order of the number of possible bipartitions of small graph with sizes n ≤ 16. Moreover, the numerical results suggested that indeed the method is polynomial in p advocating that the algorithm might be a strong alternative to Goemans-Williamson for large graph sizes, once hardware allows it.
This study presents a rigorous empirical evaluation of the Quantum Approximate Optimization Algorithm (QAOA) within a hybrid quantum-classical framework for solving the NP-hard Max-Cut problem. Using Python and Qiskit Aer statevector simulations, we benchmark QAOA (depths p = 2 and p = 3) against established classical algorithms, including simulated annealing, the Goemans–Williamson algorithm, and greedy heuristics, across Erdős–Rényi and regular graphs with 4 to 20 nodes (100 instances per size). Results demonstrate that low-depth QAOA suffers from significant performance degradation, achieving a 0.467 approximation ratio at 20 nodes compared to 0.856 for Goemans–Williamson, alongside a 210× runtime overhead. Convergence analysis further reveals low optimality probabilities and high iteration costs, highlighting limitations of variational optimization in NISQ-era devices. This work provides a reproducible benchmarking framework and contributes to a realistic assessment of near-term quantum advantage.
This study presents a rigorous empirical evaluation of the Quantum Approximate Optimization Algorithm (QAOA) within a hybrid quantum-classical framework for solving the NP-hard Max-Cut problem. Using Python and Qiskit Aer statevector simulations, we benchmark QAOA (depths p = 2 and p = 3) against established classical algorithms, including simulated annealing, the Goemans–Williamson algorithm, and greedy heuristics, across Erdős–Rényi and regular graphs with 4 to 20 nodes (100 instances per size). Results demonstrate that low-depth QAOA suffers from significant performance degradation, achieving a 0.467 approximation ratio at 20 nodes compared to 0.856 for Goemans–Williamson, alongside a 210× runtime overhead. Convergence analysis further reveals low optimality probabilities and high iteration costs, highlighting limitations of variational optimization in NISQ-era devices. This work provides a reproducible benchmarking framework and contributes to a realistic assessment of near-term quantum advantage.
Quantum optimization methods use a continuous degree-of-freedom of quantum states to heuristically solve combinatorial problems, such as the MAX-CUT problem, which can be attributed to various NP-hard combinatorial problems. This paper shows that some existing quantum optimization methods can be unified into a solver to find the binary solution which is most likely measured from the optimal quantum state. Combining this finding with the concept of quantum random access codes (QRACs) for encoding bits into quantum states on fewer qubits, we propose an efficient recursive quantum relaxation method called recursive quantum random access optimization (RQRAO) for MAX-CUT. Experiments on standard benchmark graphs with several hundred nodes in the MAX-CUT problem, conducted in a fully classical manner using a tensor network technique, show that RQRAO not only outperforms the Goemans-Williamson and recursive QAOA methods, but also is comparable to state-of-the-art classical solvers. The code is available at https://github.com/ToyotaCRDL/rqrao.