On Quantum Computing for Neural Network Robustness Verification
Presentation held at 1st Workshop on Formal Verification of Machine Learning, Baltimore, Maryland, USA, colocated with ICML 2022, July 22, 2022
In recent years, a multitude of approaches to certify the prediction of neural networks have been proposed. Classically, complete verification techniques struggle with large networks as the combinatorial space grows exponentially, implying that realistic networks are difficult to be verified. For this reason, we propose to leverage the computational power of quantum computing for the robustness verification of neural networks. Further, we introduce a new Hybrid Quantum-Classical Robustness Algorithm for Neural network verification (HQ-CRAN). By applying Benders decomposition we split the verification problem into a quadratic unconstrained binary optimization and a linear program which we solve with quantum and classical computers, respectively. Further, we 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 provide bounds on the minimum number of qubits necessary to obtain a reasonable approximation. Finally, we evaluate our method on quantum hardware.