Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

The International journal of networked and distributed computing

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

Simone Faro, Gabriele Messina, Damiano Muzzicato, Caterina Viola

Published Nov 11, 2026• 0 citations
Publisher

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 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.

DOI
10.1007/s44227-026-00131-1

Related papers

Evaluating QAOA and Quantum Annealing for Minimum Vertex Cover on NISQ Devices

Simone Faro, Gabriele Messina, Damiano Muzzicato +1 more

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.

ACM International Symposium on High-Performance Parallel and Distributed Computing (HPDC)•Jul 11, 2026•1 citation

Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices

Leo Zhou, Sheng-Tao Wang, Soonwon Choi +2 more

The quantum approximate optimization algorithm (QAOA) is a hybrid quantum-classical variational algorithm designed to tackle combinatorial optimization problems.Despite its promise for near-term quantum applications, not much is currently understood about the QAOA's performance beyond its lowestdepth variant.An essential but missing ingredient for understanding and deploying the QAOA is a constructive approach to carry out the outer-loop classical optimization.We provide an in-depth study of the performance of the QAOA on MaxCut problems by developing an efficient parameter-optimization procedure and revealing its ability to exploit nonadiabatic operations.Building on observed patterns in optimal parameters, we propose heuristic strategies for initializing optimizations to find quasioptimal p-level QAOA parameters in O½polyðpÞ time, whereas the standard strategy of random initialization requires 2 OðpÞ optimization runs to achieve similar performance.We then benchmark the QAOA and compare it with quantum annealing, especially on difficult instances where adiabatic quantum annealing fails due to small spectral gaps.The comparison reveals that the QAOA can learn via optimization to utilize nonadiabatic mechanisms to circumvent the challenges associated with vanishing spectral gaps.Finally, we provide a realistic resource analysis on the experimental implementation of the QAOA.When quantum fluctuations in measurements are accounted for, we illustrate that optimization is important only for problem sizes beyond numerical simulations but accessible on near-term devices.We propose a feasible implementation of large MaxCut problems with a few hundred vertices in a system of 2D neutral atoms, reaching the regime to challenge the best classical algorithms.

arXiv:1812.01041•Physical Review X•Jun 24, 2020•1,132 citations

Degree-conditioned anneal offsets reshape certified-optimum sampling for minimum vertex cover

Jiwan Kang, Namshik Han

Quantum annealers can sample degenerate optima unevenly, so the composition of finite-read output matters when multiple solutions are sought. We investigate whether problem structure can steer this output through node-dependent anneal offsets for Minimum Vertex Cover (MVC). In MVC, vertex degree equals the number of incident edge-cover constraints and therefore measures local constraint participation. We use this relation to define degree-conditioned offset-scheduled quantum annealing (DC-OSQA), a static rule assigning more negative offsets to vertices with larger max-normalized degree. Experiments used a D-Wave Advantage2 system1 quantum processing unit (QPU). For each graph, DC-OSQA was compared with a zero-offset baseline using the same MVC encoding, fixed physical embedding, majority-vote chain decoding, and 1000-read budget. A sampled bitstring was counted as a certified candidate only if it represented a feasible vertex cover and its cardinality matched the minimum independently certified by integer linear programming. Across 120 paired comparisons on sparse Barabasi-Albert graphs with two attachments per added vertex and graph sizes N = 70-150, DC-OSQA increased the mean number of distinct certified candidates from 171.7 to 455.8 and the mean number of complete-linkage Hamming-distance families from 22.5 to 80.0; paired gains were positive at every tested size. These shifts, together with lower empirical concentration, indicate a change in the composition of the observed certified support. At N = 150, the degree-aligned assignment exceeded the within-instance mean over 20 random reassignments of the same offset values in 19 of 20 graphs for certified-support size and all 20 graphs for Hamming families. Within the tested ensemble, these results show that an MVC-specific degree rule changes the certified optima observed within a fixed QPU read budget.

quant-pharXiv:2610.03379•Oct 5, 2026•0 citations

Error Mitigation–Driven Enhancement of QAOA Performance on NISQ Devices

Kondreddy Sathwika, Maka Sri Varshith, Marati Nanda Kumar +1 more

