Building an Iterative Heuristic Solver for a Quantum Annealer

By Gili Rosenberg, Mohammad Vazifeh, Brad Woods, & Eldad Haber

A quantum annealer heuristically minimizes quadratic unconstrained binary optimization (QUBO) problems, but is limited by the physical hardware in the size and density of the problems it can handle. We have developed a meta-heuristic solver that utilizes D-Wave Systems’ quantum annealer (or any other QUBO problem optimizer) to solve larger or denser problems, by iteratively solving subproblems, while keeping the rest of the variables fixed. We present our algorithm, several variants, and the results for the optimization of standard QUBO problem instances from OR-Library of sizes 500 and 2500 as well as the Palubeckis instances of sizes 3000 to 7000. For practical use of the solver, we show the dependence of the time to best solution on the desired gap to the best known solution. In addition, we study the dependence of the gap and the time to best solution on the size of the problems solved by the underlying optimizer.

Journal reference: Computational Optimization and Applications , Volume 65, Issue 3, pp 845–869

PDF     arXiv preprint

Most Recent Papers

Variationally Scheduled Quantum Simulation

By Shunji Matsuura, Samantha Buck, Valentin Senicourt, & Arman Zaribafiyan Eigenstate preparation is ubiquitous in quantum computing, and a standard approach for generating the lowest-energy states of a given system is by employing adiabatic state preparation...

A Quantum Annealing-Based Approach to Extreme Clustering

By Tim Jaschek, Marko Bucyk, & Jaspreet S. Oberoi Clustering, or grouping, dataset elements based on similarity can be used not only to classify a dataset into a few categories, but also to approximate it by a relatively large number of representative elements. In...