搜索

x
中国物理学会期刊

面向最大割问题的量子近似优化算法设计

CSTR: 32037.14.aps.74.20241223

Design of quantum approximation optimization algorithm for the maximum cut problem

CSTR: 32037.14.aps.74.20241223
PDF
HTML
导出引用
  • 量子近似优化算法(QAOA)作为含噪的中等规模量子(NISQ)计算时代的重要算法, 在最大割问题上展现了极大的优势和潜力. 然而由于缺乏量子纠错的支持, 在NISQ体系中计算的可靠性会随着算法的线路深度增加而急剧下降. 这样, 如何针对最大割问题设计高效的浅层低复杂度QAOA, 是当前NISQ时代展现量子计算优势所面临的一个重要挑战. 本文在标准QAOA算法解决最大割问题的目标哈密顿量线路中引入泡利Y旋转门, 通过提高量子试探函数在单次迭代中的操控灵活性和希尔伯特空间的检索效率, 显著提升了QAOA在最大割问题上的性能表现. 基于MindSpore Quantum平台的模拟实验表明, 与标准QAOA及当前其主流变体MA-QAOA和QAOA+等相比, 本文提出的QAOA新变体——RY层辅助QAOA在可降低线路深度、减少CNOT双比特量子逻辑门数量的同时, 依然可达到更优的逼近率, 具备更高可靠性的潜力.

     

    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.

     

    目录

    /

    返回文章
    返回