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

Abstract

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 comment7 pages, 5 figures

References in corpus (19)

• Ising formulations of many NP problems
• Quantum Annealing in the Transverse Ising Model
• Adiabatic Quantum Computing
• Ultimate physical limits to computation
• The maximum speed of dynamical evolution
• Quantum annealing with more than one hundred qubits
• Theory of Quantum Annealing of an Ising Spin Glass
• Quantum Annealing and Analog Quantum Computation
• Observation of topological phenomena in a programmable lattice of 1,800 qubits
• What is the Computational Value of Finite Range Tunneling?
• Anderson localization casts clouds over adiabatic quantum optimization
• Demonstration of a scaling advantage for a quantum annealer over simulated annealing
• Entanglement in a quantum annealing processor
• Quantum versus Classical Annealing of Ising Spin Glasses
• Probing for quantum speedup in spin glass problems with planted solutions
• Scaling advantage in quantum simulation of geometrically frustrated magnets
• Prospects for Quantum Enhancement with Diabatic Quantum Annealing
• Exponential complexity of an adiabatic algorithm for an NP-complete problem
• From local to global ground states in Ising spin glasses

Cited by in corpus (5)

• Quantum Annealing: An Overview
• Load Balancing For High Performance Computing Using Quantum Annealing
• Random Projection using Random Quantum Circuits
• Development of research network on Quantum Annealing Computation and Information using Google Scholar data
• Investigating Techniques to Optimise the Layout of Turbines in a Windfarm using a Quantum Computer