TY - GEN
T1 - Efficient MILP Decomposition in Quantum Computing for ReLU Network Robustness
AU - Franco, Nicola
AU - Wollschläger, Tom
AU - Poggel, Benedikt
AU - Günnemann, Stephan
AU - Lorenz, Jeanette Miriam
N1 - Publisher Copyright:
© 2023 IEEE.
PY - 2023
Y1 - 2023
N2 - 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.
AB - 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.
KW - Hybrid Algorithm
KW - Mixed-Integer Linear Programming
KW - Quantum Computing
UR - http://www.scopus.com/inward/record.url?scp=85180006733&partnerID=8YFLogxK
U2 - 10.1109/QCE57702.2023.00066
DO - 10.1109/QCE57702.2023.00066
M3 - Conference contribution
AN - SCOPUS:85180006733
T3 - Proceedings - 2023 IEEE International Conference on Quantum Computing and Engineering, QCE 2023
SP - 524
EP - 534
BT - Proceedings - 2023 IEEE International Conference on Quantum Computing and Engineering, QCE 2023
A2 - Muller, Hausi
A2 - Alexev, Yuri
A2 - Delgado, Andrea
A2 - Byrd, Greg
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 4th IEEE International Conference on Quantum Computing and Engineering, QCE 2023
Y2 - 17 September 2023 through 22 September 2023
ER -