| CONDENSED MATTER: ELECTRONIC STRUCTURE, ELECTRICAL, MAGNETIC, AND OPTICAL PROPERTIES |
Prev
Next
|
|
|
Non-Markovian dynamical solver for efficient combinatorial optimization |
| Haijie Xu(徐海杰)1,2 and Zhe Yuan(袁喆)2,3,† |
1 Center for Advanced Quantum Studies and School of Physics and Astronomy, Beijing Normal University, Beijing 100875, China;
2 Interdisciplinary Center for Theoretical Physics and Information Sciences, Fudan University, Shanghai 200433, China;
3 State Key Laboratory of Surface Physics, Fudan University, Shanghai 200433, China |
|
|
|
|
Abstract We incorporate a non-Markovian feedback mechanism into the simulated bifurcation method for dynamical solvers addressing combinatorial optimization problems. By reinjecting a portion of dissipated kinetic energy into each spin in a history-dependent and trajectory-informed manner, the method effectively suppresses early freezing induced by inelastic boundaries and enhances the system's ability to explore complex energy landscapes. Numerical results on the maximum cut (MAX-CUT) instances of fully connected Sherrington-Kirkpatrick (SK) spin glass models, including the 2000-spin ${K}_{2000}$ benchmark, demonstrate that the non-Markovian algorithm significantly improves both solution quality and convergence speed. Tests on randomly generated SK instances with 100 to 1000 spins further indicate favorable scalability and substantial gains in computational efficiency. Moreover, the proposed scheme is well suited for massively parallel hardware implementations, such as field-programmable gate arrays, providing a practical and scalable approach for solving large-scale combinatorial optimization problems.
|
Received: 07 November 2025
Revised: 15 November 2025
Accepted manuscript online: 17 November 2025
|
|
PACS:
|
75.10.Nr
|
(Spin-glass and other random models)
|
| |
02.60.Pn
|
(Numerical optimization)
|
| |
05.10.-a
|
(Computational methods in statistical physics and nonlinear dynamics)
|
|
| Fund: This project was supported by the National Key Research and Development Program of China (Grant No. 2024YFA1408500), the National Natural Science Foundation of China (Grant Nos. 12174028 and 12574115), and the Open Fund of the State Key Laboratory of Spintronics Devices and Technologies (Grant No. SPL-2408). |
Corresponding Authors:
Zhe Yuan
E-mail: yuanz@fudan.edu.cn
|
Cite this article:
Haijie Xu(徐海杰) and Zhe Yuan(袁喆) Non-Markovian dynamical solver for efficient combinatorial optimization 2026 Chin. Phys. B 35 027503
|
[1] Mezard M, Parisi G and Virasoro M A 1987 Spin Glass Theory and Beyond (Singapore : Singapore World Scientific)
[2] Barahona F, Gröschel M, Jünger M and Reinelt G 1988 Oper. Res. 36 493
[3] Chang K C and Du D H C 1987 IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. 6 67
[4] Wang J, Jebara T and Chang S F 2013 J. Mach. Learn. Res. 14 771
[5] Collins T 2004 Graph Cut Matching in Computer Vision (Edinburgh: University of Edinburgh)
[6] Lucas A 2014 Front. Phys. 2 5
[7] Hopfield J J 1982 Proc. Natl. Acad. Sci. USA 79 2554
[8] Aarts E H L and Korst J 1989 Simulated Annealing and Boltzmann Machines (Chichester: Wiley)
[9] Bellitti M, Ricci-Tersenghi F and Scardicchio A 2021 Phys. Rev. Res. 3 043015
[10] Monasson R, Zecchina R, Kirkpatrick S, Selman B and Troyansky L 1999 Nature 400 133
[11] Albash T and Lidar D 2018 Rev. Mod. Phys. 90 015002
[12] Santoro G E, Martonak R, Tosatti E and Car R 2002 Science 295 2427
[13] Kirkpatrick S, Gelatt C D and Vecchi M P 1983 Science 220 671
[14] Goto H, Endo K, Suzuki M, Sakai Y, Kanao T, Hamakawa Y, Hidaka R, Yamasaki M and Tatsumura K 2021 Sci. Adv. 7 eabe7953
[15] Honjo T, Sonobe T, Inaba K, Inagaki T, Ikuta T, Yamada Y, Kazama T, Enbutsu K, Umeki T, Kasahara R, Kawarabayashi K and Takesue H 2021 Sci. Adv. 7 eabh0952
[16] Okawachi Y, Yu M, Jang J K, Ji X, Zhao Y, Kim B Y, Lipson M and Gaeta A L 2020 Nat. Commun. 11 4119
[17] Tatsumura K, Dixon A R and Goto H 2019 29th International Conference on Field Programmable Logic and Applications (FPL) 59
[18] Yamaoka M, Yoshimura C, Hayashi M, Okuyama T, Aoki H and Mizuno H 2016 IEEE J. Solid-State Circuits 51 303
[19] Mohseni N, McMahon P L and Byrnes T 2022 Nat. Rev. Phys. 4 363
[20] Inagaki T, Haribara Y, Igarashi K, Sonobe T, Tamate S, Honjo T, Marandi A, McMahon P L, Umeki T, Enbutsu K, Tadanaga O, Takenouchi H, Aihara K, Kawarabayashi K-I, Inoue K, Utsunomiya S and Takesue H 2016 Science 354 603
[21] Goto H 2016 Sci. Rep. 6 21686
[22] Goto H, Tatsumura K and Dixon A R 2019 Sci. Adv. 5 eaav2372
[23] Leleu T, Yamamoto Y, McMahon P L and Aihara K 2019 Phys. Rev. Lett. 122 040607
[24] Wang J, Ebler D, Wong K Y M, Hui D S W and Sun J 2023 Nat. Commun. 14 2510
[25] Kanao T and Goto H 2022 Commun. Phys. 5 212
[26] De Vega I and Alonso D 2017 Rev. Mod. Phys. 89 015001
[27] Breuer H P, Laine E M, Piilo J and Vacchini B 2016 Rev. Mod. Phys. 88 021002
[28] Mendonca T M, Celeri L C, Paternostro M and Soares-Pinto D O 2024 Phys. Rev. A 110 L040401
[29] Miao Y, Zhao L, Zhang Y and Yuan Z 2025 Sci. China Phys. Mech. Astron. 68 217511
[30] Zhao L, Zhang M, Zhang Y, Mi Y, Yuan Z and Xia K 2024 Phys. Rev. Appl. 21 064040
[31] Zhang Y, Zheng Q, Zhu X, Yuan Z and Xia K 2020 Sci. China Phys. Mech. Astron. 63 277531
[32] Qiao Y, Zhang Y and Yuan Z 2023 New J. Phys. 25 033031
[33] Sherrington D and Kirkpatrick S 1975 Phys. Rev. Lett. 35 1792
[34] Aramon M, Rosenberg G, Valiante E, Miyazawa T, Tamura H and Katzgraber H G 2019 Front. Phys. 7 48
[35] Leimkuhler B and Reich S 2004 Simulating Hamiltonian Dynamics (Cambridge : Cambridge University Press)
[36] Benda J and Herz A V M 2003 Neural Comput. 15 2523 |
| 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
|
|
|
