REVIEW 1 cited by
Solving large Minimum Vertex Cover problems on a quantum annealer
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
Solving large Minimum Vertex Cover problems on a quantum annealer
read the original 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.
Forward citations
Cited by 1 Pith paper
-
Iterative quantum algorithms for the minimum vertex cover problem based on continuous-time quantum walks
A constraint-preserving continuous-time quantum walk on the space of valid vertex covers supplies vertex rankings that improve greedy minimum-vertex-cover heuristics on small random graphs.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.