Quantum approximate optimization algorithm for the Max-Cut problem: a case study for random graph topologies

Reuben Tate, Swati Gupta

Huy Phuc Nguyen Ha, Viết Hùng Nguyễn, Anh Son Ta

Yun-Jiang Wang, XI Huiming, XIAO Zhuoyan +2 more

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.

Nicholas J. Guerrero

Sowmya B J, Geetha J, Vijaya Kumar B P +3 more

This paper presents an experimental study of the Quantum Approximate Optimization Algorithm (QAOA) applied to the Max-Cut problem on small graph instances. Using PennyLane and a quantum simulator, a modular QAOA framework is implemented and evaluated on a fixed set of graphs, including ring, complete, star, and random graphs. For each graph, QAOA circuits with one and two layers are optimized using gradient-based methods, and the optimized states are sampled to obtain candidate cut solutions. The analysis includes visualizations of graph structures, cut partitions, bitstring distributions, and quantum circuit diagrams. This study serves as a clear and reproducible demonstration of QAOA behavior on combinatorial optimization problems.

Kunal Marwaha

The p -stage Quantum Approximate Optimization Algorithm (QAOA p ) is a promising approach for combinatorial optimization on noisy intermediate-scale quantum (NISQ) devices, but its theoretical behavior is not well understood beyond p=1 . We analyze QAOA 2 for the maximum cut problem (MAX-CUT), deriving a graph-size-independent expression for the expected cut fraction on any D -regular graph of girth >5 (i.e. without triangles, squares, or pentagons).We show that for all degrees D≥2 and every D -regular graph G of girth >5 , QAOA 2 has a larger expected cut fraction than QAOA 1 on G . However, we also show that there exists a 2 -local randomized classical algorithm A such that A has a larger expected cut fraction than QAOA 2 on all G . This supports our conjecture that for every constant p , there exists a local classical MAX-CUT algorithm that performs as well as QAOA p on all graphs.