-
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.
-
Keywords:
- QAOA /
- MaxCut /
- Quantum computing /
- Quantum circuit
-
图 1 (a) 由问题酉算符和混合酉算符构成的单层QAOA量子线路框图; (b)标准QAOA的问题酉算符(蓝色)和混合酉算符(紫色)的分解; (c)MA-QAOA问题酉算符(蓝色)和混合酉算符(紫色)的分解; (d) RY层辅助QAOA问题酉算符(蓝色)和混合酉算符(紫色)的分解
Figure 1. (a) Single-layer QAOA quantum circuit diagram composed of problem and mixing operators; (b) Decomposition of the problem operator (blue) and mixing operator (purple) in standard QAOA; (c) Decomposition of the problem operator (blue) and mixing operator (purple) in MA-QAOA; (d) Decomposition of the problem operator (blue) and mixing operator (purple) in RY-layer-assisted QAOA
图 2 (a)增加了问题无关层的QAOA+的量子线路框图; [22](b) QAOA+问题无关层的分解
Figure 2. (a) The QAOA+ quantum circuit includes a standard QAOA layer and an additional problem-independent multi-parameter layer; (b) The decomposition of the problem-independent multi-parameter layer
图 3 实验采用的四类图 (a)完全图; (b) 3-正则图; (c) 4-正则图; (d)边概率在0.3到0.5之间的随机图
Figure 3. The four types of graphs adopted in the experiments (a) complete graphs; (b) 3-regular graphs; (c) 4-regular graphs; (d) random graphs with edge probabilities between 0.3 and 0.5
图 4 单层QAOA、MA-QAOA、QAOA+和RY层辅助QAOA分别在四类图上的平均逼近率 (a)完全图; (b) 3-regular图; (c) 4-regular图; (d)随机图. 这里的问题图由NetworkX库随机生成
Figure 4. Average approximation ratios of single-layer QAOA, MA-QAOA, QAOA+, and RY-layer-assisted QAOA on the four types of graphs (a) complete graphs; (b) 3-regular graphs; (c) 4-regular graphs; (d) random graphs. The problem instances are randomly generated using the NetworkX library
图 5 标准QAOA(包括单层和双层)及其各变体在8节点各类型图上的资源消耗及性能表现
Figure 5. Resource consumption and performance of standard QAOA (including single-layer and double-layer) and its variants on 8-node graphs of various types.
图 6 噪声条件下, 标准QAOA(双层)及RY层辅助QAOA在5—10节点4-正则图上的平均逼近率
Figure 6. Average approximation ratios of standard QAOA (two-layer) and RY-layer-assisted QAOA on 4-regular graphs with 5 to 10 nodes under noisy conditions.
表 1 100个8节点随机问题图上, 各变体达到0.9的逼近率需要的平均线路深度、参数数量及CNOT门数
Table 1. The average circuit depth, number of parameters, and number of CNOT gates required for each variant to achieve an approximation ratio of 0.9 on 100 random 8-node problem graphs.
变体 线路深度 参数数量 CNOT门数量 QAOA 61.09 7.54 104.96 MA-QAOA 31.76 84.61 53.73 QAOA+ 50.09 38.52 89.54 RY层辅助QAOA 21.92 29.84 27.84 
DownLoad: CSV
-
[1] Cook W, Lovász L, Seymour P D 1995 Combinatorial optimization: papers from the DIMACS Special Year, vol. 20 (American Mathematical Soc.
[2] Håstad J 2001 JACM 48 798
Google Scholar
[3] Goemans M X, Williamson D P 1995 JACM 42 1115
Google Scholar
[4] Preskill J 2018 Quantum 2 79
Google Scholar
[5] Cruz D, Fournier R, Gremion F, Jeannerot A, Komagata K, Tosic T, Thiesbrummel J, Chan C L, Macris N, Dupertuis M A, et al 2019 Adv. Quantum Technol. 2 1900015
Google Scholar
[6] Zhang J, Hegde S S, Suter D 2020 Phys. Rev. Lett. 125 030501
Google Scholar
[7] Wernsdorfer W, Godfrin C, Balestro F 2019 In APS March Meeting Abstracts, vol. 2019. p S36
[8] Borle A, Elfving V, Lomonaco S J 2021 SciPost Phys. Core 4 031
Google Scholar
[9] Farhi E, Goldstone J, Gutmann S 2014 arXiv: 1411.4028[quant-ph]
[10] Guerreschi G G, Matsuura A Y 2019 Sci. Rep. 9 6903
Google Scholar
[11] Herrman R, Ostrowski J, Humble T S, Siopsis G 2021 Quantum Inf. Process. 20 1
Google Scholar
[12] Wurtz J, Lykov D 2021 Phys. Rev. A 104 052419
Google Scholar
[13] Akshay V, Philathong H, Morales M E, Biamonte J D 2020 Phys. Rev. Lett. 124 090504
Google Scholar
[14] Wurtz J, Love P 2021 Phys. Rev. A 103 042612
Google Scholar
[15] Farhi E, Gamarnik D, Gutmann S 2020 arXiv: 2005.08747[quant-ph]
[16] 薛程, 陈昭昀, 吴玉椿, 郭国平 2021 中国物理快报 38 030302
Google Scholar
Xue C, Chen Z Y, Wu Y C, Guo G P 2021 Chinese Phys. Lett. 38 030302
Google Scholar
[17] Wang S, Fontana E, Cerezo M, Sharma K, Sone A, Cincio L, Coles P J 2021 Nat. Commun. 12 6961
Google Scholar
[18] Marshall J, Wudarski F, Hadfield S, Hogg T 2020 IOPSN 1 025208
[19] Alam M, Ash-Saki A, Ghosh S 2019 arXiv: 1907.09631[quant-ph]
[20] Chandarana P, Hegade N N, Paul K, Albarrán-Arriagada F, Solano E, Del Campo A, Chen X 2022 Phys. Rev. Res. 4 013141
Google Scholar
[21] Magann A B, Rudinger K M, Grace M D, Sarovar M 2022 Phys. Rev. A 106 062414
Google Scholar
[22] Chalupnik M, Melo H, Alexeev Y, Galda A 2022 In 2022 IEEE International Conference on Quantum Computing and Engineering (QCE) (IEEE), p 97
[23] Sun Z H, Wang Y Y, Cui J, Fan H 2023 NJP 25 013015
Google Scholar
[24] Wurtz J, Love P J 2021 TQE 2 1
[25] Wang Z D, Zheng P L, Wu B, Zhang Y 2022 arXiv: 2203.10101[quant-ph]
[26] Herrman R, Lotshaw P C, Ostrowski J, Humble T S, Siopsis G 2022 Sci. Rep. 12 6781
Google Scholar
[27] Xu X, Cui J, Cui Z, He R, Li Q, Li X, Lin Y, Liu J, Liu W, Lu J, et al. 2024 arXiv: 2406.17248[quant-ph]
[28] AbuGhanem M 2024 arXiv: 2410.00916[quant-ph]
DownLoad:
Metrics
- Abstract views: 247
- PDF Downloads: 7
- Cited By: 0
