Parallel computing of Edwards--Anderson model

M. A. Padalko ; Yu. A. Shevchenko

Dalʹnevostočnyj matematičeskij žurnal, Tome 21 (2021) no. 2, pp. 234-246.

Résumé

An algorithm for parallel exact calculation of the ground state of a two-dimensional Edwards–Anderson model with free boundary conditions is given. The running time of the algorithm grows exponentially as the side of the lattice square increases. If one side of the lattice is fixed, the running time grows polynomially with increasing size of the other side. The method may find application in the theory of spin glasses, in the field of quantum computing. Performance data for the bimodal distribution is given. The distribution of spin bonds can be either bimodal or Gaussian. The method makes it possible to compute systems up to a size of 40x40.

Bibliographie

[1] J. L. van Hemmen, “Classical Spin-Glass Model”, Phys. Rev. Lett., 49:6 (1982), 409–412 | DOI | MR

[2] S. F. Edwards, P. W. Anderson, “Theory of spin glasses”, Phys. F : Metal Phys., 5 (1975), 965–74 | DOI

[3] R. Rammal, G. Toulouse, M. A. Virasoro, “Ultrametricity for physicists”, Rev. Mod. Phys., 58 (1986), 765 | DOI

[4] J. J. Hopfield, D. W. Tank, ““Neural” Computation of Decisions in Optimization Problems”, Biol. Cybern., 52 (1985), 141–152 | MR | Zbl

[5] R. McEliece, E. Posner, E. Rodemich, S. Venkatesh, “The capacity of the Hopfield associative memory”, IEEE Transactions on Information Theory, 33:4 (1987), 461–482 | DOI | MR | Zbl

[6] J. L. van Hemmen, “Spin-glass models of a neural network”, Phys. Rev. A, 34:4 (1986), 3435–3445 | DOI | MR

[7] G. S. Hartnett, E. Parker, E. Geist, “Replica symmetry breaking in bipartite spin glasses and neural networks”, Phys. Rev. E, 98:2 (2018), 022116 | DOI

[8] R. Salakhutdinov, G. Hinton, “Deep Boltzmann machines”, Phys. Rev. E, 5:2 (2009), 448–455

[9] C. Amoruso, A. K. Hartmann, M. A. Moore, “Determining energy barriers by iterated optimization: The two-dimensional Ising spin glass”, Phys. Rev. B, 73:18 (2006), 184405 | DOI

[10] B. Waclaw, Z. Burda, “Counting metastable states of Ising spin glasses on arbitrary graphs”, Phys. Rev. E, 77:4 (2008), 041114 | DOI | MR

[11] Z. Burda, A. Krzywicki, O. C. Martin, Z. Tabor, “From simple to complex networks: Inherent structures, barriers, and valleys in the context of spin glasses”, Phys. Rev. E, 73:3 (2006), 036110 | DOI

[12] S. Schnabel, W. Janke, “Distribution of metastable states of Ising spin glasses”, Phys. Rev. E, 97:17 (2018), 174204 | DOI

[13] M. W. Johnson , M. H. Amin, S. Gildert , T. Lanting , F. Hamze, N. Dickson, R. Harris, A. J. Berkley, J. Johansson, P. Bunyk, E. M. Chapple, C. Enderud, J. P. Hilton, K. Karimi, E. Ladizinsky, N. Ladizinsky, T. Oh , I. Perminov, C. Rich , M. C. Thom, E. Tolkacheva, C. J. Truncik, S. Uchaikin, J. Wang, B. Wilson, G. Rose, “Quantum annealing with manufactured spins”, Nature, 473:7346 (2011), 194–8 | DOI

[14] P. I. Bunyk, E. M. Hoskinson, M. W. Johnson, E. Tolkacheva, F. Altomare, A. J. Berkley, R. Harris, J. P. Hilton, T. Lanting, A. J. Przybysz, J. Whittaker, “Quantum annealing with manufactured spins”, IEEE Transactions on Applied Superconductivity, 24:4 (2014), 1–20 | DOI

[15] D. Perera, F. Hamze, J. Raymond, M. Weigel, H. Katzgraber, “Computational hardness of spin-glass problems with tile-planted solutions”, Phys. Rev. E, 101:2 (2020), 023316 | DOI

[16] I. Hen, “Equation Planting: A Tool for Benchmarking Ising Machines”, Phys. Rev. Applied, 12:1 (2019), 011003 | DOI

[17] D. Pierangeli, M. Rafayelyan, C. Conti, S. Gigan, “Scalable Spin-Glass Optical Simulator”, Phys. Rev. Applied, 15:3 (2019), 034087 | DOI

[18] T. Kadowaki, H. Nishimori, “Quantum annealing in the transverse Ising model”, Phys. Rev. E, 58:5 (2019), 5355–5363 | DOI

[19] G. E. Santoro, R. Martonak, E. Tosatti, R. Car, “Theory of Quantum Annealing of an Ising Spin Glass”, Phys. Rev. Applied, 295:5564 (2002), 2427–2430

[20] J. Machta, “Population annealing with weighted averages: A Monte Carlo method for rough free-energy landscapes”, Phys. Rev. E, 82:2 (2010), 026704 | DOI

[21] J. Houdayer, O. C. Martin, “Hierarchical approach for computing spin glass ground states”, Phys. Rev. E, 64:5 (2001), 056704 | DOI

[22] W. Wang, J. Machta, H. G. Katzgraber, “Population annealing: Theory and application in spin glasses”, Phys. Rev. E, 92:6 (2015), 063307 | DOI

[23] D. P. Morelo, A. Ramirez-Pastor, F. Rom, “Ground-state energy and entropy of the two-dimensional Edwards – Anderson”, Physica A: Statistical Mechanics and its Applications, 391 (2011)

[24] N. Hatano, “Evidence for the double degeneracy of the ground state in the three-dimensional $\pm$J spin glass”, Phys. Rev. B, 66 (2002) | DOI

[25] A. Galluccio, “New Algorithm for the Ising Problem: Partition Function for Finite Lattice Graphs”, Phys. Rev. Lett., 84:26 (2000), 5924–5927 | DOI

[26] A. K. Hartmann, H. Rieger, New Optimization Algorithms in Physics, Wiley-VCH, Berlin, 2004 | Zbl

[27] A. K.Hartmann, “Cluster-exact approximation of spin glass ground states”, Physica A, 224:480 (1996)

[28] A. K. Hartmann, “Ground States of Two-Dimensional Ising Spin Glasses: Fast Algorithms, Recent Developments and a Ferromagnet-Spin Glass Mixture”, J Stat Phys, 144:519 (2011) | Zbl

[29] G. Pardella, F. Liers, “Exact Ground States of Large Two-Dimensional Planar Ising Spin Glasses”, Physical Review. E, Statistical, nonlinear, and soft matter physics, 78 (2011), 056705 | DOI | MR

[30] B. Kaufman, “Crystal statistics. ii. partition function evaluated by spinor analysis”, Phys. Rev., 78 (1949), 1232–1243 | DOI

[31] M. Suzuki, “Transfer-matrix method and Monte Carlo simulation in quantum spin systems”, Phys. Rev. B., 31:5 (1985), 2957–2965 | DOI

[32] M. Suzuki, “Generalized Trotter's Formula and Systematic Approximants of Exponential Operators and Inner Derivations with Applications to Many-Body Problems. Commun”, Math. Phys., 51 (1976), 183–190 | DOI | Zbl