2014

Optimized simulated annealing for Ising spin glasses

Isakov, S. V., Zintchenko, I. N., Rønnow, T. F. et al.

Understand

We present several efficient implementations of the simulated annealing algorithm for Ising spin glasses on sparse graphs.

In particular, we provide a generic code for any choice of couplings, an optimized code for bipartite graphs, and highly optimized implementations using multi-spin coding for graphs with small maximum degree and discrete couplings with a finite range.
The latter codes achieve up to 50 spin flips per nanosecond on modern Intel CPUs.
We also compare the performance of the codes to that of the special purpose D-Wave devices built for solving such Ising spin glass problems.

Built on

F. Barahona, On the computational complexity of Ising spin glass models , Journal of Physics A: Mathematical and General 15 (10) (1982) 3241. URL http://stacks.iop.org/0305-4470/15/i=10/a=028
1982
Earlier work this paper cites.
doi:10.1126/science.220.4598.671
S. Kirkpatrick, C. D. Gelatt, M. P. Vecchi, Optimization by simulated annealing , Science 220 (4598) (1983) 671–680 · 1983
Earlier work this paper cites.
doi:10.1103/PhysRevLett.57.2607
R. H. Swendsen, J.-S. Wang, Replica monte carlo simulation of spin-glasses , Phys. Rev. Lett. 57 (1986) 2607–2609 · 1986
Earlier work this paper cites.
doi:10.1007/BF01011918
G. Bhanot, D. Duke, R. Salvador, A fast algorithm for the cyber 205 to simulate the 3d ising model , Journal of Statistical Physics 44 (5-6) (1986) 985–1002 · 1986
Earlier work this paper cites.
L. Pierre, T. Giamarchi, H. J. Schulz, A new random-number generator for multispin monte carlo algorithms , Journal of Statistical Physics 48 (1987) 135–149, 10.1007/BF01010404. URL http://dx.doi.org/10.1007/BF01010404
1987
Earlier work this paper cites.
N. Ito, Y. Kanada, Monte carlo simulation of the ising model and random number generation on the vector processor (1990) 753–763 doi:10.1109/SUPERC.1990.130097
1990
Earlier work this paper cites.

Similar

doi:10.1016/0010-4655(90)90186-5
H.-O. Heuer, A fast vectorized fortran 77 program for the monte carlo simulation of the three-dimensional ising system , Computer Physics Communications 59 (2) (1990) 387 – 398 · 1990
Cited alongside, same era.
C. J. Geyer, Markov chain monte carlo maximum likelihood, in: E. M. Keramidas (Ed.), Computing Science and Statistics: 23rd Symposium on the Interface, Interface Foundation, Fairfax Station, 1991, 1991, pp. 156–163
1991
Cited alongside, same era.
doi:10.1007/BF01053609
H. Rieger, Fast vectorized algorithm for the monte carlo simulation of the random field ising model , Journal of Statistical Physics 70 (3-4) (1993) 1063–1073 · 1993
Cited alongside, same era.
T. Fischer, H. Lüthi, W. Petersen, A New Optimization Technique for Artificial Neural Networks Used in Prediction of Force Constants of Large Molecules , IPS research report, IPS, Interdisciplinary Project Center for Supercomputing, ETH-Zentrum, 1994. URL http://books.google.ch/books?id=d-onPwAACAAJ
1994
Cited alongside, same era.
doi:10.1142/S0129183103004498
J. J. Moreno, H. G. Katzgraber, A. K. Hartmann, Finding low-temperature states with parallel tempering, simulated annealing and simple monte carlo , International Journal of Modern Physics C 14 (03) (2003) 285–302 · 2003
Cited alongside, same era.
arXiv:arXiv:0804.4457
Original
H. Neven, G. Rose, W. G. Macready, Image recognition with an adiabatic quantum computer i. mapping to quadratic unconstrained binary optimization (2008) · 2008
Cited alongside, same era.

Then

doi:10.1016/j.physa.2009.03.036
F. Romá, S. Risau-Gusman, A. Ramirez-Pastor, F. Nieto, E. Vogel, The ground state energy of the edwards–anderson spin glass model with a parallel tempering monte carlo algorithm , Physica A: Statistical Mechanics and its Applications 388 (14) (2009) 2821 – 2838 · 2009
Later among the works it cites.
doi:10.1016/j.cpc.2010.05.005
B. Block, P. Virnau, T. Preis, Multi-gpu accelerated multi-spin monte carlo simulations of the 2d ising model, Computer Physics Communications 181 (9) (2010) 1549 – 1556 · 2010
Later among the works it cites.
arXiv:arXiv:1205.1148
Original
V. S. Denchev, N. Ding, S. V. N. Vishwanathan, H. Neven, Robust classification with adiabatic quantum optimization (2012) · 2012
Later among the works it cites.
C. C. McGeoch, C. Wang, Experimental evaluation of an adiabatic quantum system for combinatorial optimization, in: Proceedings of the 2013 ACM Conference on Computing Frontiers, 2013
2013
Later among the works it cites.
doi:10.1126/science.1252319
Original
T. F. Rønnow, Z. Wang, J. Job, S. Boixo, S. V. Isakov, D. Wecker, J. M. Martinis, D. A. Lidar, M. Troyer, Defining and detecting quantum speedup , Science 345 (6195) (2014) 420–424 · 2014
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…