Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2205.00900 · IEEE International Conference on Quantum Computing and Engineering (QCE)

Quantum Robustness Verification: A Hybrid Quantum-Classical Neural Network Certification Algorithm

Nicola Franco, Tom Wollschläger, Nicholas Gao, Jeanette Miriam Lorenz, Stephan Günnemann

Published Sep 1, 2022• 29 citations
arXivHTMLPDF

Abstract

In recent years, quantum computers and algorithms have made significant progress indicating the prospective importance of quantum computing (QC). Especially combinatorial optimization has gained a lot of attention as an application field for near-term quantum computers, both by using gate-based QC via the Quantum Approximate Optimization Algorithm and by quantum annealing using the Ising model. However, demonstrating an advantage over classical methods in real-world applications remains an active area of research. In this work, we investigate the robustness verification of ReLU networks, which involves solving many-variable mixed-integer programs (MIPs), as a practical application. Classically, complete verification techniques struggle with large networks as the combinatorial space grows exponentially, implying that realistic networks are difficult to be verified by classical methods. To alleviate this issue, we propose to use QC for neural network verification and introduce a hybrid quantum procedure to compute provable certificates. By applying Benders decomposition, we split the MIP into a quadratic unconstrained binary optimization and a linear program which are solved by quantum and classical computers, respectively. We further improve existing hybrid methods based on the Benders decomposition by reducing the overall number of iterations and placing a limit on the maximum number of qubits required. We show that, in a simulated environment, our certificate is sound, and provides bounds on the minimum number of qubits necessary to approximate the problem. Finally, we evaluate our method within simulations and on quantum hardware.

DOI
10.1109/qce53715.2022.00033

Related papers

Efficient MILP Decomposition in Quantum Computing for ReLU Network Robustness

Nicola Franco, Tom Wollschläger, Benedikt Poggel +2 more

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.

arXiv:2305.00472•IEEE International Conference on Quantum Computing and Engineering (QCE)•Sep 17, 2023•13 citations

On Hybrid Quantum and Classical Computing Algorithms for Mixed-Integer Programming

Chin-Yao Chang, E. D. Jones, Yao, Yiyun +2 more

Quantum computing is emerging as a new computing resource that could be superior to conventional computing for certain classes of optimization problems. However, in principle, most existing approaches to quantum optimization are intended to solve unconstrained binary programming problems, while mixed-integer linear programming is of most interest in practice. We attempt to bridge the gap between the capability of quantum computing and real-world applications by developing a new approach for mixed-integer programming. The approach applies Benders decomposition to decompose the mixed-integer programming into binary programming and linear programming sub-problems, which are solved by a noisy intermediate-scale quantum processor and conventional processor, respectively. The algorithm is provably able to reach the optimal solution of the original mixed-integer programming problem. The algorithm is tested on a D-Wave 2000Q quantum processing unit and is shown to be effective for small-scaled test cases. We also test the algorithm on a mixed-integer programming inspired by power system applications. Many insights are drawn from the numerical results for both the capabilities and limitations of the proposed algorithm.

arXiv:2010.07852•Oct 15, 2020•36 citations

A hybrid quantum–classical algorithm for mixed-integer optimization in power systems

Petros Ellinas, Samuel C. Chevalier, Spyros Chatzivasileiadis

Mixed Integer Linear Programming (MILP) can be considered the backbone of the modern power system optimization process, with a large application spectrum, from Unit Commitment and Optimal Transmission Switching to verifying Neural Networks for power system applications. The main issue of these formulations is the computational complexity of the solution algorithms , as they are considered NP-Hard problems. Quantum computing has been tested as a potential solution towards reducing the computational burden imposed by these problems, providing promising results, motivating the can be used to speedup the solution of MILPs . In this work, we present a general framework for solving power system optimization problems with a Quantum Computer (QC), which leverages mathematical tools and QCs’ sampling ability to provide accelerated solutions. Our guiding applications are the optimal transmission switching and the verification of neural networks trained to solve a DC Optimal Power Flow. Specifically, using an accelerated version of Benders Decomposition , we split a given MILP into an Integer Master Problem and a linear Subproblem and solve it through a hybrid “quantum–classical” approach, getting the best of both worlds. We provide 2 use cases, and benchmark the developed framework against other classical and hybrid methodologies, to demonstrate the opportunities and challenges of hybrid quantum–classical algorithms for power system mixed integer optimization problems.

arXiv:2404.10693•Electric Power Systems Research•Jul 6, 2024•33 citations

Robustness Verification of Binary Neural Networks: An Ising and Quantum-Inspired Framework

Rahul Kumar Singh, Seyran Saeedi, Zheng Zhang

