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

Applied Soft Computing

Applying the quantum approximate optimization algorithm to the minimum vertex cover problem

Yongqiang Zhang, X.D. Mu, Xiaowen Liu, Xingyu Wang, X. Zhang, Kai Li, Tianyi Wu, Dao Zhao, Chen Dong

Published Feb 5, 2022• 46 citations
Publisher
DOI
10.1016/j.asoc.2022.108554

Related papers

Quantum speedup for solving the minimum vertex cover problem based on Grover search algorithm

Zhaocai Wang, Kun Liang, Xiaoguang Bao +1 more

Quantum Information Processing•Jul 1, 2023•8 citations

An improved quantum-inspired evolutionary algorithm framework implemented to solve minimum vertex cover problem

Sulabh Bansal, Shiladitya Bhattacharjee

Structural and Multidisciplinary Optimization•Jul 1, 2025•3 citations

Performance analysis of the quantum alternating operator ansatz for solving the minimum weighted vertex cover problem

Guanghui Li, Shasha Wang, Xiao‐Hui Ni +4 more

Physics Letters A•May 28, 2025•2 citations

Ising Hamiltonians for Constrained Combinatorial Optimization Problems and the Metropolis‐Hastings Warm‐Starting Algorithm

Huimin Li, Jin‐Min Liang, Zhi‐Xi Wang +1 more

Abstract Quantum approximate optimization algorithm (QAOA) is a promising variational quantum algorithm for combinatorial optimization problems. However, the implementation of QAOA is limited due to the requirement that the problems be mapped to Ising Hamiltonians and the nonconvex optimization landscapes. Although the Ising Hamiltonians for many NP hard problems have been obtained, a general method to obtain the Ising Hamiltonians for constrained combinatorial optimization problems (CCOPs) has not yet been investigated. In this paper, a general method is introduced to obtain the Ising Hamiltonians for CCOPs and the Metropolis‐Hastings warm‐starting algorithm for QAOA is presented which can provably converge to the global optimal solutions. The effectiveness of this method is demonstrated by tackling the minimum weight vertex cover (MWVC) problem, the minimum vertex cover (MVC) problem, and the maximal independent set problem as examples. The Ising Hamiltonian for the MWVC problem is obtained first time by using this method. The advantages of the Metropolis‐Hastings warm‐starting algorithm presented here is numerically analyzed through solving 30 randomly generated MVC cases with 1‐depth QAOA.

arXiv:2307.08980•Advanced Quantum Technologies•Jul 16, 2023•5 citations

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

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

The International journal of networked and distributed computing•Nov 11, 2026•0 citations

The Quantum Approximate Optimization Algorithm

Stefan Isermann

•Jan 1, 2022•0 citations
Abstract Quantum approximate optimization algorithm (QAOA) is a promising variational quantum algorithm for combinatorial optimization problems. However, the implementation of QAOA is limited due to the requirement that the problems be mapped to Ising Hamiltonians and the nonconvex optimization landscapes. Although the Ising Hamiltonians for many NP hard problems have been obtained, a general method to obtain the Ising Hamiltonians for constrained combinatorial optimization problems (CCOPs) has not yet been investigated. In this paper, a general method is introduced to obtain the Ising Hamiltonians for CCOPs and the Metropolis‐Hastings warm‐starting algorithm for QAOA is presented which can provably converge to the global optimal solutions. The effectiveness of this method is demonstrated by tackling the minimum weight vertex cover (MWVC) problem, the minimum vertex cover (MVC) problem, and the maximal independent set problem as examples. The Ising Hamiltonian for the MWVC problem is obtained first time by using this method. The advantages of the Metropolis‐Hastings warm‐starting algorithm presented here is numerically analyzed through solving 30 randomly generated MVC cases with 1‐depth QAOA.
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.