Highly parallel algorithm for the Ising ground state searching problem
This addresses the need for efficient and scalable solutions to combinatorial optimization problems in various scientific domains, though it appears incremental as it builds on existing methods.
The paper tackles the computationally hard problem of finding energy minima in the Ising model by introducing a highly parallel algorithm called MARS, which combines simulated annealing and mean-field annealing to achieve excellent performance on large systems and benchmark instances in terms of solution quality and computational time.
Finding an energy minimum in the Ising model is an exemplar objective, associated with many combinatorial optimization problems, that is computationally hard in general, but occurs in all areas of modern science. There are several numerical methods, providing solution for the medium size Ising spin systems. However, they are either computationally slow and badly parallelized, or do not give sufficiently good results for the large systems. In this paper, we present a highly parallel algorithm, called Mean-field Annealing from a Random State (MARS), incorporating the best features of the classical simulated annealing (SA) and Mean-Field Annealing (MFA) methods. The algorithm is based on the mean-field descent from a randomly selected configuration and temperature. Since a single run requires little computational effort, the effectiveness can be achieved by massive parallelisation. MARS shows excellent performance both on the large Ising spin systems and on the set of exemplary maximum cut benchmark instances in terms of both solution quality and computational time.