The Quantum Approximate Optimization Algorithm (QAOA) is widely regarded as a promising near-term quantum algorithm for addressing hard combinatorial optimization problems on Noisy Intermediate-Scale Quantum (NISQ) devices; however, its real-world effectiveness is severely constrained by hardware noise, including gate infidelities, decoherence, and measurement errors. This work explores an error mitigation–driven approach to enhance the performance and robustness of QAOA without altering its algorithmic structure or requiring fault-tolerant quantum resources. Measurement error mitigation and zero-noise extrapolation are incorporated into the execution and post-processing stages of QAOA circuits and evaluated using the Minimum Vertex Cover problem as a representative benchmark. Performance is assessed through approximation ratios, solution stability, and noise sensitivity across multiple circuit depths. The results indicate that error mitigation not only improves approximation accuracy but also stabilizes output distributions and delays performance degradation at increased circuit depths. Additionally, the mitigated executions demonstrate better consistency across repeated runs, highlighting improved resilience to stochastic noise. These findings emphasize that lightweight and hardware-efficient error mitigation techniques can significantly extend the practical usability of QAOA on current NISQ hardware, providing a scalable and realistic pathway for executing quantum optimization algorithms more reliably in near-term quantum computing environments.

International Conference on AI-Driven Smart Systems and Ubiquitous Computing (ICAUC)•Jan 19, 2026•0 citations

Quantum Approaches to the Minimum Edge Multiway Cut Problem

Ali Abbassi, Yann Dujardin, Eric Gourdin +2 more

We investigate the minimum edge multiway cut problem, a fundamental task in evaluating the resilience of telecommunication networks. This study benchmarks the problem across three quantum computing paradigms: quantum annealing on a D-Wave quantum processing unit, photonic variational quantum circuits simulated on Quandela s Perceval platform, and IBM s gate-based Quantum Approximate Optimization Algorithm (QAOA). We assess the comparative feasibility of these approaches for early-stage quantum optimization, highlighting trade-offs in circuit constraints, encoding overhead, and scalability. Our findings suggest that quantum annealing currently offers the most scalable performance for this class of problems, while photonic and gate-based approaches remain limited by hardware and simulation depth. These results provide actionable insights for designing quantum workflows targeting combinatorial optimization in telecom security and resilience analysis.

quant-pharXiv:2601.00720•Communications in computer and information science•Jan 5, 2026•4 citations

On the Use of the Quantum Alternating Operator Ansatz in Quantum-Informed Recursive Optimization: A Case Study on the Minimum Vertex Cover

Pablo Ramos-Ruiz, Antonio Miguel Fuentes-Jiménez, José E. Ramos-Ruíz +1 more

In recent years, several quantum algorithms have been proposed for addressing combinatorial optimization problems. Among them, the Quantum Approximate Optimization Algorithm (QAOA) has become a widely used approach. However, reported limitations of QAOA have motivated the development of multiple algorithmic variants, including recursive hybrid methods such as the Recursive Quantum Approximate Optimization Algorithm (RQAOA), as well as the Quantum-Informed Recursive Optimization (QIRO) framework. In this work, we integrate the Quantum Alternating Operator Ansatz within the QIRO framework in order to improve its quantum inference stage. Both the original and the enhanced versions of QIRO are applied to the Minimum Vertex Cover problem, an NP-complete problem of practical relevance. Performance is evaluated on a benchmark of Erdös-Rényi graph instances with varying sizes, densities, and random seeds. The results show that the proposed modification leads to a higher number of successfully solved instances across the considered benchmark, indicating that refinements of the variational layer can improve the effectiveness of the QIRO framework.

