中国物理B ›› 2026, Vol. 35 ›› Issue (2): 27503-027503.doi: 10.1088/1674-1056/ae1fea

• • 上一篇    下一篇

Non-Markovian dynamical solver for efficient combinatorial optimization

Haijie Xu(徐海杰)1,2 and Zhe Yuan(袁喆)2,3,†   

  1. 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
  • 收稿日期:2025-11-07 修回日期:2025-11-15 接受日期:2025-11-17 出版日期:2026-01-21 发布日期:2026-01-21
  • 通讯作者: Zhe Yuan E-mail:yuanz@fudan.edu.cn
  • 基金资助:
    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).

Non-Markovian dynamical solver for efficient combinatorial optimization

Haijie Xu(徐海杰)1,2 and Zhe Yuan(袁喆)2,3,†   

  1. 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
  • Received:2025-11-07 Revised:2025-11-15 Accepted:2025-11-17 Online:2026-01-21 Published:2026-01-21
  • Contact: Zhe Yuan E-mail:yuanz@fudan.edu.cn
  • Supported by:
    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).

PDF (PC)

5

赞

摘要： 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.

关键词: non-Markovian dynamics, simulated bifurcation, combinatorial optimization, maximum cut (MAX-CUT) problem, spin glass

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.

Key words: non-Markovian dynamics, simulated bifurcation, combinatorial optimization, maximum cut (MAX-CUT) problem, spin glass

中图分类号:  (Spin-glass and other random models)

  • 75.10.Nr
02.60.Pn (Numerical optimization) 05.10.-a (Computational methods in statistical physics and nonlinear dynamics)