Solving MIPs with Enhanced Quantum-Ready Decomposition

Why is quantum computing interesting for optimization problems? Quantum computing (QC) offers exciting opportunities to solve certain computational problems like in combinatorial optimization more efficiently than classical approaches, thereby accelerating solving challenging optimization problems [1,2]. However, optimization problems must be translated into an appropriate formulation to be amendable to quantum computing. A problem class often studied on a quantum computer or annealer is the class of quadratic unconstrained binary optimization (QUBO) problems. The reason is that QUBOs are closely related to Ising models, and any QUBO can be mapped directly to Ising models and vice versa [3]. With mathematical transformations, many combinatorial optimization problems can be written as a QUBO and solved using quantum computers.

However, industry-relevant optimization problems usually consist of substantial inequality constraints and continuous variables - quite the opposite of unconstrained and binary. While strategies exist to capture inequality constraints and continuous variables as QUBOs, this usually comes at the cost of a dimensional explosion. In the current noisy intermediate-scale quantum (NISQ) computing era, quantum processor units (QPUs) equipped with millions of qubits are not available. As such, a complete, qubit-wasteful reformulation to QUBOs is impractical. A promising research direction is identifying and solving difficult parts of an optimization model on QPUs while addressing the simpler parts using classical hardware like CPUs and GPUs.

Specifically for quantum utility and the quantum routines in hybrid and hardware-agnostic workflows, respecting the available QPU requirements is a must. Larger quantum circuits can be split via techniques like circuit knitting to deal with the restricted number of available qubits. But what about solving an optimization problem with an algorithm that uses some quantum and classical routines within and, therefore, doesn’t just require splitting a large quantum circuit but splitting the entire problem while guaranteeing convergence to optimality within the process? This is where Quantagonia’s HybridSolver and our cutting-edge decomposition techniques come in. This approach enables the integration of built-in hardware accelerators of CPUs, GPUs, and QPUs into hybrid and hardware-agnostic workflows, ensuring adherence to QPU requirements while aiming for quantum utility. Combined with techniques like Quantum Branch and Bound (check out our two blogs on that: here and here), the HybridSolver can now be used to truly solve not just QUBOs but also mixed integer programs (MIPs) in a hybrid quantum-classical and hardware-agnostic fashion, all with optimality-proof!

How does our HybridSolver do this? It leverages proprietary decomposition methods that build on techniques such as Benders decomposition and Dantzig-Wolfe reformulation to decompose optimization problems into difficult (MIPs with continuous variables and inequality constraints) and easily reformulated (binary programs with equality constraints) parts. The easily reformulated problems possess a QUBO representation, allowing us to solve them using various (heuristic) quantum optimization techniques within our hybrid workflows. Our decomposition approaches can handle approximate solutions of the auxiliary problems while still guaranteeing to terminate with the globally optimal solution of the original optimization task. This method is both effective and adaptable, allowing for an increase in the size of QUBOs as more qubits become available on QPUs.

Are you interested in using our hybrid classic-quantum optimization solver for your optimization problems, such as mixed linear integer programming? Reach out to us or book a demo and see how easy it is to model your optimization problem in, e.g., python and solve it via Quantagonia’s HybridSolver.

‍

‍

[1] Pirnay, N., Ulitzsch, V., Wilde, F., Eisert, J., & Seifert, J.-P. (2022). A super-polynomial quantum advantage for combinatorial optimization problems. arXiv.

[2] Lucas, A. (2014). Ising formulations of many NP problems. Frontiers in Physics, 2. Frontiers Media SA.

[3] Cerezo, M., Arrasmith, A., Babbush, R., Benjamin, S. C., Endo, S., Fujii, K., McClean, J. R., Mitarai, K., Yuan, X., Cincio, L., & Coles, P. J. (2021). Variational quantum algorithms. Nature Reviews Physics, 3, 625–644.