{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,3]],"date-time":"2026-10-03T02:21:57Z","timestamp":1790994117893,"version":"4.1.0"},"reference-count":24,"publisher":"MDPI AG","issue":"6","license":[{"start":{"date-parts":[[2021,6,21]],"date-time":"2021-06-21T00:00:00Z","timestamp":1624233600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>Quantum annealers, such as the device built by D-Wave Systems, Inc., offer a way to compute solutions of NP-hard problems that can be expressed in Ising or quadratic unconstrained binary optimization (QUBO) form. Although such solutions are typically of very high quality, problem instances are usually not solved to optimality due to imperfections of the current generations quantum annealers. In this contribution, we aim to understand some of the factors contributing to the hardness of a problem instance, and to use machine learning models to predict the accuracy of the D-Wave 2000Q annealer for solving specific problems. We focus on the maximum clique problem, a classic NP-hard problem with important applications in network analysis, bioinformatics, and computational chemistry. By training a machine learning classification model on basic problem characteristics such as the number of edges in the graph, or annealing parameters, such as the D-Wave\u2019s chain strength, we are able to rank certain features in the order of their contribution to the solution hardness, and present a simple decision tree which allows to predict whether a problem will be solvable to optimality with the D-Wave 2000Q. We extend these results by training a machine learning regression model that predicts the clique size found by D-Wave.<\/jats:p>","DOI":"10.3390\/a14060187","type":"journal-article","created":{"date-parts":[[2021,6,21]],"date-time":"2021-06-21T04:21:21Z","timestamp":1624249281000},"page":"187","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["Using Machine Learning for Quantum Annealing Accuracy Prediction"],"prefix":"10.3390","volume":"14","author":[{"given":"Aaron","family":"Barbosa","sequence":"first","affiliation":[{"name":"CCS-3 Information Sciences, Los Alamos National Laboratory, Los Alamos, NM 87545, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Elijah","family":"Pelofske","sequence":"additional","affiliation":[{"name":"CCS-3 Information Sciences, Los Alamos National Laboratory, Los Alamos, NM 87545, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6008-2720","authenticated-orcid":false,"given":"Georg","family":"Hahn","sequence":"additional","affiliation":[{"name":"T.H. Chan School of Public Health, Harvard University, Boston, MA 02115, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9286-8824","authenticated-orcid":false,"given":"Hristo N.","family":"Djidjev","sequence":"additional","affiliation":[{"name":"CCS-3 Information Sciences, Los Alamos National Laboratory, Los Alamos, NM 87545, USA"},{"name":"Institute of Information and Communication Technologies, Bulgarian Academy of Sciences, 1113 Sofia, Bulgaria"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"1968","published-online":{"date-parts":[[2021,6,21]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1007\/s11265-018-1357-8","article-title":"Finding Maximum Cliques on the D-Wave Quantum Annealer","volume":"91","author":"Chapuis","year":"2019","journal-title":"J. Signal Process. Syst."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.3389\/fphy.2014.00005","article-title":"Ising formulations of many NP problems","volume":"2","author":"Lucas","year":"2014","journal-title":"Front. Phys."},{"key":"ref_3","first-page":"2825","article-title":"Scikit-learn: Machine Learning in Python","volume":"12","author":"Pedregosa","year":"2011","journal-title":"J. Mach. Learn. Res."},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Pelofske, E., Hahn, G., and Djidjev, H. (2019). Solving large Maximum Clique problems on a quantum annealer. International Workshop on Quantum Technology and Optimization Problems, Springer.","DOI":"10.1145\/3310273.3321562"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"113022","DOI":"10.1088\/1367-2630\/aae94a","article-title":"Learning the quantum algorithm for state overlap","volume":"20","author":"Cincio","year":"2018","journal-title":"New J. Phys."},{"key":"ref_6","unstructured":"Verdon, G., Broughton, M., McClean, J.R., Sung, K.J., Babbush, R., Jiang, Z., Neven, H., and Mohseni, M. (2019). Learning to learn with quantum neural networks via classical neural networks. arXiv."},{"key":"ref_7","unstructured":"F\u00f6sel, T., Niu, M.Y., Marquardt, F., and Li, L. (2021). Quantum circuit optimization with deep reinforcement learning. arXiv."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"200501","DOI":"10.1103\/PhysRevLett.114.200501","article-title":"Machine Learning for Discriminating Quantum Measurement Trajectories and Improving Readout","volume":"114","author":"Magesan","year":"2015","journal-title":"Phys. Rev. Lett."},{"key":"ref_9","unstructured":"Rivera-Dean, J., Huembeli, P., Ac\u00edn, A., and Bowles, J. (2021). Avoiding local minima in Variational Quantum Algorithms with Neural Networks. arXiv."},{"key":"ref_10","unstructured":"Farhi, E., Goldstone, J., Gutmann, S., and Neven, H. (2017). Quantum Algorithms for Fixed Qubit Architectures. arXiv."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"033446","DOI":"10.1103\/PhysRevResearch.2.033446","article-title":"Reinforcement-learning-assisted quantum optimization","volume":"2","author":"Wauters","year":"2020","journal-title":"Phys. Rev. Res."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"044009","DOI":"10.1088\/2058-9565\/abb8e5","article-title":"To quantum or not to quantum: Towards algorithm selection in near-term quantum optimization","volume":"5","author":"Moussa","year":"2020","journal-title":"Quantum Sci. Technol."},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Pelofske, E., Hahn, G., and Djidjev, H. (2019, January 4\u20138). Optimizing the Spin Reversal Transform on the D-Wave 2000Q. Proceedings of the 2019 IEEE International Conference on Rebooting Computing (ICRC), San Mateo, CA, USA.","DOI":"10.1109\/ICRC.2019.8914719"},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Barbosa, A., Pelofske, E., Hahn, G., and Djidjev, H. (2020). Optimizing embedding-related quantum annealing parameters for reducing hardware bias. arXiv.","DOI":"10.1007\/978-981-16-0010-4_15"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1007\/BF02392825","article-title":"Clique is hard to approximate within n1\u2212\u03b5","volume":"182","year":"1999","journal-title":"Acta Math."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"1346","DOI":"10.1016\/j.jcss.2006.04.007","article-title":"Strong computational lower bounds via parameterized complexity","volume":"72","author":"Chen","year":"2006","journal-title":"J. Comput. Syst. Sci."},{"key":"ref_17","unstructured":"D-Wave Systems (2021, May 15). D-Wave Ocearn: Minorminer. Available online: https:\/\/docs.ocean.dwavesys.com\/projects\/minorminer\/en\/latest\/."},{"key":"ref_18","unstructured":"D-Wave Systems (2021, May 15). D-Wave System Documentation: Uniform Torque Compensation. Available online: https:\/\/docs.ocean.dwavesys.com\/projects\/system\/en\/stable\/reference\/generated\/dwave.embedding.chain_strength.uniform_torque_compensation.html."},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Hagberg, A.A., Schult, D.A., and Swart, P.J. (2008, January 19\u201324). Exploring Network Structure, Dynamics, and Function using NetworkX. Proceedings of the 7th Python in Science Conference, Pasadena, CA, USA.","DOI":"10.25080\/TCWV9851"},{"key":"ref_20","unstructured":"NetworkX (2021, May 15). Return the Clique Number (Size of the Largest Clique) for a Graph. Available online: https:\/\/networkx.org\/documentation\/networkx-1.10\/reference\/generated\/networkx.algorithms.clique.graph_clique_number.html."},{"key":"ref_21","unstructured":"Scikit Learn (2021, May 15). Gradient Boosting for Regression. Available online: https:\/\/scikit-learn.org\/stable\/modules\/generated\/sklearn.ensemble.GradientBoostingRegressor.html."},{"key":"ref_22","first-page":"449","article-title":"The second largest eigenvalue of a graph (a survey)","volume":"9","year":"1995","journal-title":"Filomat"},{"key":"ref_23","unstructured":"Lov\u00e1sz, L. (2021, May 15). Eigenvalues of Graphs. Available online: https:\/\/web.cs.elte.hu\/~lovasz\/eigenvals-x.pdf."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1023\/A:1010933404324","article-title":"Random Forests","volume":"45","author":"Breiman","year":"2001","journal-title":"Mach. Learn."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/6\/187\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T06:19:54Z","timestamp":1760163594000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/6\/187"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,21]]},"references-count":24,"journal-issue":{"issue":"6","published-online":{"date-parts":[[2021,6]]}},"alternative-id":["a14060187"],"URL":"https:\/\/doi.org\/10.3390\/a14060187","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,6,21]]}}}