Highly parallel algorithm for the Ising ground state searching problem
arXiv:1907.05124
Abstract
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.
22 pages, 3 figures
References in corpus (8)
- A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
- A Coherent Ising Machine Based On Degenerate Optical Parametric Oscillators
- Optimized simulated annealing for Ising spin glasses
- Scaling of stiffness energy for 3d +/-J Ising spin glasses
- Comparing Monte Carlo methods for finding ground states of Ising spin glasses: population annealing, simulated annealing and parallel tempering
- Aspect-Ratio Scaling and The Stiffness Exponent for Ising Spin Glasses
- The stiffness exponent of two-dimensional Ising spin glasses for non-periodic boundary conditions using aspect-ratio scaling
- Emulating the coherent Ising machine with a mean-field algorithm