Solving large Minimum Vertex Cover problems on a quantum annealer

Abstract

We consider the minimum vertex cover problem having applications in e.g. biochemistry and network security. Quantum annealers can find the optimum solution of such NP-hard problems, given they can be embedded on the hardware. This is often infeasible due to limitations of the hardware connectivity structure. This paper presents a decomposition algorithm for the minimum vertex cover problem: The algorithm recursively divides an arbitrary problem until the generated subproblems can be embedded and solved on the annealer. To speed up the decomposition, we propose several pruning and reduction techniques. The performance of our algorithm is assessed in a simulation study.

References in corpus (5)

• Finding community structure in networks using the eigenvectors of matrices
• Solving large Maximum Clique problems on a quantum annealer
• Efficient Combinatorial Optimization Using Quantum Annealing
• Fast Algorithms for the Maximum Clique Problem on Massive Sparse Graphs
• What if CLIQUE were fast? Maximum Cliques in Information Networks and Strong Components in Temporal Networks

Cited by in corpus (10)

• Solving Larger Maximum Clique Problems Using Parallel Quantum Annealing
• Optimizing the spin reversal transform on the D-Wave 2000Q
• Decomposition algorithms for solving NP-hard problems on a quantum annealer
• Quantum Annealing Algorithms for Boolean Tensor Networks
• Advanced unembedding techniques for quantum annealers
• Incentivising Demand Side Response through Discount Scheduling using Hybrid Quantum Optimization
• Quantum-Assisted Support Vector Regression
• Peering into the Anneal Process of a Quantum Annealer
• Inferring the Dynamics of the State Evolution During Quantum Annealing
• Using machine learning for quantum annealing accuracy prediction