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:0705.1115 · Quantum Information and Computation

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

Published Jul 1, 2009• 36 citations
arXivHTMLPDF

Abstract

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.

DOI
10.26421/qic9.7-8-12

Related papers

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

Comparison between a quantum annealer and a classical approximation algorithm 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 to solve them. An approach developed in computer science for dealing with such problems is to devise approximation algorithms; these are algorithms, whose run time scales polynomially with the input size, that 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 bounded degree graph that provide different approximation guarantees were introduced. D-Wave, a Canadian-based company, has constructed a physical realization of a quantum annealer and has enabled researchers and practitioners to access it via their cloud service. D-Wave is particularly suited for computing an approximation for the ground state of an Ising spin glass on its Chimera and Pegasus graphs-both with a bounded degree. To assess the quality of D-Wave's solution, it is natural to compare it to classical approximation algorithms specifically designed to solve the same problem. In this work, we compare the performance of a recently developed approximation algorithm to solve the Ising spin-glass problem on graphs of bounded degree against the performance of the D-Wave computer. We also compared the performance of D-Wave's computer in the Chimera architecture against the performance of a heuristic tailored specifically to handle the Chimera graph. We found that the D-Wave computer was able to find better approximations for all the random instances of the problem we studied-Gaussian weights, uniform weights, and discrete binary weights. Furthermore, the convergence times of D-Wave's computer were also significantly better. These results indicate the merit of D-Wave's computer under certain specific instances. More broadly, our method is relevant to a wider class of performance comparison studies, and 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 against approximation algorithms with polynomial run-time scaling and a provable guarantee of performance.

Physical review. E•Mar 28, 2022•10 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

A PTAS for the Classical Ising Spin Glass Problem on the Chimera Graph Structure

Rishi Saket

We present a polynomial time approximation scheme (PTAS) for the minimum value of the classical Ising Hamiltonian with linear terms on the Chimera graph structure as defined in the recent work of McGeoch and Wang. The result follows from a direct application of the techniques used by Bansal, Bravyi and Terhal who gave a PTAS for the same problem on planar and, in particular, grid graphs. We also show that on Chimera graphs, the trivial lower bound is within a constant factor of the optimum.

arXiv:1306.6943•Jun 20, 2013•9 citations

A Quantum Approximate Optimization Algorithm for Local Hamiltonian Problems

Ishaan Kannan, Robbie King, Leo Zhou

Local Hamiltonian Problems (LHPs) are important problems that are computationally QMA-complete and physically relevant for many-body quantum systems. Quantum MaxCut (QMC), which equates to finding ground states of the quantum Heisenberg model, is the canonical LHP for which various algorithms have been proposed, including semidefinite programs and variational quantum algorithms. We propose and analyze a quantum approximation algorithm which we call the Hamiltonian Quantum Approximate Optimization Algorithm (HamQAOA), which builds on the well-known scheme for combinatorial optimization and is suitable for implementations on near-term hardware. We establish rigorous performance guarantees of the HamQAOA for QMC on high-girth regular graphs, and our result provides bounds on the ground energy density for quantum Heisenberg spin glasses in the infinite size limit that improve with depth. Furthermore, we develop heuristic strategies with which to efficiently obtain good HamQAOA parameters. Through numerical simulations, we show that the HamQAOA empirically outperforms prior algorithms on a wide variety of QMC instances. In particular, our results indicate that the linear-depth HamQAOA can deterministically prepare exact ground states of 1-dimensional antiferromagnetic Heisenberg spin chains described by the Bethe ansatz, in contrast to the exponential depths required in previous protocols for preparing Bethe states.

arXiv:2412.09221•Dec 12, 2024•0 citations

On complexity of the quantum Ising model

Sergey B. Bravyi, Matthew B. Hastings

