Solving Large Maximum Clique Problems on a Quantum Annealer
Open accessThe DOI matches its Crossref record; 5 of the 5 references it cites were found in a registry or an index.
Abstract
Commercial quantum annealers from D-Wave Systems can find high quality solutions of quadratic unconstrained binary optimization problems that can be embedded onto its hardware. However, even though such devices currently offer up to 2048 qubits, due to limitations on the connectivity of those qubits, the size of problems that can typically be solved is rather small (around 65 variables). This limitation poses a problem for using D-Wave machines to solve application-relevant problems, which can have thousands of variables. For the important Maximum Clique problem, this article investigates methods for decomposing larger problem instances into smaller ones, which can subsequently be solved on D-Wave. During the decomposition, we aim to prune as many generated subproblems that don’t contribute to the solution as possible, in order to reduce the computational complexity. The reduction methods presented in this article include upper and lower bound heuristics in conjunction with graph decomposition, vertex and edge extraction, and persistency analysis.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Exploring Network Structure, Dynamics, and Function Using NetworkX
Hagberg, A. A., Schult, D. A., & Swart, P. J. (2008) · Proceedings of the Python in Science Conference · doi:10.25080/tcwv9851 · Cited by 7,477 · cited 2×
“In the simulations of section 4, we use two greedy algorithms: the greedy coloring algorithm greedy color of the python module Networkx (Hagberg et al., 2008) as well as the upper bound algorithm of (Budinich, 2003, eq.”
MethodIsing formulations of many NP problems
Lucas, A. (2014) · Frontiers in Physics · doi:10.3389/fphy.2014.00005 · Cited by 2,512
On the evolution of random graphs
Erdös, P., & Rényi, A. (2011) · The Structure and Dynamics of Networks · doi:10.1515/9781400841356.38 · Cited by 1,757
Boros, E., & Hammer, P. L. (2002) · Discrete Applied Mathematics · doi:10.1016/s0166-218x(01)00341-9 · Cited by 827
A deceptive step towards quantum speedup detection
Mandrà, S., & Katzgraber, H. G. (2018) · Quantum Science and Technology · doi:10.1088/2058-9565/aac8b2 · Cited by 82 · cited 1×
“The Time-To-Solution (TTS) measure is defined in (Mandrà and Katzgraber, 2018, eq.”
Method
Cited by
Quantum Bridge Analytics I: a tutorial on formulating and using QUBO models
Glover, F., Kochenberger, G., & Du, Y. (2019) · 4OR · doi:10.1007/s10288-019-00424-y · Cited by 298
Hybrid Annealing Method Based on subQUBO Model Extraction With Multiple Solution Instances
Atobe, Y., Tawada, M., & Togawa, N. (2022) · IEEE Transactions on Computers · doi:10.1109/tc.2021.3138629 · Cited by 38
“Note that several studies proposed subQUBO model extraction methods for specific problems, such as the maximum-clique problem in [24], [25], [26], the constraint satisfaction problem in [27], and the maximum constraint satisfaction problem in [28].”
BackgroundOptimizing the Spin Reversal Transform on the D-Wave 2000Q
Pelofske, E., Hahn, G., & Djidjev, H. (2019) · 2019 IEEE International Conference on Rebooting Computing (ICRC) · doi:10.1109/icrc.2019.8914719 · Cited by 26
“The reason for using |V | = 64 vertices stems from the fact that this is the largest size of an arbitrary graph that can be embedded onto D-Wave 2000Q, see [8], [9].”
BackgroundSelf-citationQuantum Combinatorial Optimization in the NISQ Era: A Systematic Mapping Study
Gemeinhardt, F., Garmendia, A., Wimmer, M., Weder, B., & Leymann, F. (2024) · ACM Computing Surveys · doi:10.1145/3620668 · Cited by 22
“Further problem-specific decomposition methods have been proposed for the item listing problem [102] and the Max-Clique problem [110].”
MethodNoise dynamics of quantum annealers: estimating the effective noise using idle qubits
Pelofske, E., Hahn, G., & Djidjev, H. N. (2023) · Quantum Science and Technology · doi:10.1088/2058-9565/accbe6 · Cited by 12
Self-citation
Metadata
- Authors
- Pelofske, E., Hahn, G., & Djidjev, H.
- Venue
- Lecture Notes in Computer Science
- Publisher
- Springer International Publishing
- Published
- 2019
- Pages
- 123-135
- ISSN
- 0302-9743 (ISSN-L)
- 1611-3349
- OpenAlex
- W2914574155
- Cited by
- 38
- References
- 5
- FWCI
- 2.10
- Type
- conference paper
- Language
- en
- Open access
- green
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Solving Large Maximum Clique Problems on a Quantum Annealer. https://app.cochat.ai/papers/10.1007/978-3-030-14082-3_11
- The paper
- Pelofske, E., Hahn, G., & Djidjev, H. (2019). Solving Large Maximum Clique Problems on a Quantum Annealer. Lecture Notes in Computer Science. https://doi.org/10.1007/978-3-030-14082-3_11
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.