  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 a 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 provide bounds on the
minimum number of qubits necessary to approximate the problem. Finally, we
evaluate our method within simulation and on quantum hardware.
