Efficient MILP Decomposition in Quantum Computing for ReLU Network Robustness
This addresses the challenge of limited qubit availability in quantum computing for optimization problems, with incremental improvements in decomposition methods.
The study tackled the problem of efficiently solving Mixed-Integer Linear Programming (MILP) on quantum computers by decomposing it into smaller subproblems, showing that Dantzig-Wolfe decomposition saves up to 90% of qubits compared to existing methods for certifying ReLU network robustness.
Emerging quantum computing technologies, such as Noisy Intermediate-Scale Quantum (NISQ) devices, offer potential advancements in solving mathematical optimization problems. However, limitations in qubit availability, noise, and errors pose challenges for practical implementation. In this study, we examine two decomposition methods for Mixed-Integer Linear Programming (MILP) designed to reduce the original problem size and utilize available NISQ devices more efficiently. We concentrate on breaking down the original problem into smaller subproblems, which are then solved iteratively using a combined quantum-classical hardware approach. We conduct a detailed analysis for the decomposition of MILP with Benders and Dantzig-Wolfe methods. In our analysis, we show that the number of qubits required to solve Benders is exponentially large in the worst-case, while remains constant for Dantzig-Wolfe. Additionally, we leverage Dantzig-Wolfe decomposition on the use-case of certifying the robustness of ReLU networks. Our experimental results demonstrate that this approach can save up to 90\% of qubits compared to existing methods on quantum annealing and gate-based quantum computers.