Minimum Vertex Cover on Near-Term Quantum Hardware: A Benchmarking Study

We investigate and compare the performance of two quantum optimization approaches, the Quantum Approximate Optimization Algorithm (QAOA) and quantum annealing, applied to the Minimum Vertex Cover ( MVC ) problem. The problem is encoded as an Ising Hamiltonian, and experiments are conducted on the ibm_kingston gate-based quantum machine, accessed via the IBM Quantum Platform , and on the D-Wave Advantage2 quantum annealer, accessed via the D-Wave Leap quantum cloud service. A classical 2-approximation algorithm is included as a reference baseline. The variational parameters used in the QAOA implementation are selected using the Qiskit AerSimulator with calibration data from the ibm_kingston quantum processor. For quantum annealing, the parameters are determined testing multiple configurations of simulated annealing performed with the SimulatedAnnealingSampler of the dwave-samplers package, and retaining those yielding the best solution quality. Performance is evaluated in terms of solution quality, measurement probability, and proportion of valid solutions. Our results show that, within our experimental setting, quantum annealing consistently outperforms QAOA on instances with up to 10 vertices, and in some cases recovers the exact minimum vertex cover, while the classical 2-approximation baseline serves as a reference point for solution quality. On larger instances, both paradigms exhibit reduced stability and yield fewer valid solutions, with performance becoming increasingly sensitive to parameter choices such as the penalty term.