Binary optimization by momentum annealing
Authors:
- 10 July 2019
- journal article
- research article
- Published by American Physical Society (APS) in Physical Review E
- Vol. 100 (1) , 012111
Abstract
One of the vital roles of computing is to solve large-scale combinatorial optimization problems in a short time. In recent years, methods have been proposed that map optimization problems to ones of searching for the ground state of an Ising model by using a stochastic process. Simulated annealing (SA) is a representative algorithm. However, it is inherently difficult to perform a parallel search. Here we propose an algorithm called momentum annealing (MA), which, unlike SA, updates all spins of fully connected Ising models simultaneously and can be implemented on GPUs that are widely used for scientific computing. MA running in parallel on GPUs is 250 times faster than SA running on a modern CPU at solving problems involving 100 000 spin Ising models.Keywords
This publication has 40 references indexed in Scilit:
- Chaotic Boltzmann machinesScientific Reports, 2013
- Quantum annealing with manufactured spinsNature, 2011
- Spectral distributions of adjacency and Laplacian matrices of random graphsThe Annals of Applied Probability, 2010
- An information-theoretic framework for resolving community structure in complex networksProceedings of the National Academy of Sciences, 2007
- Worm algorithm for two-dimensional spin glassesPhysical Review E, 2005
- Uncovering the overlapping community structure of complex networks in nature and societyNature, 2005
- Experimental Implementation of an Adiabatic Quantum Optimization AlgorithmPhysical Review Letters, 2003
- Quantum annealing in the transverse Ising modelPhysical Review E, 1998
- Optimization by Simulated AnnealingScience, 1983
- On the computational complexity of Ising spin glass modelsJournal of Physics A: General Physics, 1982