Binary neural networks (BNNs) are increasingly deployed in edge computing applications due to their low hardware complexity and high energy efficiency. However, verifying the robustness of BNNs against input perturbations, including adversarial attacks, remains computationally challenging because the underlying decision problem is inherently combinatorial. In this paper, we propose an Ising- and quantum-inspired framework for BNN robustness verification. We show that, for a broad class of BNN architectures, robustness verification can be formulated as a Quadratic Constrained Boolean Optimization (QCBO) problem and subsequently transformed into a Quadratic Unconstrained Boolean Optimization (QUBO) instance amenable to Ising and quantum-inspired solvers. We demonstrate the feasibility of this formulation on binarized MNIST by solving the resulting QUBOs with a free energy machine (FEM) solver and simulated annealing. We also show the deployment of this framework on quantum annealing and digital annealing platforms. Our results highlight the potential of quantum-inspired computing and Ising computing as a pathway toward trustworthy AI systems.

arXiv:2602.13536•Feb 14, 2026•1 citation

On Quantum Computing for Mixed-Integer Programming

Chin-Yao Chang, Eric B. Jones, Peter A Graf

Quantum computing (QC) is emerging as a new computing resource that could be superior to conventional computing (CC) for certain classes of optimization problems. However, in principle QC can only solve unconstrained binary programming problems, while mixed-integer linear programming (MIP) is of most interest in practice. We attempt to bridge the gap between the capability of QC and real-world applications by developing a new approach for MIP. The idea is decomposing the MIP into binary programming and linear programming (LP) problems, which are respectively solved by QC and conventional computing. We formalize a decomposition approach that ensures that with a sufficient number of back and forth iterations, the algorithm can reach the optimal solution of the original MIP problem. The algorithm is tested on a 2000Q D-Wave quantum processing units (QPU) and is shown to be effective for small-scaled test cases.

•Oct 15, 2020•6 citations

Hybrid Quantum–Classical Benders' Decomposition for Federated Learning Scheduling in Distributed Networks

Xinliang Wei, Lei Fan, Yuanxiong Guo +3 more

Scheduling multiple federated learning (FL) models within a distributed network, especially in large-scale scenarios, poses significant challenges since it involves solving NP-hard mixed-integer nonlinear programming (MINLP) problems. However, it's imperative to optimize participant selection and learning rate determination for these FL models to avoid excessive training costs and prevent resource contention. While some existing methods focus solely on optimizing a single global FL model, others struggle to achieve optimal solutions as the problem grows more complex. In this paper, exploiting the potential of quantum computing, we introduce the Hybrid Quantum-Classical Benders' Decomposition (HQCBD) algorithm to effectively tackle the joint MINLP optimization problem for multi-model FL training. HQCBD combines quantum and classical computing to solve the joint participant selection and learning scheduling problem. It decomposes the optimization problem into a master problem with binary variables and small subproblems with continuous variables, then leverages the strengths of both quantum and classical computing to solve them respectively and iteratively. Furthermore, we propose the Hybrid Quantum-Classical Multiple-cuts Benders' Decomposition (MBD) algorithm, which utilizes the inherent capabilities of quantum algorithms to produce multiple cuts in each round, to speed up the proposed HQCBD algorithm. Extensive simulation on the commercial quantum annealing machine demonstrates the effectiveness and robustness of the proposed methods (both HQCBD and MBD), with improvements of up to 70.3% in iterations and 81% in computation time over the classical Benders' decomposition algorithm on classical CPUs, even at modest scales.

