Efficient MILP Decomposition in Quantum Computing for ReLU Network Robustness

Nicola Franco, Tom Wollschläger, Benedikt Poggel, Stephan Günnemann, Jeanette Miriam Lorenz

Publikation: Beitrag in Buch/Bericht/KonferenzbandKonferenzbeitragBegutachtung

1 Zitat (Scopus)

Abstract

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.

OriginalspracheEnglisch
TitelProceedings - 2023 IEEE International Conference on Quantum Computing and Engineering, QCE 2023
Redakteure/-innenHausi Muller, Yuri Alexev, Andrea Delgado, Greg Byrd
Herausgeber (Verlag)Institute of Electrical and Electronics Engineers Inc.
Seiten524-534
Seitenumfang11
ISBN (elektronisch)9798350343236
DOIs
PublikationsstatusVeröffentlicht - 2023
Veranstaltung4th IEEE International Conference on Quantum Computing and Engineering, QCE 2023 - Bellevue, USA/Vereinigte Staaten
Dauer: 17 Sept. 202322 Sept. 2023

Publikationsreihe

NameProceedings - 2023 IEEE International Conference on Quantum Computing and Engineering, QCE 2023
Band1

Konferenz

Konferenz4th IEEE International Conference on Quantum Computing and Engineering, QCE 2023
Land/GebietUSA/Vereinigte Staaten
OrtBellevue
Zeitraum17/09/2322/09/23

Fingerprint

Untersuchen Sie die Forschungsthemen von „Efficient MILP Decomposition in Quantum Computing for ReLU Network Robustness“. Zusammen bilden sie einen einzigartigen Fingerprint.

Dieses zitieren