Evaluating QAOA and Quantum Annealing for Minimum Vertex Cover on NISQ Devices
TL;DR
Investigation 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 suggest that while both paradigms hold potential for combinatorial optimization, further advances in hardware capabilities and parameter calibration will be necessary to achieve reliable performance on larger instances.
Abstract
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 and Ising model, and experiments are conducted on IBM’s GenericBackendV2 noisy superconducting qubit simulator and the D-Wave Advantage2 quantum annealer. Performance is evaluated in terms of solution quality, measurement probability, and proportion of valid solutions. The results we obtained show that, within our experimental setting, quantum annealing consistently outperforms its classical counterpart on small instances, while QAOA, though currently limited by simulation constraints, shows promising behavior that improves with increasing circuit depth. As problem size grows, both approaches exhibit sensitivity to parameter choices such as the penalty term and graph density, underscoring the need for careful tuning. These findings suggest that while both paradigms hold potential for combinatorial optimization, further advances in hardware capabilities and parameter calibration will be necessary to achieve reliable performance on larger instances.