物理学报2025，Vol.74Issue(8)：1-9,9.DOI:10.7498/aps.74.20241223
面向最大割问题的量子近似优化算法设计
Design of quantum approximation optimization algorithm for the maximum cut problem
摘要
Abstract
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.关键词
量子近似优化算法/最大割/量子计算/量子线路Key words
quantum approximate optimization algorithm/max-cut/quantum computing/quantum circuit引用本文复制引用
王云江,习汇明,肖卓彦,王增斌,石莎..面向最大割问题的量子近似优化算法设计[J].物理学报,2025,74(8):1-9,9.基金项目
国家自然科学基金(批准号:62471368)、广东省自然科学基金(批准号:2023A1515010671)、陕西省重点研发计划(批准号:2023-YBGY-206,2024GX-YBXM-069)和陕西高校青年创新团队资助的课题. Project supported by the National Natural Science Foundation of China(Grant No.62471368),the Natural Science Foundation of Guangdong Province,China(Grant No.2023A1515010671),the Key Research and Development Project of Shannxi Province,China(Grant Nos.2023-YBGY-206,2024GX-YBXM-069),and the Young Innovation Team in Colleges and Universities of Shannxi Province,China. （批准号:62471368）
