Home > Research > Publications & Outputs > Finding Maximum Cliques on a Quantum Annealer

Research

Associated organisational unit

Electronic data

  • paper

    Rights statement: © ACM, 2017. This is the author's version of the work. It is posted here for your personal use. Not for redistribution. The definitive Version of Record was published in CF'17 Proceedings of the Computing Frontiers Conference http://dx.doi.org/10.1145/3075564.3075575

    Accepted author manuscript, 397 KB, PDF document

    Available under license: CC BY-NC: Creative Commons Attribution-NonCommercial 4.0 International License

Links

Text available via DOI:

Keywords

View graph of relations

Finding Maximum Cliques on a Quantum Annealer

Research output: Contribution in Book/Report/Proceedings - With ISBN/ISSN › Conference contribution/Paper › peer-review

Published

Standard

Finding Maximum Cliques on a Quantum Annealer. / Chapuis, Guillaume; Djidjev, Hristo; Hahn, Georg et al.
CF'17 Proceedings of the Computing Frontiers Conference. New York: Association for Computing Machinery, Inc, 2017. p. 63-70.

Research output: Contribution in Book/Report/Proceedings - With ISBN/ISSN › Conference contribution/Paper › peer-review

Harvard

Chapuis, G, Djidjev, H, Hahn, G & Rizk, G 2017, Finding Maximum Cliques on a Quantum Annealer. in CF'17 Proceedings of the Computing Frontiers Conference. Association for Computing Machinery, Inc, New York, pp. 63-70, 14th ACM International Conference on Computing Frontiers, CF 2017, Siena, Italy, 15/05/17. https://doi.org/10.1145/3075564.3075575

APA

Chapuis, G., Djidjev, H., Hahn, G., & Rizk, G. (2017). Finding Maximum Cliques on a Quantum Annealer. In CF'17 Proceedings of the Computing Frontiers Conference (pp. 63-70). Association for Computing Machinery, Inc. https://doi.org/10.1145/3075564.3075575

Vancouver

Chapuis G, Djidjev H, Hahn G, Rizk G. Finding Maximum Cliques on a Quantum Annealer. In CF'17 Proceedings of the Computing Frontiers Conference. New York: Association for Computing Machinery, Inc. 2017. p. 63-70 doi: 10.1145/3075564.3075575

Author

Chapuis, Guillaume ; Djidjev, Hristo ; Hahn, Georg et al. / Finding Maximum Cliques on a Quantum Annealer. CF'17 Proceedings of the Computing Frontiers Conference. New York : Association for Computing Machinery, Inc, 2017. pp. 63-70

Bibtex

@inproceedings{3f2e45f8fe6d4ae98af2e7afaedfc635,
title = "Finding Maximum Cliques on a Quantum Annealer",
abstract = "This paper assesses the performance of the D-Wave 2X (DW) quantum annealer for finding a maximum clique in a graph, one of the most fundamental and important NP-hard problems. Because the size of the largest graphs DW can directly solve is quite small (usually around 45 vertices), we also consider decomposition algorithms intended for larger graphs and analyze their performance. For smaller graphs that fit DW, we provide formulations of the maximum clique problem as a quadratic unconstrained binary optimization (QUBO) problem, which is one of the two input types (together with the Ising model) acceptable by the machine, and compare several quantum implementations to current classical algorithms such as simulated annealing, Gurobi, and third-party clique finding heuristics. We further estimate the contributions of the quantum phase of the quantum annealer and the classical post-processing phase typically used to enhance each solution returned by DW. We demonstrate that on random graphs that fit DW, no quantum speedup can be observed compared with the classical algorithms. On the other hand, for instances specifically designed to fit well the DW qubit interconnection network, we observe substantial speed-ups in computing time over classical approaches.",
keywords = "D-Wave 2X, Gurobi, Maximum clique, Optimization, Quantum annealing",
author = "Guillaume Chapuis and Hristo Djidjev and Georg Hahn and Guillaume Rizk",
note = "{\textcopyright} ACM, 2017. This is the author's version of the work. It is posted here for your personal use. Not for redistribution. The definitive Version of Record was published in CF'17 Proceedings of the Computing Frontiers Conference http://dx.doi.org/10.1145/3075564.3075575; 14th ACM International Conference on Computing Frontiers, CF 2017 ; Conference date: 15-05-2017 Through 17-05-2017",
year = "2017",
month = may,
day = "15",
doi = "10.1145/3075564.3075575",
language = "English",
pages = "63--70",
booktitle = "CF'17 Proceedings of the Computing Frontiers Conference",
publisher = "Association for Computing Machinery, Inc",

}

RIS

TY - GEN

T1 - Finding Maximum Cliques on a Quantum Annealer

AU - Chapuis, Guillaume

AU - Djidjev, Hristo

AU - Hahn, Georg

AU - Rizk, Guillaume

N1 - © ACM, 2017. This is the author's version of the work. It is posted here for your personal use. Not for redistribution. The definitive Version of Record was published in CF'17 Proceedings of the Computing Frontiers Conference http://dx.doi.org/10.1145/3075564.3075575

PY - 2017/5/15

Y1 - 2017/5/15

N2 - This paper assesses the performance of the D-Wave 2X (DW) quantum annealer for finding a maximum clique in a graph, one of the most fundamental and important NP-hard problems. Because the size of the largest graphs DW can directly solve is quite small (usually around 45 vertices), we also consider decomposition algorithms intended for larger graphs and analyze their performance. For smaller graphs that fit DW, we provide formulations of the maximum clique problem as a quadratic unconstrained binary optimization (QUBO) problem, which is one of the two input types (together with the Ising model) acceptable by the machine, and compare several quantum implementations to current classical algorithms such as simulated annealing, Gurobi, and third-party clique finding heuristics. We further estimate the contributions of the quantum phase of the quantum annealer and the classical post-processing phase typically used to enhance each solution returned by DW. We demonstrate that on random graphs that fit DW, no quantum speedup can be observed compared with the classical algorithms. On the other hand, for instances specifically designed to fit well the DW qubit interconnection network, we observe substantial speed-ups in computing time over classical approaches.

AB - This paper assesses the performance of the D-Wave 2X (DW) quantum annealer for finding a maximum clique in a graph, one of the most fundamental and important NP-hard problems. Because the size of the largest graphs DW can directly solve is quite small (usually around 45 vertices), we also consider decomposition algorithms intended for larger graphs and analyze their performance. For smaller graphs that fit DW, we provide formulations of the maximum clique problem as a quadratic unconstrained binary optimization (QUBO) problem, which is one of the two input types (together with the Ising model) acceptable by the machine, and compare several quantum implementations to current classical algorithms such as simulated annealing, Gurobi, and third-party clique finding heuristics. We further estimate the contributions of the quantum phase of the quantum annealer and the classical post-processing phase typically used to enhance each solution returned by DW. We demonstrate that on random graphs that fit DW, no quantum speedup can be observed compared with the classical algorithms. On the other hand, for instances specifically designed to fit well the DW qubit interconnection network, we observe substantial speed-ups in computing time over classical approaches.

KW - D-Wave 2X

KW - Gurobi

KW - Maximum clique

KW - Optimization

KW - Quantum annealing

U2 - 10.1145/3075564.3075575

DO - 10.1145/3075564.3075575

M3 - Conference contribution/Paper

AN - SCOPUS:85027002240

SP - 63

EP - 70

BT - CF'17 Proceedings of the Computing Frontiers Conference

PB - Association for Computing Machinery, Inc

CY - New York

T2 - 14th ACM International Conference on Computing Frontiers, CF 2017

Y2 - 15 May 2017 through 17 May 2017

ER -