  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.
