The performances of two D-Wave 2 machines (476 and 496 qubits) and of a 1097-qubit D-Wave 2X were investigated. Each chip has a Chimera interaction graph G. Problem input consists of values for the fields hj and for the two-qubit interactions Ji,j of an Ising spin-glass problem formulated on G. Output is returned in terms of a spin configuration {sj}, with sj = +1 or –1. We generated random spanning trees (RSTs) uniformly distributed over all spanning trees of G. On the 476-qubit D-Wave 2, RSTs were generated on the full chip with Ji,j = –1 and hj = 0 and solved one thousand times. The distribution of solution energies and the average magnetization of each qubit were determined. On both the 476- and 1097- qubit machines, four identical spanning trees were generated on each quadrant of the chip. The statistical independence of these regions was investigated.
The performances of two D-Wave 2 machines (476 and 496 qubits) and of a 1097-qubit D-Wave 2X were investigated. Each chip has a Chimera interaction graph G. Problem input consists of values for the fields hj and for the two-qubit interactions Ji,j of an Ising spin-glass problem formulated on G. Output is returned in terms of a spin configuration {sj}, with sj = +1 or –1. We generated random spanning trees (RSTs) uniformly distributed over all spanning trees of G. On the 476-qubit D-Wave 2, RSTs were generated on the full chip with Ji,j = –1 and hj = 0 and solved one thousand times. The distribution of solution energies and the average magnetization of each qubit were determined. On both the 476- and 1097- qubit machines, four identical spanning trees were generated on each quadrant of the chip. The statistical independence of these regions was investigated.
The performance of a 496 qubit D-Wave Two quantum computer was investigated for spanning tree problems. The chip has a Chimera interaction graph G, an 8x8 lattice of clusters of eight qubits. Problem input consists of values for the fields hj and for the two-qubit interactions Ji,j of an Ising spin-glass problem formulated on G. Output is returned in terms of a spin configuration {sj}, with sj = ±1. A tree is a connected, undirected subgraph of G that contains no cycles, and a spanning tree is a tree which includes all of the vertices of G. We generated random spanning trees (RSTs), uniformly distributed over all spanning trees of G. One hundred RSTs with random Ji,j = {-1,1} and hj = 0 were generated on the full 8x8 graph G of the chip. Each RST problem was solved up to one hundred times and the number of times the ground state energy was found was recorded. This procedure was repeated for square subgraphs G′, thereby providing results for portions of the chip with dimensions ranging from 2x2 to 8x8.
Calculations on D-Wave machines are presented, both for the 500-qubit and the 1000-qubit machines. Results are presented for spanning trees on the available K 4,4 Chimera graphs of both machines. Comparing trees of approximately the same size, the frequency of finding the ground state for the 1000-qubit machine is significantly improved over the 500- qubit older generation machine. Spanning trees are difficult problems for solution by adiabatic quantum computers, so the enhanced frequency of finding the ground state for newer machine generations and larger machines is encouraging for this immature technology.
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.
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.
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.
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.