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.In this paper, we propose a new hybrid approach to the robustness verification of ReLU networks with quantum computers.By applying Benders decomposition, the verification problem is split into a quadratic unconstrained binary optimization and a linear program which are solved by 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.