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 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 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/ϵ, where ϵ 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.
Quantum annealing is getting increasing attention in combinatorial optimization. The quantum processing unit by D-Wave is constructed to approximately solve Ising models on so-called Chimera graphs. Ising models are equivalent to quadratic unconstrained binary optimization (QUBO) problems and maximum cut problems on the associated graphs. We have tailored branch-and-cut as well as semidefinite programming algorithms for solving Ising models for Chimera graphs to provable optimality and use the strength of these approaches for comparing our solution values to those obtained on the current quantum annealing machine, D-Wave 2000Q. This allows for the assessment of the quality of solutions produced by the D-Wave hardware. In addition, we also evaluate the performance of a heuristic by Selby. It has been a matter of discussion in the literature how well the D-Wave hardware performs at its native task, and our experiments shed some more light on this issue. In particular, we examine how reliably the D-Wave computer can deliver true optimum solutions and present some surprising results.
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.
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.
The recent availability of the first commercial quantum computers has provided a promising tool to tackle NP hard problems which can only be solved heuristically with present techniques. However, it is unclear if the current state of quantum computing already provides a quantum advantage over the current state of the art in classical computing. This article assesses the performance of the D-Wave 2X quantum annealer on two NP hard graph problems, in particular clique finding and graph partitioning. For this, we provide formulations as Qubo and Ising Hamiltonians suitable for the quantum annealer and compare a variety of quantum solvers (Sapi, QBSolv, QSage provided by D-Wave Sys, Inc.) to current classical algorithms (METIS, Simulated Annealing, third-party clique finding and graph splitting heuristics) on certain test sets of graphs. We demonstrate that for small graph instances, classical methods still outperform the quantum annealer in terms of computing time, even though the quality of the best solutions obtained is comparable. Nevertheless, due to the limited problem size which can be embedded on the D-Wave 2X chip, the aforementioned finding applies to most of problems of general nature solvable on the quantum annealer. For instances specifically designed to fit the D-Wave 2X architecture, we observe substantial speed-ups in computing time over classical approaches.