AppliedMath•Feb 6, 2026•1 citation
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.
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.
The quantum approximate optimization algorithm (QAOA) is a hybrid quantum-classical variational algorithm designed to tackle combinatorial optimization problems.Despite its promise for near-term quantum applications, not much is currently understood about the QAOA's performance beyond its lowestdepth variant.An essential but missing ingredient for understanding and deploying the QAOA is a constructive approach to carry out the outer-loop classical optimization.We provide an in-depth study of the performance of the QAOA on MaxCut problems by developing an efficient parameter-optimization procedure and revealing its ability to exploit nonadiabatic operations.Building on observed patterns in optimal parameters, we propose heuristic strategies for initializing optimizations to find quasioptimal p-level QAOA parameters in O½polyðpÞ time, whereas the standard strategy of random initialization requires 2 OðpÞ optimization runs to achieve similar performance.We then benchmark the QAOA and compare it with quantum annealing, especially on difficult instances where adiabatic quantum annealing fails due to small spectral gaps.The comparison reveals that the QAOA can learn via optimization to utilize nonadiabatic mechanisms to circumvent the challenges associated with vanishing spectral gaps.Finally, we provide a realistic resource analysis on the experimental implementation of the QAOA.When quantum fluctuations in measurements are accounted for, we illustrate that optimization is important only for problem sizes beyond numerical simulations but accessible on near-term devices.We propose a feasible implementation of large MaxCut problems with a few hundred vertices in a system of 2D neutral atoms, reaching the regime to challenge the best classical algorithms.
Quantum annealers can sample degenerate optima unevenly, so the composition of finite-read output matters when multiple solutions are sought. We investigate whether problem structure can steer this output through node-dependent anneal offsets for Minimum Vertex Cover (MVC). In MVC, vertex degree equals the number of incident edge-cover constraints and therefore measures local constraint participation. We use this relation to define degree-conditioned offset-scheduled quantum annealing (DC-OSQA), a static rule assigning more negative offsets to vertices with larger max-normalized degree. Experiments used a D-Wave Advantage2 system1 quantum processing unit (QPU). For each graph, DC-OSQA was compared with a zero-offset baseline using the same MVC encoding, fixed physical embedding, majority-vote chain decoding, and 1000-read budget. A sampled bitstring was counted as a certified candidate only if it represented a feasible vertex cover and its cardinality matched the minimum independently certified by integer linear programming. Across 120 paired comparisons on sparse Barabasi-Albert graphs with two attachments per added vertex and graph sizes N = 70-150, DC-OSQA increased the mean number of distinct certified candidates from 171.7 to 455.8 and the mean number of complete-linkage Hamming-distance families from 22.5 to 80.0; paired gains were positive at every tested size. These shifts, together with lower empirical concentration, indicate a change in the composition of the observed certified support. At N = 150, the degree-aligned assignment exceeded the within-instance mean over 20 random reassignments of the same offset values in 19 of 20 graphs for certified-support size and all 20 graphs for Hamming families. Within the tested ensemble, these results show that an MVC-specific degree rule changes the certified optima observed within a fixed QPU read budget.
The Quantum Approximate Optimization Algorithm (QAOA) is widely regarded as a promising near-term quantum algorithm for addressing hard combinatorial optimization problems on Noisy Intermediate-Scale Quantum (NISQ) devices; however, its real-world effectiveness is severely constrained by hardware noise, including gate infidelities, decoherence, and measurement errors. This work explores an error mitigation–driven approach to enhance the performance and robustness of QAOA without altering its algorithmic structure or requiring fault-tolerant quantum resources. Measurement error mitigation and zero-noise extrapolation are incorporated into the execution and post-processing stages of QAOA circuits and evaluated using the Minimum Vertex Cover problem as a representative benchmark. Performance is assessed through approximation ratios, solution stability, and noise sensitivity across multiple circuit depths. The results indicate that error mitigation not only improves approximation accuracy but also stabilizes output distributions and delays performance degradation at increased circuit depths. Additionally, the mitigated executions demonstrate better consistency across repeated runs, highlighting improved resilience to stochastic noise. These findings emphasize that lightweight and hardware-efficient error mitigation techniques can significantly extend the practical usability of QAOA on current NISQ hardware, providing a scalable and realistic pathway for executing quantum optimization algorithms more reliably in near-term quantum computing environments.
We investigate the minimum edge multiway cut problem, a fundamental task in evaluating the resilience of telecommunication networks. This study benchmarks the problem across three quantum computing paradigms: quantum annealing on a D-Wave quantum processing unit, photonic variational quantum circuits simulated on Quandela s Perceval platform, and IBM s gate-based Quantum Approximate Optimization Algorithm (QAOA). We assess the comparative feasibility of these approaches for early-stage quantum optimization, highlighting trade-offs in circuit constraints, encoding overhead, and scalability. Our findings suggest that quantum annealing currently offers the most scalable performance for this class of problems, while photonic and gate-based approaches remain limited by hardware and simulation depth. These results provide actionable insights for designing quantum workflows targeting combinatorial optimization in telecom security and resilience analysis.
In recent years, several quantum algorithms have been proposed for addressing combinatorial optimization problems. Among them, the Quantum Approximate Optimization Algorithm (QAOA) has become a widely used approach. However, reported limitations of QAOA have motivated the development of multiple algorithmic variants, including recursive hybrid methods such as the Recursive Quantum Approximate Optimization Algorithm (RQAOA), as well as the Quantum-Informed Recursive Optimization (QIRO) framework. In this work, we integrate the Quantum Alternating Operator Ansatz within the QIRO framework in order to improve its quantum inference stage. Both the original and the enhanced versions of QIRO are applied to the Minimum Vertex Cover problem, an NP-complete problem of practical relevance. Performance is evaluated on a benchmark of Erdös-Rényi graph instances with varying sizes, densities, and random seeds. The results show that the proposed modification leads to a higher number of successfully solved instances across the considered benchmark, indicating that refinements of the variational layer can improve the effectiveness of the QIRO framework.