Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topics

Exact integer algorithm for the two-dimensional ±JIsing spin glass

Lawrence K. Saul, Mehran Kardar A

Published Nov 1, 1993• 96 citations
Publisher

Abstract

We describe an exact integer algorithm to compute the partition function of a two-dimensional \ifmmode\pm\else\textpm\fi{}J Ising spin glass. Given a set of quenched random bonds, the algorithm returns the density of states as a function of energy. The computation time is polynomial in the lattice size. We investigate defects, low-lying excitations, and zeros of the partition function in the complex plane. We also discuss the potential to examine other types of quenched randomness.

DOI
10.1103/physreve.48.r3221

Related papers

Numerically Exact Polynomial Time Algorithm for the Ising Spin Glass in Any Dimension: Evidence for P=NP on a Quantum Computer

Daniel A. Lidar, Ofer Biham

We present a polynomial time algorithm for the construction of the Gibbs distribution of configurations in the Ising model, on a quantum computer. The algorithm is designed so that each run provides one configuration with exactly the correct quantum probability, namely, the corresponding thermodynamic weight. The partition function is thus approximated in the most efficient way. The algorithm does not suffer from critical slowing down, unlike its classical counterparts. Moreover, the algorithm can be applied in any dimension, to any of the frustrated Ising models, diluted Ising models, and spin glasses. In particular, we show that under certain plausible assumptions concerning the scaling of the number of low-lying metastable states, the ground state of any dimensional short-range spin glass can be found in poly(N_T) steps, N_T being the number of spins (N) in the system plus the number of bonds between them (N_B). Since the problem of finding the ground state of a spin glass in 3D is known to be NP-complete, we thus provide evidence that possibly P=NP on a quantum computer.

•Nov 21, 1996•0 citations

Inference from Matrix Products: A Heuristic Spin-Glass Algorithm

M. B. Hastings

We present an algorithm for finding ground states of two-dimensional spin-glass systems based on ideas from matrix product states in quantum information theory. The algorithm works directly at zero temperature and defines an approximation to the energy whose accuracy depends on a parameter k. We test the algorithm against exact methods on random field and random bond Ising models, and we find that accurate results require a k which scales roughly polynomially with the system size. The algorithm also performs well when tested on small systems with arbitrary interactions, where no fast, exact algorithms exist. The time required is significantly less than Monte Carlo schemes.

arXiv:0807.3008•Physical Review Letters•Oct 17, 2008•5 citations

Evidence against a spin-glass transition in three dimensions

Gyan V Bhanot, K.J.M. Moriarty, Román Salvador

We study the Ising spin-glass model in two and three dimensions on small lattices by exactly computing the partition function for a large number of bond configurations. An analysis of the zeros of these partition functions suggests that there is no nonanalyticity in the free energy of the spin glass in either two or three dimensions.

Physical review. B, Condensed matter•Jan 1, 1989•1 citation

Finite-size scaling analysis of exact ground states for ± J spin glass models in two dimensions

Naoki Kawashima, Heiko Rieger

With the help of exact ground states obtained by a polynomial algorithm we compute the domain wall energy Δ at zero temperature for the bond-random and the site-random Ising spin glass model in two dimensions. We find that in both models the stability of the ferromagnetic and the spin glass order ceases to exist at a unique concentration p c for the ferromagnetic bonds. In the vicinity of this critical point, the size and concentration dependence of the first and second moment of the domain wall energy are, for both models, described by a common finite-size scaling form. Moreover, below this concentration the stiffness exponent turns out to be slightly negative, θ S = − 0.056(6), indicating the absence of any intermediate spin glass phase at non-zero temperature.

arXiv:cond-mat/9612116•Europhysics Letters (EPL)•Jul 1, 1997•81 citations

Critical Thermodynamics of the Two-Dimensional ±J Ising Spin Glass

Jovanka Lukic, Anna Galluccio, Enzo Marinari +2 more

We compute the exact partition function of 2d Ising spin glasses with binary couplings. In these systems, the ground state is highly degenerate and is separated from the first excited state by a gap of size 4J. Nevertheless, we find that the low temperature specific heat density scales as exp(-2J/T), corresponding to an "effective" gap of size 2J; in addition, an associated crossover length scale grows as exp(J/T). We justify these scalings via the degeneracy of the low lying excitations and by the way low energy domain walls proliferate in this model.

