Digital Annealing with Parallel Flip Dynamics
George Higgins Hutchinson, Tinish Bhattacharya, Arne Heittmann +1 more
Digital Annealing (DA) is an enhancement of the simulated annealing (SA) algorithm, achieved through a paralleltrial update scheme that boosts the flip acceptance rate, and a dynamic escape mechanism that helps overcome narrow energy barriers. In each parallel-trial iteration of the DA algorithm, every variable of the problem is independently proposed ("tried") for a flip. If any such candidate flips are accepted, a single candidate flip is then selected at random and applied. The primary contribution of this work is an improvement of the DA algorithm through parallel-flip dynamics, in which multiple candidate variable flips are applied within a single parallel-trial iteration. By utilizing computations of a parallel-trial scheme more efficiently, the enhanced algorithm exhibits faster convergence and a more favorable scaling exponent with respect to the number of parallel-trial iterations. This is demonstrated by benchmarking uniform random-SAT problems, where the algorithm outperforms other local search methods. To further motivate these results, we show that the proposed algorithm is well-suited for an efficient implementation on recently developed in-memory-computing parallel-gradient hardware, highlighting its potential for next-generation optimization solver accelerators.
Asilomar Conference on Signals, Systems and Computers (ACSSC)•Oct 26, 2025•0 citations