Home > Research > Publications & Outputs > Solving large Minimum Vertex Cover problems on ...

Research

Links

Keywords

View graph of relations

Solving large Minimum Vertex Cover problems on a quantum annealer

Research output: Contribution to Journal/Magazine › Journal article

Published

Standard

Solving large Minimum Vertex Cover problems on a quantum annealer. / Pelofske, Elijah; Hahn, Georg; Djidjev, Hristo N.
In: arxiv.org, 29.03.2019.

Research output: Contribution to Journal/Magazine › Journal article

Harvard

Pelofske, E, Hahn, G & Djidjev, HN 2019, 'Solving large Minimum Vertex Cover problems on a quantum annealer', arxiv.org. <https://arxiv.org/abs/1904.00051>

APA

Pelofske, E., Hahn, G., & Djidjev, H. N. (2019). Solving large Minimum Vertex Cover problems on a quantum annealer. arxiv.org. https://arxiv.org/abs/1904.00051

Vancouver

Pelofske E, Hahn G, Djidjev HN. Solving large Minimum Vertex Cover problems on a quantum annealer. arxiv.org. 2019 Mar 29.

Author

Pelofske, Elijah ; Hahn, Georg ; Djidjev, Hristo N. / Solving large Minimum Vertex Cover problems on a quantum annealer. In: arxiv.org. 2019.

Bibtex

@article{010efb0d23cc4882bae06367c37f9f0b,
title = "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. ",
keywords = "quant-ph, cs.DS",
author = "Elijah Pelofske and Georg Hahn and Djidjev, {Hristo N.}",
year = "2019",
month = mar,
day = "29",
language = "English",
journal = "arxiv.org",

}

RIS

TY - JOUR

T1 - Solving large Minimum Vertex Cover problems on a quantum annealer

AU - Pelofske, Elijah

AU - Hahn, Georg

AU - Djidjev, Hristo N.

PY - 2019/3/29

Y1 - 2019/3/29

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

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

KW - quant-ph

KW - cs.DS

M3 - Journal article

JO - arxiv.org

JF - arxiv.org

ER -