2019/07/11 by A. Yavorsky, Yavorsky, A., L. A. Markovich +5 · 1 citation
Computer Science · Mathematics · Physics and Astronomy · #Complex Network Analysis Techniques #FOS: Computer and information sciences #FOS: Physical sciences #Machine Learning (stat.ML) #Markov Chains and Monte Carlo Methods #Quantum Computing Algorithms and Architecture #Quantum Physics (quant-ph) #Statistical Mechanics (cond-mat.stat-mech)
paper · pdf · doi:10.48550/arxiv.1907.05124
openalex publication_date 2019/07/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.