Binary Integer Reformulations for Adiabatic Quantum Annealing Hardware

It has been demonstrated that Binary Integer Programming (BIP) formulations can be reformulated to a corresponding quadratic unconstrained binary optimization (QUBO) problem. The reformulation allows for BIPs to run as QUBOs on adiabatic quantum annealing hardware. Current BIP to QUBO reformulation techniques propagate dense QUBO structures that are not ideal for current hardware where quantum bits, and the connections between them, are scarce. We propose a methodology for BIP to QUBO reformulation that results in a sparse QUBO that, when used to embed set-partitioning problems onto a D-Wave Pegasus topology, requires 80% fewer qubits and is embedded is 41 times faster. The same methodology for set-covering problems requires 77% fewer qubits and is embedded 26 times faster. We discuss the limitations of the technique and avenues for future extensions.