Non-Markovian dynamical solver for efficient combinatorial optimization

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₂₀₀₀ 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.