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

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

Published Nov 21, 1996• 0 citations
OpenAlex

Abstract

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.

Related papers

Simulating Ising spin glasses on a quantum computer

Daniel A. Lidar, Ofer Biham

A linear-time algorithm is presented 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 a quantum probability equal to the corresponding thermodynamic weight. The partition function is thus approximated efficiently. The algorithm neither suffers from critical slowing down nor gets stuck in local minima. The algorithm can be applied in any dimension, to a class of spin-glass Ising models with a finite portion of frustrated plaquettes, diluted Ising models, and models with a magnetic field.

arXiv:quant-ph/9611038•Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topics•Sep 1, 1997•120 citations

Computational complexity of three-dimensional Ising spin glass: Lessons from D-wave annealer

Hao Zhang, Alex Kamenev

Finding an exact ground state of a three-dimensional (3D) Ising spin glass is proven to be an NP-hard problem (i.e., at least as hard as any problem in the nondeterministic polynomial-time (NP) class). Given validity of the exponential time hypothesis, its computational complexity was proven to be no less than 2 N 2 / 3 , where N is the total number of spins. Here, we report results of extensive experimentation with D-Wave 3D annealer with N ≤ 5627 . We found exact ground states (in a probabilistic sense) for typical realizations of 3D spin glasses with the efficiency, which scales as 2 N / β with β ≈ 10 3 . Based on statistical analysis of low-energy states, we argue that with an improvement of annealing protocols and device noise reduction, β can be increased even further. This suggests that, for N < β 3 , annealing devices provide most efficient way to find an exact ground state.

arXiv:2501.01107•Physical Review Research•Jul 14, 2025•5 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

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•2 citations

Classical approximation schemes for the ground-state energy of quantum and classical Ising spin Hamiltonians on planar graphs

Nikhil Bansal, Sergey B. Bravyi, Barbara M. Terhal

We describe a classical approximation algorithm for evaluating the ground state energy of the classical Ising Hamiltonian with linear terms on an arbitrary planar graph. The running time of the algorithm grows linearly with the number of spins and exponentially with $1/\epsilon$, where $\epsilon$ is the worst-case relative error. This result contrasts the well known fact that exact computation of the ground state energy for the two-dimensional Ising spin glass model is NP-hard. We also present a classical approximation algorithm for the quantum Local Hamiltonian Problem or Quantum Ising Spin Glass problem on a planar graph {\em with bounded degree} which is known to be a QMA-complete problem. Using a different technique we find a classical approximation algorithm for the quantum Ising spin glass problem on the simplest planar graph with unbounded degree, the star graph.

arXiv:0705.1115•Quantum Information and Computation•Jul 1, 2009•36 citations

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
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.
A linear-time algorithm is presented 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 a quantum probability equal to the corresponding thermodynamic weight. The partition function is thus approximated efficiently. The algorithm neither suffers from critical slowing down nor gets stuck in local minima. The algorithm can be applied in any dimension, to a class of spin-glass Ising models with a finite portion of frustrated plaquettes, diluted Ising models, and models with a magnetic field.
Finding an exact ground state of a three-dimensional (3D) Ising spin glass is proven to be an NP-hard problem (i.e., at least as hard as any problem in the nondeterministic polynomial-time (NP) class). Given validity of the exponential time hypothesis, its computational complexity was proven to be no less than 2 N 2 / 3 , where N is the total number of spins. Here, we report results of extensive experimentation with D-Wave 3D annealer with N ≤ 5627 . We found exact ground states (in a probabilistic sense) for typical realizations of 3D spin glasses with the efficiency, which scales as 2 N / β with β ≈ 10 3 . Based on statistical analysis of low-energy states, we argue that with an improvement of annealing protocols and device noise reduction, β can be increased even further. This suggests that, for N < β 3 , annealing devices provide most efficient way to find an exact ground state.
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.
We describe a classical approximation algorithm for evaluating the ground state energy of the classical Ising Hamiltonian with linear terms on an arbitrary planar graph. The running time of the algorithm grows linearly with the number of spins and exponentially with 1/ϵ1/\epsilon1/ϵ, where ϵ\epsilonϵ is the worst-case relative error. This result contrasts the well known fact that exact computation of the ground state energy for the two-dimensional Ising spin glass model is NP-hard. We also present a classical approximation algorithm for the quantum Local Hamiltonian Problem or Quantum Ising Spin Glass problem on a planar graph {\em with bounded degree} which is known to be a QMA-complete problem. Using a different technique we find a classical approximation algorithm for the quantum Ising spin glass problem on the simplest planar graph with unbounded degree, the star graph.