中国物理B ›› 2026, Vol. 35 ›› Issue (7): 70305-070305.doi: 10.1088/1674-1056/ae29f7

• • 上一篇    下一篇

Enhanced multiscale quantum approximate optimization algorithm in multibody combinatorial optimization problems

Lei-Lei Chen(陈蕾蕾)1, Ping Zou(邹平)1,†, and Ya-Fei Yu(於亚飞)1,2,‡   

  1. 1 Guangdong Provincial Key Laboratory of Nanophotonic Functional Materials and Devices, School of Optoelectronic Science and Engineering, South China Normal University, Guangzhou 510006, China;
    2 Quantum Science Center of Guangdong-Hong Kong-Macao Greater Bay Area, Shenzhen 518109, China
  • 收稿日期:2025-07-17 修回日期:2025-11-26 接受日期:2025-12-09 发布日期:2026-07-21
  • 通讯作者: Ping Zou, Ya-Fei Yu E-mail:zouping@m.scnu.edu.cn;yuyafei@m.scnu.edu.cn
  • 基金资助:
    Project supported by the National Natural Science Foundation of China (Grants Nos. 62371199 and 62071186) and Guangdong Provincial Quantum Science Strategic Initiative (Grants Nos. GDZX2303007 and GDZX2305001).

Enhanced multiscale quantum approximate optimization algorithm in multibody combinatorial optimization problems

Lei-Lei Chen(陈蕾蕾)1, Ping Zou(邹平)1,†, and Ya-Fei Yu(於亚飞)1,2,‡   

  1. 1 Guangdong Provincial Key Laboratory of Nanophotonic Functional Materials and Devices, School of Optoelectronic Science and Engineering, South China Normal University, Guangzhou 510006, China;
    2 Quantum Science Center of Guangdong-Hong Kong-Macao Greater Bay Area, Shenzhen 518109, China
  • Received:2025-07-17 Revised:2025-11-26 Accepted:2025-12-09 Published:2026-07-21
  • Contact: Ping Zou, Ya-Fei Yu E-mail:zouping@m.scnu.edu.cn;yuyafei@m.scnu.edu.cn
  • Supported by:
    Project supported by the National Natural Science Foundation of China (Grants Nos. 62371199 and 62071186) and Guangdong Provincial Quantum Science Strategic Initiative (Grants Nos. GDZX2303007 and GDZX2305001).

PDF (PC)

0

赞

摘要： At present, the quantum approximate optimization algorithm (QAOA) faces scalability challenges in high-dimensional combinatorial optimization problems due to exponentially growing computational costs and reachability deficits for noisy intermediate-scale quantum (NISQ) devices. This study focuses on the multiscale quantum approximate optimization algorithm (MQAOA), which integrates renormalization group (RG) transformations with QAOA to address these limitations. Based on the connections between the variables in the problem to be solved, the weighted maximal matching method is employed to generate a variable partitioning strategy guiding the RG transformation. This approach not only extends the applicability of MQAOA to satisfiability (SAT) problems - including those with three-body and higher-order interactions in the problem Hamiltonian - but also eliminates the algorithm's sensitivity to problem density. Validations conducted on quantum simulators show that, after running two-round MQAOA, its capability is enhanced to identify optimal solutions with approximately 97% success probability as defined by the ground-state overlap for Max-2-SAT problems (78% success probability for Max-3-SAT problems). The results confirm the feasibility of MQAOA and establish it as a resource-efficient framework for complex combinatorial optimization problems, providing a pathway for NISQ-era deployment.

关键词: quantum algorithm, parameterized quantum circuit, renormalization group transformation, combinatorial optimization, Max-SAT problems

Abstract: At present, the quantum approximate optimization algorithm (QAOA) faces scalability challenges in high-dimensional combinatorial optimization problems due to exponentially growing computational costs and reachability deficits for noisy intermediate-scale quantum (NISQ) devices. This study focuses on the multiscale quantum approximate optimization algorithm (MQAOA), which integrates renormalization group (RG) transformations with QAOA to address these limitations. Based on the connections between the variables in the problem to be solved, the weighted maximal matching method is employed to generate a variable partitioning strategy guiding the RG transformation. This approach not only extends the applicability of MQAOA to satisfiability (SAT) problems - including those with three-body and higher-order interactions in the problem Hamiltonian - but also eliminates the algorithm's sensitivity to problem density. Validations conducted on quantum simulators show that, after running two-round MQAOA, its capability is enhanced to identify optimal solutions with approximately 97% success probability as defined by the ground-state overlap for Max-2-SAT problems (78% success probability for Max-3-SAT problems). The results confirm the feasibility of MQAOA and establish it as a resource-efficient framework for complex combinatorial optimization problems, providing a pathway for NISQ-era deployment.

Key words: quantum algorithm, parameterized quantum circuit, renormalization group transformation, combinatorial optimization, Max-SAT problems

中图分类号:  (Quantum algorithms, protocols, and simulations)

  • 03.67.Ac
03.67.Lx (Quantum computation architectures and implementations) 03.67.-a (Quantum information)