Building an iterative heuristic solver for a quantum annealer

Abstract

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.

21 pages, 4 figures; minor edits

References in corpus (9)

• Digital quantum simulation of fermionic models with a superconducting circuit
• What is the Computational Value of Finite Range Tunneling?
• Minor-embedding in adiabatic quantum computation: II. Minor-universal graph design
• Probing for quantum speedup in spin glass problems with planted solutions
• Quantum annealing correction for random Ising problems
• Simulated Quantum Annealing Can Be Exponentially Faster than Classical Simulated Annealing
• Unraveling Quantum Annealers using Classical Hardness
• Error correction for encoded quantum annealing
• From local to global ground states in Ising spin glasses

Cited by in corpus (14)

• Physics-Inspired Optimization for Quadratic Unconstrained Problems Using a Digital Annealer
• Efficient partition of integer optimization problems with one-hot encoding
• Improving solutions by embedding larger subproblems in a D-Wave quantum annealer
• Network Community Detection On Small Quantum Computers
• Multi-block ADMM Heuristics for Mixed-Binary Optimization on Classical and Quantum Computers
• Quantum annealing applications, challenges and limitations for optimisation problems compared to classical solvers
• Quantum Annealing Learning Search for solving QUBO problems
• Quantum Computing Techniques for Multi-Knapsack Problems
• Towards Hybrid Classical-Quantum Computation Structures in Wirelessly-Networked Systems
• Digitized Counterdiabatic Quantum Algorithms for Logistics Scheduling
• Hybrid Optimization Method Using Simulated-Annealing-Based Ising Machine and Quantum Annealer
• Tabu-driven Quantum Neighborhood Samplers
• Ground States of the Mean-Field Spin Glass with 3-Spin Couplings
• Hybrid classical-quantum branch-and-bound algorithm for solving integer linear problems