IEEE Transactions on Network Science and Engineering•Aug 14, 2024•28 citations
In recent years, quantum computers and algorithms have made significant progress indicating the prospective importance of quantum computing (QC). Especially combinatorial optimization has gained a lot of attention as an application field for near-term quantum computers, both by using gate-based QC via the Quantum Approximate Optimization Algorithm and by quantum annealing using the Ising model. However, demonstrating an advantage over classical methods in real-world applications remains an active area of research. In this work, we investigate the robustness verification of ReLU networks, which involves solving many-variable mixed-integer programs (MIPs), as a practical application. Classically, complete verification techniques struggle with large networks as the combinatorial space grows exponentially, implying that realistic networks are difficult to be verified by classical methods. To alleviate this issue, we propose to use QC for neural network verification and introduce a hybrid quantum procedure to compute provable certificates. By applying Benders decomposition, we split the MIP into a quadratic unconstrained binary optimization and a linear program which are solved by quantum and classical computers, respectively. We further improve existing hybrid methods based on the Benders decomposition by reducing the overall number of iterations and placing a limit on the maximum number of qubits required. We show that, in a simulated environment, our certificate is sound, and provides bounds on the minimum number of qubits necessary to approximate the problem. Finally, we evaluate our method within simulations and on quantum hardware.
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.
Quantum computing is emerging as a new computing resource that could be superior to conventional computing for certain classes of optimization problems. However, in principle, most existing approaches to quantum optimization are intended to solve unconstrained binary programming problems, while mixed-integer linear programming is of most interest in practice. We attempt to bridge the gap between the capability of quantum computing and real-world applications by developing a new approach for mixed-integer programming. The approach applies Benders decomposition to decompose the mixed-integer programming into binary programming and linear programming sub-problems, which are solved by a noisy intermediate-scale quantum processor and conventional processor, respectively. The algorithm is provably able to reach the optimal solution of the original mixed-integer programming problem. The algorithm is tested on a D-Wave 2000Q quantum processing unit and is shown to be effective for small-scaled test cases. We also test the algorithm on a mixed-integer programming inspired by power system applications. Many insights are drawn from the numerical results for both the capabilities and limitations of the proposed algorithm.
Mixed Integer Linear Programming (MILP) can be considered the backbone of the modern power system optimization process, with a large application spectrum, from Unit Commitment and Optimal Transmission Switching to verifying Neural Networks for power system applications. The main issue of these formulations is the computational complexity of the solution algorithms , as they are considered NP-Hard problems. Quantum computing has been tested as a potential solution towards reducing the computational burden imposed by these problems, providing promising results, motivating the can be used to speedup the solution of MILPs . In this work, we present a general framework for solving power system optimization problems with a Quantum Computer (QC), which leverages mathematical tools and QCs’ sampling ability to provide accelerated solutions. Our guiding applications are the optimal transmission switching and the verification of neural networks trained to solve a DC Optimal Power Flow. Specifically, using an accelerated version of Benders Decomposition , we split a given MILP into an Integer Master Problem and a linear Subproblem and solve it through a hybrid “quantum–classical” approach, getting the best of both worlds. We provide 2 use cases, and benchmark the developed framework against other classical and hybrid methodologies, to demonstrate the opportunities and challenges of hybrid quantum–classical algorithms for power system mixed integer optimization problems.
Binary neural networks (BNNs) are increasingly deployed in edge computing applications due to their low hardware complexity and high energy efficiency. However, verifying the robustness of BNNs against input perturbations, including adversarial attacks, remains computationally challenging because the underlying decision problem is inherently combinatorial. In this paper, we propose an Ising- and quantum-inspired framework for BNN robustness verification. We show that, for a broad class of BNN architectures, robustness verification can be formulated as a Quadratic Constrained Boolean Optimization (QCBO) problem and subsequently transformed into a Quadratic Unconstrained Boolean Optimization (QUBO) instance amenable to Ising and quantum-inspired solvers. We demonstrate the feasibility of this formulation on binarized MNIST by solving the resulting QUBOs with a free energy machine (FEM) solver and simulated annealing. We also show the deployment of this framework on quantum annealing and digital annealing platforms. Our results highlight the potential of quantum-inspired computing and Ising computing as a pathway toward trustworthy AI systems.
Quantum computing (QC) is emerging as a new computing resource that could be superior to conventional computing (CC) for certain classes of optimization problems. However, in principle QC can only solve unconstrained binary programming problems, while mixed-integer linear programming (MIP) is of most interest in practice. We attempt to bridge the gap between the capability of QC and real-world applications by developing a new approach for MIP. The idea is decomposing the MIP into binary programming and linear programming (LP) problems, which are respectively solved by QC and conventional computing. We formalize a decomposition approach that ensures that with a sufficient number of back and forth iterations, the algorithm can reach the optimal solution of the original MIP problem. The algorithm is tested on a 2000Q D-Wave quantum processing units (QPU) and is shown to be effective for small-scaled test cases.
Scheduling multiple federated learning (FL) models within a distributed network, especially in large-scale scenarios, poses significant challenges since it involves solving NP-hard mixed-integer nonlinear programming (MINLP) problems. However, it's imperative to optimize participant selection and learning rate determination for these FL models to avoid excessive training costs and prevent resource contention. While some existing methods focus solely on optimizing a single global FL model, others struggle to achieve optimal solutions as the problem grows more complex. In this paper, exploiting the potential of quantum computing, we introduce the Hybrid Quantum-Classical Benders' Decomposition (HQCBD) algorithm to effectively tackle the joint MINLP optimization problem for multi-model FL training. HQCBD combines quantum and classical computing to solve the joint participant selection and learning scheduling problem. It decomposes the optimization problem into a master problem with binary variables and small subproblems with continuous variables, then leverages the strengths of both quantum and classical computing to solve them respectively and iteratively. Furthermore, we propose the Hybrid Quantum-Classical Multiple-cuts Benders' Decomposition (MBD) algorithm, which utilizes the inherent capabilities of quantum algorithms to produce multiple cuts in each round, to speed up the proposed HQCBD algorithm. Extensive simulation on the commercial quantum annealing machine demonstrates the effectiveness and robustness of the proposed methods (both HQCBD and MBD), with improvements of up to 70.3% in iterations and 81% in computation time over the classical Benders' decomposition algorithm on classical CPUs, even at modest scales.