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

arXiv:cond-mat/0504423 · Physical Review B

Exact algorithm for spin-correlation functions of the two-dimensional ±J Ising spin glass in the ground state

J. Poulter, John A. Blackman

Published Sep 12, 2005• 17 citations
arXivHTMLPDF

Abstract

We introduce an exact algorithm for the computation of spin correlation functions for the two dimensional $\ifmmode\pm\else\textpm\fi{}J$ Ising spin glass in the ground state. Unlike with the transfer matrix method, there is no particular restriction on the shape of the lattice sample, and unlike Monte Carlo based methods it avoids extrapolation from finite temperatures. The computational requirements depend only on the number and distribution of frustrated plaquettes.

DOI
10.1103/physrevb.72.104422

Related papers

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

’’Exact’’ calculations for finite Ising spin glass lattices (invited)

I. Morgenstern, Kurt Binder

By a recursive method numerically exact free energies and correlation functions are calculated for finite two- and three-dimensional Ising lattices with bonds chosen randomly either ±J or from a gaussian distribution. While (dynamic) Monte Carlo simulations of precisely the same systems show the onset of Edwards-Anderson ordering at rather sharply defined nonzero freezing temperature Tf, the exact static calculations imply that there is no static order parameter qEA = [<Si≳2T]av at nonzero temperature. The correlation length, which would become infinite when qEA would start to become nonzero, is found at Tf to be of the order of a few lattice spacings only. As a result, the freezing-in of these models is identified as a dynamic phenomenon, and not a phase transition associated with static Edwards-Anderson order. The specific heat of the gaussian spin glass is found to vary nearly linear with temperature. On the other hand, in two-dimensional Ising systems with random fields a nonzero (Mattis-like) spin glass order is found.

Journal of Applied Physics•Mar 1, 1981•13 citations

Numerically exact correlations and sampling in the two-dimensional Ising spin glass

Creighton K. Thomas, A. Alan Middleton

A powerful existing technique for evaluating statistical mechanical quantities in two-dimensional Ising models is based on constructing a matrix representing the nearest-neighbor spin couplings and then evaluating the Pfaffian of the matrix. Utilizing this technique and other more recent developments in evaluating elements of inverse matrices and exact sampling, a method and computer code for studying two-dimensional Ising models is developed. The formulation of this method is convenient and fast for computing the partition function and spin correlations. It is also useful for exact sampling, where configurations are directly generated with probability given by the Boltzmann distribution. These methods apply to Ising model samples with arbitrary nearest-neighbor couplings and can also be applied to general dimer models. Example results of computations are described, including comparisons with analytic results for the ferromagnetic Ising model, and timing information is provided.

arXiv:1301.1252•Physical Review E•Apr 5, 2013•11 citations

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

GROUND STATES FOR LARGE SAMPLES OF TWO-DIMENSIONAL ISING SPIN GLASSES

Richard G. Palmer, Joan Adler

We have developed a combinatoric matching method to find the exact groundstate energy for the 2-D Ising spin glass with the ± J distribution and equal numbers of positive and negative bonds. For the largest size (1800×1800 plaquettes of spins), we averaged results from 278 samples and for the smaller ones up to 374, 375 samples. We also studied the behavior of the distributions of computer time (CPU) and memory as functions of sample size. We present finite size scaling leading to a groundstate energy estimate of E∞=-1.40193±2 for the infinite system. We found that the memory scales as the square of sample length and that for a given size, the CPU time appears to have a skewed and high-tailed distribution.

International Journal of Modern Physics C•Jun 1, 1999•35 citations

Ground-state magnetization of Ising spin glasses

Francisco Barahona

We study the magnetization of the ground states of Ising spin glasses as a function of the magnetic field. The grids are two-dimensional with Gaussian bond distribution. Finding a ground state in this case is a difficult combinatorial problem. We present a method that guarantees finding a true ground state. Although it is unlikely that one can have an algorithm with a polynomial bound for the running time, in all cases we tried, our method found a solution in a reasonable amount of time. We used this to obtain estimations of the critical exponents.

Physical review. B, Condensed matter•May 1, 1994•20 citations
We introduce an exact algorithm for the computation of spin correlation functions for the two dimensional \ifmmode±\else\textpm\fiJ\ifmmode\pm\else\textpm\fi{}J\ifmmode±\else\textpm\fiJ Ising spin glass in the ground state. Unlike with the transfer matrix method, there is no particular restriction on the shape of the lattice sample, and unlike Monte Carlo based methods it avoids extrapolation from finite temperatures. The computational requirements depend only on the number and distribution of frustrated plaquettes.
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.
By a recursive method numerically exact free energies and correlation functions are calculated for finite two- and three-dimensional Ising lattices with bonds chosen randomly either ±J or from a gaussian distribution. While (dynamic) Monte Carlo simulations of precisely the same systems show the onset of Edwards-Anderson ordering at rather sharply defined nonzero freezing temperature Tf, the exact static calculations imply that there is no static order parameter qEA = [<Si≳2T]av at nonzero temperature. The correlation length, which would become infinite when qEA would start to become nonzero, is found at Tf to be of the order of a few lattice spacings only. As a result, the freezing-in of these models is identified as a dynamic phenomenon, and not a phase transition associated with static Edwards-Anderson order. The specific heat of the gaussian spin glass is found to vary nearly linear with temperature. On the other hand, in two-dimensional Ising systems with random fields a nonzero (Mattis-like) spin glass order is found.
A powerful existing technique for evaluating statistical mechanical quantities in two-dimensional Ising models is based on constructing a matrix representing the nearest-neighbor spin couplings and then evaluating the Pfaffian of the matrix. Utilizing this technique and other more recent developments in evaluating elements of inverse matrices and exact sampling, a method and computer code for studying two-dimensional Ising models is developed. The formulation of this method is convenient and fast for computing the partition function and spin correlations. It is also useful for exact sampling, where configurations are directly generated with probability given by the Boltzmann distribution. These methods apply to Ising model samples with arbitrary nearest-neighbor couplings and can also be applied to general dimer models. Example results of computations are described, including comparisons with analytic results for the ferromagnetic Ising model, and timing information is provided.
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 have developed a combinatoric matching method to find the exact groundstate energy for the 2-D Ising spin glass with the ± J distribution and equal numbers of positive and negative bonds. For the largest size (1800×1800 plaquettes of spins), we averaged results from 278 samples and for the smaller ones up to 374, 375 samples. We also studied the behavior of the distributions of computer time (CPU) and memory as functions of sample size. We present finite size scaling leading to a groundstate energy estimate of E∞=-1.40193±2 for the infinite system. We found that the memory scales as the square of sample length and that for a given size, the CPU time appears to have a skewed and high-tailed distribution.
We study the magnetization of the ground states of Ising spin glasses as a function of the magnetic field. The grids are two-dimensional with Gaussian bond distribution. Finding a ground state in this case is a difficult combinatorial problem. We present a method that guarantees finding a true ground state. Although it is unlikely that one can have an algorithm with a polynomial bound for the running time, in all cases we tried, our method found a solution in a reasonable amount of time. We used this to obtain estimations of the critical exponents.