Дальневосточный математический журнал

К содержанию выпуска


Параллельные вычисления модели Эдвардса–Андерсона


М.А. Падалко, Ю.А. Шевченко

2021, выпуск 2, С. 234–246
DOI: https://doi.org/10.47910/FEMJ202120


Аннотация
Приводится алгоритм параллельного точного вычисления основного состояния двумерной модели Эдвардса–Андерсона со свободными граничными условиями. Время работы алгоритма экспоненциально растет с увеличением стороны квадрата решетки. При фиксации одной из сторон решетки время работы растет полиномиально с увеличением размера другой стороны. Метод может найти применение в теории спиновых стекол, в области вычислений на квантовых компьютерах. Приводятся данные производительности для бимодального распределения. Распределение связей спинов может быть как бимодальным, так и гауссовым. Метод дает возможность осуществлять расчет систем вплоть до размеров 40x40.

Ключевые слова: модель Эдвардса–Андерсона, спиновые стекла, основное состояние, высокопроизводительные вычисления, квантовые вычисления

Полный текст статьи (файл PDF)

Библиографический список

[1] J.L. van Hemmen, “Classical Spin-Glass Model”, Phys. Rev. Lett., 49:6 (1982), 409–412.
[2] S.F. Edwards, P.W. Anderson, “Theory of spin glasses”, Phys. F: Metal Phys., 5 (1975), 965–74.
[3] R. Rammal, G. Toulouse, M.A. Virasoro, “Ultrametricity for physicists”, Rev. Mod. Phys., 58 (1986), 765.
[4] J.J. Hop?eld, D.W. Tank, “Neural Computation of Decisions in Optimization Problems”, Biol. Cybern., 52 (1985), 141–152.
[5] R. McEliece, E. Posner, E. Rodemich, S. Venkatesh, “The capacity of the Hop?eld associative memory”, IEEE Transactions on Information Theory, 33:4 (1987), 461–482.
[6] J.L. van Hemmen, “Spin-glass models of a neural network”, Phys. Rev. A, 34:4 (1986), 3435–3445.
[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.
[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.
[10] B. Waclaw, Z. Burda, “Counting metastable states of Ising spin glasses on arbitrary graphs”, Phys. Rev. E, 77:4 (2008), 041114.
[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.
[12] S. Schnabel, W. Janke, “Distribution of metastable states of Ising spin glasses”, Phys. Rev. E, 97:17 (2018), 174204.
[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), 19–48.
[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.
[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.
[16] I. Hen, “Equation Planting: A Tool for Benchmarking Ising Machines”, Phys. Rev. Applied, 12:1 (2019), 011003.
[17] D. Pierangeli, M. Rafayelyan, C. Conti, S. Gigan, “Scalable Spin-Glass Optical Simulator”, Phys. Rev. Applied, 15:3 (2019), 034087.
[18] T. Kadowaki, H. Nishimori, “Quantum annealing in the transverse Ising model”, Phys. Rev. E, 58:5 (2019), 5355–5363.
[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.
[21] J. Houdayer, O.C. Martin, “Hierarchical approach for computing spin glass ground states”, Phys. Rev. E, 64:5 (2001), 056704.
[22] W. Wang, J. Machta, H.G. Katzgraber, “Population annealing: Theory and application in spin glasses”, Phys. Rev. E, 92:6 (2015), 063307.
[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 ±J spin glass”, Phys. Rev. B, 66 (2002).
[25] A. Galluccio, “New Algorithm for the Ising Problem: Partition Function for Finite Lattice Graphs”, Phys. Rev. Lett., 84:26 (2000), 5924–5927.
[26] A.K. Hartmann, H. Rieger, New Optimization Algorithms in Physics, Wiley-VCH, Berlin, 2004.
[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).
[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.
[30] B. Kaufman, “Crystal statistics. ii. partition function evaluated by spinor analysis”, Phys. Rev., 78 (1949), 1232–1243.
[31] M. Suzuki, “Transfer-matrix method and Monte Carlo simulation in quantum spin systems”, Phys. Rev. B., 31:5 (1985), 2957–2965.
[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.

К содержанию выпуска