|
|
|
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 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 |
|
|
|
|
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.
|
Received: 17 July 2025
Revised: 26 November 2025
Accepted manuscript online: 09 December 2025
|
|
PACS:
|
03.67.Ac
|
(Quantum algorithms, protocols, and simulations)
|
| |
03.67.Lx
|
(Quantum computation architectures and implementations)
|
| |
03.67.-a
|
(Quantum information)
|
|
| Fund: 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). |
Corresponding Authors:
Ping Zou, Ya-Fei Yu
E-mail: zouping@m.scnu.edu.cn;yuyafei@m.scnu.edu.cn
|
Cite this article:
Lei-Lei Chen(陈蕾蕾), Ping Zou(邹平), and Ya-Fei Yu(於亚飞) Enhanced multiscale quantum approximate optimization algorithm in multibody combinatorial optimization problems 2026 Chin. Phys. B 35 070305
|
[1] Bharti K, Cervera-Lierta A, Kyaw T H, Haug T, AlperinLea S, Anand A, Degroote M, Heimonen H, Kottmann J S, Menke T, Mok W K, Sim S, Kwek L C and Aspuru-Guzik A 2022 Rev. Mod. Phys. 94 015004
[2] Peruzzo A, McClean J, Shadbolt P, Yung M H, Zhou X Q, Love P J, Aspuru-Guzik A and O’Brien J L 2014 Nat. Commun. 5 4213
[3] Li Y and Benjamin S C 2017 Phys. Rev. X 7 021050
[4] Farhi E, Goldstone J and Gutmann S 2014 arXiv:1411.4028 [quant-ph]
[5] Blekos K, Brand D, Ceschini A, Chou C, Li R, Pandya K and Summer A 2024 Phys. Rep. 1068 1
[6] Papalitsas C, Andronikos T, Giannakis K, Theocharopoulou G and Fanarioti S 2019 Algorithms 12 224
[7] Bourreau E, Fleury G and Lacomme P 2025 arXiv:2505.01214 [quantph]
[8] Ding Q M, Huang YMand Yuan X 2024 Phys. Rev. Applied 21 034036
[9] Papalitsas C, Guan Y, Waghe S, Liakos A, Balatsos I and Pantazopoulos V 2025 arXiv:2503.04239 [cs.ET]
[10] Akshay V, Philathong H, MoraclesME S and Biamonte J D 2020 Phys. Rev. Lett. 124 090504
[11] Akshay V, Philathong H, Campos E, Rabinovich D, Zacharov I, Zhang X M and Biamonte J D 2022 Phys. Rev. A 106 042438
[12] Campos E, Rabinovich D, Akshay V and Biamonte J 2021 Phys. Rev. A 104 L030401
[13] McClean J R, Boixo S, Smelyanskiy V N, Babbush R and Neven H 2018 Nat. Commun. 9 4812
[14] Wang Z, Zheng P L,Wu B and Zhang Y 2023 Phys. Rev. Res. 5 023171
[15] Villalba-Diez J, González-Marcos A and Ordieres-Meré J B 2021 Sensors 22 244
[16] Herrman R, Lotshaw P C, Ostrowski J, Humble T S and Siopsis G 2022 Sci. Rep. 12 6781
[17] Chandarana P, Hegade N N, Paul K, Albarrán-Arriagada F, Solano E, del Campo A and Chen X 2021 Phys. Rev. Res. 4 013141
[18] Yu Y, Cao C, Dewey C,Wang X B, Shannon N and Joynt R 2022 Phys. Rev. Res. 4 023249
[19] Lee X, Saito Y, Cai D and Asai N 2021 IEEE International Conference on Quantum Computing and Engineering (QCE) pp. 10
[20] Fernández-Pendás M, Combarro E F, Vallecorsa S, Ranilla J and Rúa I F 2022 J. Comput. Appl. Math. 404 113388
[21] Shaydulin R, Hadfield S, Hogg T and Safro I 2021 Quantum Inf. Process 20 359
[22] Zou P 2025 Phys. Rev. A 111 012427
[23] Wilson K G 1975 Rev. Mod. Phys. 47 773
[24] Romero S V, Visuri A M, Cadavid A G, Simen A, Solano E and Hegade N N 2025 Commun. Phys. 8 348
[25] Moret B M E 1988 SIGACT News 19 51 |
| No Suggested Reading articles found! |
|
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|
Cited |
|
|
|
|
Altmetric
|
|
blogs
Facebook pages
Wikipedia page
Google+ users
|
Online attention
Altmetric calculates a score based on the online attention an article receives. Each coloured thread in the circle represents a different type of online attention. The number in the centre is the Altmetric score. Social media and mainstream news media are the main sources that calculate the score. Reference managers such as Mendeley are also tracked but do not contribute to the score. Older articles often score higher because they have had more time to get noticed. To account for this, Altmetric has included the context data for other articles of a similar age.
View more on Altmetrics
|
|
|
