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:0807.3008 · Physical Review Letters

Inference from Matrix Products: A Heuristic Spin-Glass Algorithm

M. B. Hastings

Published Oct 17, 2008• 5 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1103/physrevlett.101.167206

Related papers

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

J. Poulter, John A. Blackman

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.

arXiv:cond-mat/0504423•Physical Review B•Sep 12, 2005•17 citations

Efficient algorithm for approximating one-dimensional ground states

Dorit Aharonov, Itai Arad, Sandy Irani

The density-matrix renormalization-group method is very effective at finding ground states of one-dimensional (1D) quantum systems in practice, but it is a heuristic method, and there is no known proof for when it works. In this article we describe an efficient classical algorithm which provably finds a good approximation of the ground state of 1D systems under well-defined conditions. More precisely, our algorithm finds a matrix product state of bond dimension $D$ whose energy approximates the minimal energy such states can achieve. The running time is exponential in $D$, and so the algorithm can be considered tractable even for $D$, which is logarithmic in the size of the chain. The result also implies trivially that the ground state of any local commuting Hamiltonian in 1D can be approximated efficiently; we improve this to an exact algorithm.

arXiv:0910.5055•Physical Review A•Jul 16, 2010•22 citations

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

Lawrence K. Saul, Mehran Kardar A

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.

Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topics•Nov 1, 1993•96 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

Evidence Against Spin-Glass Order in the Two-Dimensional Random-Bond Ising Model

I. Morgenstern, Kurt Binder

By recursive methods, numerically exact free energies are calculated for $L\ifmmode\times\else\texttimes\fi{}L$ Ising lattices with bonds of randomly chosen sign, with $6<~L<~18$. Ground states of these systems are identified, and the response to ordering fields is studied. By performing Monte Carlo simulations for precisely the same systems we are able to unambiguously distinguish nonequilibrium phenomena from equilibrium properties. The $L$ dependence of our results suggests that there is no nonzero spin-glass order parameter for $L\ensuremath{\rightarrow}\ensuremath{\infty}$.

Physical Review Letters•Nov 19, 1979•178 citations

Ground-state properties of the two-dimensional SWAP spin-glass ensemble

Alexander K. Hartmann, Leticia F. Cugliandolo, Marco Tarzia

We study the recently introduced SWAP ensemble for Ising spin-glasses, where the spins obtain varying lengths, with length scale $Δ\in [0, 2]$. The lengths can be exchanged in the spirit of the SWAP algorithm for glassy poly-disperse hard-sphere systems. Using an annealing schedule, if the annealing is slow enough, ground states of the corresponding Ising Hamiltonian, where the spin lengths are incorporated into the bonds, can be obtained with high probability. We prove this statement for two-dimensional systems with sizes of up to $L^2=1024^2$ spins by comparison with exact ground states obtained by using graph matching algorithms. In particular, we analyze the nature of the obtained realizations of the disorder by calculating exact zero-temperature domain-wall energies, from exact ground state calculations using periodic and anti-periodic boundary conditions. For medium or large values of $Δ$, e.g. $Δ=1$, the realizations turn ferromagnetic if the annealing is slow enough, i.e., they lose their zero-temperature spin-glass property. If $Δ$ is small, the realizations remain glassy, but the SWAP annealing does not easily find a true ground state.

arXiv:2610.05046•Oct 4, 2026•0 citations
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.
The density-matrix renormalization-group method is very effective at finding ground states of one-dimensional (1D) quantum systems in practice, but it is a heuristic method, and there is no known proof for when it works. In this article we describe an efficient classical algorithm which provably finds a good approximation of the ground state of 1D systems under well-defined conditions. More precisely, our algorithm finds a matrix product state of bond dimension DDD whose energy approximates the minimal energy such states can achieve. The running time is exponential in DDD, and so the algorithm can be considered tractable even for DDD, which is logarithmic in the size of the chain. The result also implies trivially that the ground state of any local commuting Hamiltonian in 1D can be approximated efficiently; we improve this to an exact algorithm.
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.
By recursive methods, numerically exact free energies are calculated for $L\ifmmode\times\else\texttimes\fi{}L$ Ising lattices with bonds of randomly chosen sign, with 6< L< 186<~L<~186< L< 18. Ground states of these systems are identified, and the response to ordering fields is studied. By performing Monte Carlo simulations for precisely the same systems we are able to unambiguously distinguish nonequilibrium phenomena from equilibrium properties. The LLL dependence of our results suggests that there is no nonzero spin-glass order parameter for $L\ensuremath{\rightarrow}\ensuremath{\infty}$.
We study the recently introduced SWAP ensemble for Ising spin-glasses, where the spins obtain varying lengths, with length scale Δ∈[0,2]Δ\in [0, 2]Δ∈[0,2]. The lengths can be exchanged in the spirit of the SWAP algorithm for glassy poly-disperse hard-sphere systems. Using an annealing schedule, if the annealing is slow enough, ground states of the corresponding Ising Hamiltonian, where the spin lengths are incorporated into the bonds, can be obtained with high probability. We prove this statement for two-dimensional systems with sizes of up to L2=10242L^2=1024^2L2=10242 spins by comparison with exact ground states obtained by using graph matching algorithms. In particular, we analyze the nature of the obtained realizations of the disorder by calculating exact zero-temperature domain-wall energies, from exact ground state calculations using periodic and anti-periodic boundary conditions. For medium or large values of ΔΔΔ, e.g. Δ=1Δ=1Δ=1, the realizations turn ferromagnetic if the annealing is slow enough, i.e., they lose their zero-temperature spin-glass property. If ΔΔΔ is small, the realizations remain glassy, but the SWAP annealing does not easily find a true ground state.