# Efficient MILP Decomposition in Quantum Computing for ReLU Network Robustness

arXiv: https://arxiv.org/abs/2305.00472 · HTML: https://mlsanity.com/paper/2305.00472/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 44 references that are in the map.
- First posted on arXiv 30 Apr 2023.

## Builds on (most cited first, 12 of 12)

- [Towards Deep Learning Models Resistant to Adversarial Attacks](https://mlsanity.com/paper/1706.06083/) (2017)
- [Reluplex: An Efficient SMT Solver for Verifying Deep Neural Networks](https://mlsanity.com/paper/1702.01135/) (2017)
- [Provable defenses against adversarial examples via the convex outer adversarial polytope](https://mlsanity.com/paper/1711.00851/) (2017)
- [Formal Verification of Piece-Wise Linear Feed-Forward Neural Networks](https://mlsanity.com/paper/1705.01320/) (2017)
- [Beta-CROWN: Efficient Bound Propagation with Per-neuron Split Constraints for Complete and Incomplete Neural Network Robustness Verification](https://mlsanity.com/paper/2103.06624/) (2021)
- [Towards Stable and Efficient Training of Verifiably Robust Neural Networks](https://mlsanity.com/paper/1906.06316/) (2019)
- [PRIMA: General and Precise Neural Network Certification via Scalable Convex Hull Approximations](https://mlsanity.com/paper/2103.03638/) (2021)
- [Scaling Polyhedral Neural Network Verification on GPUs](https://mlsanity.com/paper/2007.10868/) (2020)
- [Fast clique minor generation in Chimera qubit connectivity graphs](https://mlsanity.com/paper/1507.04774/) (2015)
- [Quantum Annealing vs. QAOA: 127 Qubit Higher-Order Ising Problems on NISQ Computers](https://mlsanity.com/paper/2301.00520/) (2023)
- [Multi-block ADMM Heuristics for Mixed-Binary Optimization on Classical and Quantum Computers](https://mlsanity.com/paper/2001.02069/) (2020)
- [Hybrid Quantum Benders' Decomposition For Mixed-integer Linear Programming](https://mlsanity.com/paper/2112.07109/) (2021)

## Built on by (most cited first, 4 of 4)

- [Discrete Randomized Smoothing Meets Quantum Computing](https://mlsanity.com/paper/2408.00895/) (2024)
- [Quadratic Advantage with Quantum Randomized Smoothing Applied to Time-Series Analysis](https://mlsanity.com/paper/2407.18021/) (2024)
- [Certifiably Robust Encoding Schemes](https://mlsanity.com/paper/2408.01200/) (2024)
- [Exact and Asymptotically Complete Robust Verifications of Neural Networks via Ising Solvers](https://mlsanity.com/paper/2603.00408/) (2026)

## Abstract (arXiv)

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.