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•26 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•94 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

A comparison between D-wave and a classical approximation algorithm and a heuristic for computing the ground state of an Ising spin glass

Ran Yacoby, Nathan Schaar, Leon Kellerhals +3 more

Finding the ground state of an Ising-spin glass on general graphs belongs to the class of NP-hard problems, widely believed to have no efficient polynomial-time algorithms for solving them. An approach developed in computer science for dealing with such problems is to devise approximation algorithms that run in polynomial time, and provide solutions with provable guarantees on their quality in terms of the optimal unknown solution. Recently, several algorithms for the Ising-spin glass problem on a graph that provide different approximation guarantees were introduced albeit without implementation. Also recently, D-wave company constructed a physical realization of an adiabatic quantum computer, and enabled researchers to access it. D-wave is particularly suited for computing an approximation for the ground state of an Ising spin glass on its chimera graph -- a graph with bounded degree. In this work, we compare the performance of a recently developed approximation algorithm for solving the Ising spin glass problem on graphs of bounded degree against the D-wave computer. We also compared a heuristic tailored specifically to handle the fixed D-wave chimera graph. D-wave computer was able to find better approximations to all the random instances we studied. Furthermore the convergence times of D-wave were also significantly better. These results indicate the merit of D-wave computer under certain specific instances. More broadly, our method is relevant to other performance comparison studies. We suggest that it is important to compare the performance of quantum computers not only against exact classical algorithms with exponential run-time scaling, but also to approximation algorithms with polynomial run-time scaling and a provable guarantee on performance.

arXiv:2105.00537•May 2, 2021•3 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}$.
Finding the ground state of an Ising-spin glass on general graphs belongs to the class of NP-hard problems, widely believed to have no efficient polynomial-time algorithms for solving them. An approach developed in computer science for dealing with such problems is to devise approximation algorithms that run in polynomial time, and provide solutions with provable guarantees on their quality in terms of the optimal unknown solution. Recently, several algorithms for the Ising-spin glass problem on a graph that provide different approximation guarantees were introduced albeit without implementation. Also recently, D-wave company constructed a physical realization of an adiabatic quantum computer, and enabled researchers to access it. D-wave is particularly suited for computing an approximation for the ground state of an Ising spin glass on its chimera graph -- a graph with bounded degree. In this work, we compare the performance of a recently developed approximation algorithm for solving the Ising spin glass problem on graphs of bounded degree against the D-wave computer. We also compared a heuristic tailored specifically to handle the fixed D-wave chimera graph. D-wave computer was able to find better approximations to all the random instances we studied. Furthermore the convergence times of D-wave were also significantly better. These results indicate the merit of D-wave computer under certain specific instances. More broadly, our method is relevant to other performance comparison studies. We suggest that it is important to compare the performance of quantum computers not only against exact classical algorithms with exponential run-time scaling, but also to approximation algorithms with polynomial run-time scaling and a provable guarantee on performance.