arXiv:cond-mat/0309238•Physical Review Letters•Mar 18, 2004•43 citations

Exact ground-state energy of the Ising spin glass on strips

Tadashi Kadowaki, Yoshihiko Nonomura, 西森 秀稔 +1 more

We propose a new method for exact analytical calculation of the ground-state energy of the Ising spin glass on strips. An outstanding advantage of this method over the numerical transfer matrix technique is that the energy is obtained for complex values of the probability describing quenched randomness. We study the $\pm J$ and the site-random models using this method for strips of various sizes up to $5\times\infty$. The ground-state energy of these models is found to have singular points in the complex-probability plane, reminiscent of Lee-Yang zeros in the complex-field plane for the Ising ferromagnet. The $\pm J$ Ising model has a series of singularities which may approach a limiting point around $p \sim 0.9$ on the real axis in the limit of infinite width.

•Feb 22, 2019•4 citations
We describe an exact integer algorithm to compute the partition function of a two-dimensional \ifmmode\pm\else\textpm\fi{}J Ising spin glass. Given a set of quenched random bonds, the algorithm returns the density of states as a function of energy. The computation time is polynomial in the lattice size. We investigate defects, low-lying excitations, and zeros of the partition function in the complex plane. We also discuss the potential to examine other types of quenched randomness.
We present a polynomial time algorithm for the construction of the Gibbs distribution of configurations in the Ising model, on a quantum computer. The algorithm is designed so that each run provides one configuration with exactly the correct quantum probability, namely, the corresponding thermodynamic weight. The partition function is thus approximated in the most efficient way. The algorithm does not suffer from critical slowing down, unlike its classical counterparts. Moreover, the algorithm can be applied in any dimension, to any of the frustrated Ising models, diluted Ising models, and spin glasses. In particular, we show that under certain plausible assumptions concerning the scaling of the number of low-lying metastable states, the ground state of any dimensional short-range spin glass can be found in poly(N_T) steps, N_T being the number of spins (N) in the system plus the number of bonds between them (N_B). Since the problem of finding the ground state of a spin glass in 3D is known to be NP-complete, we thus provide evidence that possibly P=NP on a quantum computer.
We present an algorithm for finding ground states of two-dimensional spin-glass systems based on ideas from matrix product states in quantum information theory. The algorithm works directly at zero temperature and defines an approximation to the energy whose accuracy depends on a parameter k. We test the algorithm against exact methods on random field and random bond Ising models, and we find that accurate results require a k which scales roughly polynomially with the system size. The algorithm also performs well when tested on small systems with arbitrary interactions, where no fast, exact algorithms exist. The time required is significantly less than Monte Carlo schemes.
With the help of exact ground states obtained by a polynomial algorithm we compute the domain wall energy Δ at zero temperature for the bond-random and the site-random Ising spin glass model in two dimensions. We find that in both models the stability of the ferromagnetic and the spin glass order ceases to exist at a unique concentration p c for the ferromagnetic bonds. In the vicinity of this critical point, the size and concentration dependence of the first and second moment of the domain wall energy are, for both models, described by a common finite-size scaling form. Moreover, below this concentration the stiffness exponent turns out to be slightly negative, θ S = − 0.056(6), indicating the absence of any intermediate spin glass phase at non-zero temperature.
We compute the exact partition function of 2d Ising spin glasses with binary couplings. In these systems, the ground state is highly degenerate and is separated from the first excited state by a gap of size 4J. Nevertheless, we find that the low temperature specific heat density scales as exp(-2J/T), corresponding to an "effective" gap of size 2J; in addition, an associated crossover length scale grows as exp(J/T). We justify these scalings via the degeneracy of the low lying excitations and by the way low energy domain walls proliferate in this model.
We propose a new method for exact analytical calculation of the ground-state energy of the Ising spin glass on strips. An outstanding advantage of this method over the numerical transfer matrix technique is that the energy is obtained for complex values of the probability describing quenched randomness. We study the ±J\pm J±J and the site-random models using this method for strips of various sizes up to 5×∞5\times\infty5×∞. The ground-state energy of these models is found to have singular points in the complex-probability plane, reminiscent of Lee-Yang zeros in the complex-field plane for the Ising ferromagnet. The ±J\pm J±J Ising model has a series of singularities which may approach a limiting point around p∼0.9p \sim 0.9p∼0.9 on the real axis in the limit of infinite width.