BROWSE
Detail
Journal Article
Modified recursive QAOA for exact MAX-CUT solutions on bipartite graphs: closing the gap beyond QAOA limit
- Authors
- Eunok Bae, Hyukjoon Kwon, V Vijendran, Soojoon Lee
- Issue Date
- 2025-12
- Citation
- Journal of Physics A: Mathematical and Theoretical, v.58, pp.1-22
- ISSN
- 1751-8113
- Publisher
- Institute of Physics Publishing
- Language
- English
- Type
- Journal Article
- 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.
- KSP Keywords
- Approximate optimization, Approximation ratio, Average degree, Bipartite graph, Hybrid algorithm, Max-Cut, Maximum cut, Optimization Algorithm, Performance limitations, Upper bounds, combinatorial optimization problems(COPs)
This work is distributed under the term of Creative Commons License (CCL)
(CC BY)
(CC BY)
