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

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:

View graph of relations

Finding Maximum Cliques on a Quantum Annealer

Research output: Contribution in Book/Report/Proceedings - With ISBN/ISSNConference contribution/Paperpeer-review

Published
  • Guillaume Chapuis
  • Hristo Djidjev
  • Georg Hahn
  • Guillaume Rizk
Close
Publication date15/05/2017
Host publicationCF'17 Proceedings of the Computing Frontiers Conference
Place of PublicationNew York
PublisherAssociation for Computing Machinery, Inc
Pages63-70
Number of pages8
ISBN (electronic)9781450344876
<mark>Original language</mark>English
Event14th ACM International Conference on Computing Frontiers, CF 2017 - Siena, Italy
Duration: 15/05/201717/05/2017

Conference

Conference14th ACM International Conference on Computing Frontiers, CF 2017
Country/TerritoryItaly
CitySiena
Period15/05/1717/05/17

Conference

Conference14th ACM International Conference on Computing Frontiers, CF 2017
Country/TerritoryItaly
CitySiena
Period15/05/1717/05/17

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.

Bibliographic note

© 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