Efficient Embedding of Integer Programming Problems on Quantum Annealers

David E. Bernal, Kyle E. C. Booth, Raouf Dridi +3 more

Richard S. Barr, Toby Huskinson

Abstract 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.

SRIDHAR R. TAYUR, Ananth Tenneti

In this mini-review, we introduce and summarize research from the Quantum Technologies Group (QTG) at Carnegie Mellon University related to computational experience with quantum annealing, performed in collaboration with several other institutions including IIT-Madras and NASA (QuAIL). We present a novel hybrid quantum-classical heuristic algorithm (GAMA, Graver Augmented Multi-seed Algorithm) for non-linear, integer optimization, and illustrate it on an application (in cancer genomics). We then present an algebraic geometry-based algorithm for embedding a problem onto a hardware that is not fully connected, along with a companion Integer Programming (IP) approach. Next, we discuss the performance of two photonic devices - the Temporal Multiplexed Ising Machine (TMIM) and the Spatial Photonic Ising Machine (SPIM) - on Max-Cut and Number Partitioning instances. We close with an outline of the current work.

Elijah Pelofske, Georg Hahn, Hristo N. Djidjev

Tomáš Vyskočil, Scott Pakin, Hristo N. Djidjev

Dawei Wang, Kedi Zheng, Fei Teng +1 more

Quantum annealing (QA) can be used to efficiently solve quadratic unconstrained binary optimization (QUBO) problems. Grid partitioning (GP), which is a classic NP-hard integer programming problem, can potentially be solved much faster using QA. However, inequality constraints in the GP optimization model are difficult to handle. In this study, a novel solution framework based on QA is proposed for GP problems. The integer slack (IS) and binary expansion methods are applied to transform GP problems into QUBO problems. Instead of introducing continuous variables in traditional slack methods, the proposed IS method can avoid complex iteration processes when using QA. The case study demonstrates that the IS method obtains accurate feasible solutions with less calculation time.