The Max-Cut Problem (MCP) is a classic problem in the field of combinatorial optimization and has important applications in various domains, including statistical physics and image processing. However, except for some special cases, the Max-Cut problem remains 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 Max-Cut problem. 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 Max-Cut problem is a critical challenge in demonstrating the advantages of quantum computing in the NISQ era.
In this paper, based on the standard QAOA algorithm, we introduce Pauli Y rotation gates into the target Hamiltonian circuit for the Max-Cut problem. 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 Max-Cut problem.
We conduct extensive numerical simulations using the MindSpore Quantum platform, comparing 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 demonstrate that the RY-layer-assisted QAOA achieves a higher approximation ratio across all graph types, particularly in regular and random graphs, where traditional QAOA variants struggle. Moreover, the proposed method exhibits strong robustness as the graph size increases, maintaining high performance even for larger graphs. Importantly, the RY-layer-assisted QAOA requires fewer CNOT gates and has a lower circuit depth compared to 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 offers a promising approach to solving Max-Cut problems in the NISQ era. By improving the approximation ratio while reducing circuit complexity, this method demonstrates significant potential for practical quantum computing applications, paving the way for more efficient and reliable quantum optimization algorithms.