We study complexity of several problems related to the Transverse field Ising Model (TIM). First, we consider the problem of estimating the ground state energy known as the Local Hamiltonian Problem (LHP). It is shown that the LHP for TIM on degree-3 graphs is equivalent modulo polynomial reductions to the LHP for general k-local `stoquastic' Hamiltonians with any constant $k\ge 2$. This result implies that estimating the ground state energy of TIM on degree-3 graphs is a complete problem for the complexity class StoqMA - an extension of the classical class MA. As a corollary, we complete the complexity classification of 2-local Hamiltonians with a fixed set of interactions proposed recently by Cubitt and Montanaro. Secondly, we study quantum annealing algorithms for finding ground states of classical spin Hamiltonians associated with hard optimization problems. We prove that the quantum annealing with TIM Hamiltonians is equivalent modulo polynomial reductions to the quantum annealing with a certain subclass of k-local stoquastic Hamiltonians. This subclass includes all Hamiltonians representable as a sum of a k-local diagonal Hamiltonian and a 2-local stoquastic Hamiltonian.

arXiv:1410.0703•Oct 2, 2014•8 citations
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.
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.
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 to solve them. An approach developed in computer science for dealing with such problems is to devise approximation algorithms; these are algorithms, whose run time scales polynomially with the input size, that 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 bounded degree graph that provide different approximation guarantees were introduced. D-Wave, a Canadian-based company, has constructed a physical realization of a quantum annealer and has enabled researchers and practitioners to access it via their cloud service. D-Wave is particularly suited for computing an approximation for the ground state of an Ising spin glass on its Chimera and Pegasus graphs-both with a bounded degree. To assess the quality of D-Wave's solution, it is natural to compare it to classical approximation algorithms specifically designed to solve the same problem. In this work, we compare the performance of a recently developed approximation algorithm to solve the Ising spin-glass problem on graphs of bounded degree against the performance of the D-Wave computer. We also compared the performance of D-Wave's computer in the Chimera architecture against the performance of a heuristic tailored specifically to handle the Chimera graph. We found that the D-Wave computer was able to find better approximations for all the random instances of the problem we studied-Gaussian weights, uniform weights, and discrete binary weights. Furthermore, the convergence times of D-Wave's computer were also significantly better. These results indicate the merit of D-Wave's computer under certain specific instances. More broadly, our method is relevant to a wider class of performance comparison studies, and 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 against approximation algorithms with polynomial run-time scaling and a provable guarantee of performance.
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.
Local Hamiltonian Problems (LHPs) are important problems that are computationally QMA-complete and physically relevant for many-body quantum systems. Quantum MaxCut (QMC), which equates to finding ground states of the quantum Heisenberg model, is the canonical LHP for which various algorithms have been proposed, including semidefinite programs and variational quantum algorithms. We propose and analyze a quantum approximation algorithm which we call the Hamiltonian Quantum Approximate Optimization Algorithm (HamQAOA), which builds on the well-known scheme for combinatorial optimization and is suitable for implementations on near-term hardware. We establish rigorous performance guarantees of the HamQAOA for QMC on high-girth regular graphs, and our result provides bounds on the ground energy density for quantum Heisenberg spin glasses in the infinite size limit that improve with depth. Furthermore, we develop heuristic strategies with which to efficiently obtain good HamQAOA parameters. Through numerical simulations, we show that the HamQAOA empirically outperforms prior algorithms on a wide variety of QMC instances. In particular, our results indicate that the linear-depth HamQAOA can deterministically prepare exact ground states of 1-dimensional antiferromagnetic Heisenberg spin chains described by the Bethe ansatz, in contrast to the exponential depths required in previous protocols for preparing Bethe states.
We study complexity of several problems related to the Transverse field Ising Model (TIM). First, we consider the problem of estimating the ground state energy known as the Local Hamiltonian Problem (LHP). It is shown that the LHP for TIM on degree-3 graphs is equivalent modulo polynomial reductions to the LHP for general k-local `stoquastic' Hamiltonians with any constant k≥2k\ge 2k≥2. This result implies that estimating the ground state energy of TIM on degree-3 graphs is a complete problem for the complexity class StoqMA - an extension of the classical class MA. As a corollary, we complete the complexity classification of 2-local Hamiltonians with a fixed set of interactions proposed recently by Cubitt and Montanaro. Secondly, we study quantum annealing algorithms for finding ground states of classical spin Hamiltonians associated with hard optimization problems. We prove that the quantum annealing with TIM Hamiltonians is equivalent modulo polynomial reductions to the quantum annealing with a certain subclass of k-local stoquastic Hamiltonians. This subclass includes all Hamiltonians representable as a sum of a k-local diagonal Hamiltonian and a 2-local stoquastic Hamiltonian.