Building an iterative heuristic solver for a quantum annealer
arXiv:1507.07605 · doi:10.1007/s10589-016-9844-y
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.
arXiv comment21 pages, 4 figures; minor edits
References in corpus (17)
- Quantum Annealing in the Transverse Ising Model
- Quantum annealing with more than one hundred qubits
- Theory of Quantum Annealing of an Ising Spin Glass
- Quantum Annealing: A New Method for Minimizing Multidimensional Functions
- Defining and detecting quantum speedup
- Digital quantum simulation of fermionic models with a superconducting circuit
- Architectural considerations in the design of a superconducting quantum annealing processor
- What is the Computational Value of Finite Range Tunneling?
- Minor-embedding in adiabatic quantum computation: II. Minor-universal graph design
- Error corrected quantum annealing with hundreds of qubits
- Probing for quantum speedup in spin glass problems with planted solutions
- Optimization by Quantum Annealing: Lessons from hard 3-SAT cases
- 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