Quantum annealing consistently outperformed the Quantum Approximate Optimization Algorithm on problem instances with up to 10 vertices in a benchmarking study of near-term quantum hardware. When applied to the Minimum Vertex Cover problem, the quantum annealing approach demonstrated superior solution quality compared to the gate-based optimization method and in several instances recovered the exact minimum vertex cover. To provide an objective reference point for evaluating solution quality, the experimental study incorporated a classical 2-approximation algorithm as a comparative baseline.
The benchmarking investigation centered on the Minimum Vertex Cover problem, which was mathematically encoded as an Ising Hamiltonian for processing on quantum systems. Researchers designed the experimental framework to evaluate and directly compare two leading quantum optimization paradigms: gate-based quantum computing and quantum annealing. By implementing the problem within the Ising Hamiltonian formulation, the researchers established a uniform structure to examine how differing quantum architectures handle identical combinatorial tasks under near-term hardware constraints.
Empirical trials were executed across two separate quantum computing platforms accessed through cloud infrastructure. For the gate-based quantum computing approach, tests were conducted on the ibm_kingston processor, accessed through the IBM Quantum Platform. In parallel, experiments representing the quantum annealing approach were carried out on the D-Wave Advantage2 quantum annealer, accessed through the D-Wave Leap quantum cloud service, allowing the team to directly compare physical gate-model execution against specialized annealing hardware.
Configuring the Quantum Approximate Optimization Algorithm on the gate-based system required establishing effective variational parameters prior to hardware execution. The researchers selected these variational parameters by running simulations with the Qiskit AerSimulator. To guide this selection, the AerSimulator incorporated device calibration data taken directly from the physical ibm_kingston quantum processor, enabling the team to evaluate variational parameters against the operational characteristics of the target gate-based machine.
Parameter selection for the quantum annealing approach followed a distinct optimization strategy based on simulated annealing. The researchers tested multiple parameter configurations by executing simulated annealing runs with the SimulatedAnnealingSampler from the dwave-samplers software package. By evaluating how different configurations influenced the outcome of simulated annealing, the team retained and deployed those specific parameter settings that yielded the best solution quality during physical runs on the D-Wave Advantage2 hardware.
System outcomes were evaluated across three distinct performance metrics: solution quality, measurement probability, and the proportion of valid solutions generated by each machine. Although quantum annealing maintained a consistent advantage over the Quantum Approximate Optimization Algorithm on smaller graphs with up to 10 vertices, both quantum approaches encountered limitations on larger instances. On larger problem instances, both paradigms displayed reduced stability, produced fewer valid solutions, and exhibited pronounced sensitivity to parameter selections, particularly the penalty term.
Subject of Research: Benchmarking quantum annealing and QAOA on the minimum vertex cover problem
Article Title: Minimum Vertex Cover on Near-Term Quantum Hardware: A Benchmarking Study
Article References: Faro, S., Messina, G., Muzzicato, D., & Viola, C. (2026). Minimum Vertex Cover on Near-Term Quantum Hardware: A Benchmarking Study. International Journal of Networked and Distributed Computing. https://doi.org/10.1007/s44227-026-00131-1
Image Credits: AI Generated
DOI: 10.1007/s44227-026-00131-1
Keywords: minimum vertex cover, quantum annealing, quantum approximate optimization algorithm, QAOA, Ising Hamiltonian, ibm_kingston, D-Wave Advantage2, IBM Quantum Platform, D-Wave Leap, Qiskit AerSimulator, SimulatedAnnealingSampler, dwave-samplers, 2-approximation algorithm, combinatorial optimization, solution quality, measurement probability, penalty term, variational parameters
News Source: Katie Riggs. (November 17, 2026). Quantum Annealing Outperforms QAOA on Small Minimum Vertex Cover Benchmarks. Scienmag.



