Reducing QUBOs for more scalable annealing

"”Reducing Binary Quadratic Forms for More Scalable Quantum Annealing"

Published by Georg Hahn, Hristo N. Djidjev (Imperial College, Los Alamos NL), 26th January 2018

Quantum annealing
Reducing QUBOs for more scalable annealing

Qu&Co comments on this publication:

Quantum annealers such as the D-Wave 2X allow solving NP-hard optimization problems that can be expressed as quadratic unconstrained binary (QUBO) programs. However, the relatively small number of available qubits poses a severe limitation to the range of problems that can be solved. In this paper, Hahn et al. explore the suitability of preprocessing methods for reducing the sizes of the input programs and thereby the number of qubits required for their solution on quantum computers. Specifically preprocessing reductions are discussed for max. clique and max. cut problems.