{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,16]],"date-time":"2026-04-16T10:38:03Z","timestamp":1776335883776,"version":"3.51.2"},"reference-count":86,"publisher":"Springer Science and Business Media LLC","issue":"5-6","license":[{"start":{"date-parts":[[2024,8,2]],"date-time":"2024-08-02T00:00:00Z","timestamp":1722556800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,8,2]],"date-time":"2024-08-02T00:00:00Z","timestamp":1722556800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100008902","name":"Los Alamos National Laboratory","doi-asserted-by":"publisher","award":["20210114ER"],"award-info":[{"award-number":["20210114ER"]}],"id":[{"id":"10.13039\/100008902","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["2037755"],"award-info":[{"award-number":["2037755"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Heuristics"],"published-print":{"date-parts":[[2024,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Over the past decade, the usefulness of quantum annealing hardware for combinatorial optimization has been the subject of much debate. Thus far, experimental benchmarking studies have indicated that quantum annealing hardware does not provide an irrefutable performance gain over state-of-the-art optimization methods. However, as this hardware continues to evolve, each new iteration brings improved performance and warrants further benchmarking. To that end, this work conducts an optimization performance assessment of D-Wave Systems\u2019 <jats:italic>Advantage Performance Update<\/jats:italic> computer, which can natively solve sparse unconstrained quadratic optimization problems with over 5,000 binary decision variables and 40,000 quadratic terms. We demonstrate that classes of contrived problems exist where this quantum annealer can provide run time benefits over a collection of established classical solution methods that represent the current state-of-the-art for benchmarking quantum annealing hardware. Although this work <jats:italic>does not<\/jats:italic> present strong evidence of an irrefutable performance benefit for this emerging optimization technology, it does exhibit encouraging progress, signaling the potential impacts on practical optimization tasks in the future.<\/jats:p>","DOI":"10.1007\/s10732-024-09530-5","type":"journal-article","created":{"date-parts":[[2024,8,2]],"date-time":"2024-08-02T20:32:24Z","timestamp":1722630744000},"page":"325-358","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":32,"title":["On the emerging potential of quantum annealing hardware for combinatorial optimization"],"prefix":"10.1007","volume":"30","author":[{"given":"Byron","family":"Tasseff","sequence":"first","affiliation":[]},{"given":"Tameem","family":"Albash","sequence":"additional","affiliation":[]},{"given":"Zachary","family":"Morrell","sequence":"additional","affiliation":[]},{"given":"Marc","family":"Vuffray","sequence":"additional","affiliation":[]},{"given":"Andrey Y.","family":"Lokhov","sequence":"additional","affiliation":[]},{"given":"Sidhant","family":"Misra","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3238-1699","authenticated-orcid":false,"given":"Carleton","family":"Coffrin","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,8,2]]},"reference":[{"key":"9530_CR1","unstructured":"Aaronson, S. (2017). Insert D-Wave post here. https:\/\/web.archive.org\/web\/20220305233421, Accessed 08 April 2022"},{"key":"9530_CR2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevX.8.031016","volume":"8","author":"T Albash","year":"2018","unstructured":"Albash, T., Lidar, D.A.: Demonstration of a scaling advantage for a quantum annealer over simulated annealing. Phys. Rev. X 8, 031016 (2018). https:\/\/doi.org\/10.1103\/PhysRevX.8.031016","journal-title":"Phys. Rev. X"},{"key":"9530_CR3","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.91.042314","volume":"91","author":"T Albash","year":"2015","unstructured":"Albash, T., Vinci, W., Mishra, A., et al.: Consistency tests of classical and quantum models for a quantum annealer. Phys. Rev. A 91, 042314 (2015). https:\/\/doi.org\/10.1103\/PhysRevA.91.042314","journal-title":"Phys. Rev. A"},{"key":"9530_CR4","doi-asserted-by":"publisher","DOI":"10.1103\/physrevresearch.2.043163","author":"F Baccari","year":"2020","unstructured":"Baccari, F., Gogolin, C., Wittek, P., et al.: Verifying the output of quantum optimizers with ground-state energy lower bounds. Rev. Res. Phys. (2020). https:\/\/doi.org\/10.1103\/physrevresearch.2.043163","journal-title":"Rev. Res. Phys."},{"key":"9530_CR5","unstructured":"Beasley, J.E.: Heuristic algorithms for the unconstrained binary quadratic programming problem. Tech. rep, Management School, Imperial College (1998)"},{"issue":"10","key":"9530_CR6","doi-asserted-by":"publisher","DOI":"10.1088\/0953-2048\/23\/10\/105014","volume":"23","author":"AJ Berkley","year":"2010","unstructured":"Berkley, A.J., Johnson, M.W., Bunyk, P., et al.: A scalable readout system for a superconducting adiabatic quantum optimization system. Superconduct. Sci. Technol. 23(10), 105014 (2010). https:\/\/doi.org\/10.1088\/0953-2048\/23\/10\/105014","journal-title":"Superconduct. Sci. Technol."},{"issue":"1","key":"9530_CR7","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1007\/s10107-005-0637-9","volume":"109","author":"A Billionnet","year":"2007","unstructured":"Billionnet, A., Elloumi, S.: Using a mixed integer quadratic programming solver for the unconstrained quadratic 0\u20131 problem. Math. Programm. 109(1), 55\u201368 (2007). https:\/\/doi.org\/10.1007\/s10107-005-0637-9","journal-title":"Math. Programm."},{"issue":"3","key":"9530_CR8","doi-asserted-by":"publisher","first-page":"218","DOI":"10.1038\/nphys2900","volume":"10","author":"S Boixo","year":"2014","unstructured":"Boixo, S., R\u00f8nnow, T.F., Isakov, S.V., et al.: Evidence for quantum annealing with more than one hundred qubits. Nat. Phys. 10(3), 218\u2013224 (2014). https:\/\/doi.org\/10.1038\/nphys2900","journal-title":"Nat. Phys."},{"key":"9530_CR9","doi-asserted-by":"publisher","unstructured":"Boothby, K., Bunyk, P., Raymond, J., et al.: Next-generation topology of D-Wave quantum processors. (2020). https:\/\/doi.org\/10.48550\/arXiv.2003.00133","DOI":"10.48550\/arXiv.2003.00133"},{"issue":"3","key":"9530_CR10","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1007\/BF01343193","volume":"51","author":"M Born","year":"1928","unstructured":"Born, M., Fock, V.: Beweis des adiabatensatzes. Z. Phys. 51(3), 165\u2013180 (1928). https:\/\/doi.org\/10.1007\/BF01343193","journal-title":"Z. Phys."},{"issue":"5","key":"9530_CR11","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1007\/s11128-008-0082-9","volume":"7","author":"V Choi","year":"2008","unstructured":"Choi, V.: Minor-embedding in adiabatic quantum computation: I. The parameter setting problem. Quantum Inf. Process. 7(5), 193\u2013209 (2008). https:\/\/doi.org\/10.1007\/s11128-008-0082-9","journal-title":"Quantum Inf. Process."},{"issue":"3","key":"9530_CR12","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1007\/s11128-010-0200-3","volume":"10","author":"V Choi","year":"2011","unstructured":"Choi, V.: Minor-embedding in adiabatic quantum computation: II. minor-universal graph design. Quantum Inf. Process. 10(3), 343\u2013353 (2011). https:\/\/doi.org\/10.1007\/s11128-010-0200-3","journal-title":"Quantum Inf. Process."},{"key":"9530_CR13","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1007\/978-3-030-19212-9_11","volume-title":"Integration of Constraint Programming, Artificial Intelligence, and Operations Research","author":"C Coffrin","year":"2019","unstructured":"Coffrin, C., Nagarajan, H., Bent, R.: Evaluating Ising processing units with integer programming. In: Rousseau, L.M., Stergiou, K. (eds.) Integration of Constraint Programming, Artificial Intelligence, and Operations Research, pp. 163\u2013181. Springer International Publishing, Cham (2019)"},{"issue":"7","key":"9530_CR14","doi-asserted-by":"publisher","first-page":"466","DOI":"10.1038\/s42254-021-00313-6","volume":"3","author":"EJ Crosson","year":"2021","unstructured":"Crosson, E.J., Lidar, D.A.: Prospects for quantum enhancement with diabatic quantum annealing. Nat. Rev. Phys. 3(7), 466\u2013489 (2021). https:\/\/doi.org\/10.1038\/s42254-021-00313-6","journal-title":"Nat. Rev. Phys."},{"key":"9530_CR15","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.94.062106","volume":"94","author":"PJD Crowley","year":"2016","unstructured":"Crowley, P.J.D., Green, A.G.: Anisotropic Landau\u2013Lifshitz\u2013Gilbert models of dissipation in qubits. Phys. Rev. A 94, 062106 (2016). https:\/\/doi.org\/10.1103\/PhysRevA.94.062106","journal-title":"Phys. Rev. A"},{"key":"9530_CR16","unstructured":"D-Wave Systems. (2020). D-Wave system documentation. https:\/\/docs.dwavesys.com\/docs\/latest. Accessed 17 Mar 2021"},{"key":"9530_CR17","unstructured":"D-Wave Systems. (2021). Clarity: a roadmap for the future of quantum computing. https:\/\/web.archive.org\/web\/20220320053047\/https:\/\/www.dwavesys.com\/media\/xvjpraig\/clarity-roadmap_digital_v2.pdf. Accessed 26 April 2022"},{"key":"9530_CR18","unstructured":"D-Wave Systems. (2022). dwave-neal. https:\/\/docs.ocean.dwavesys.com\/projects\/neal\/en\/latest. Accessed 15 Mar 2022"},{"key":"9530_CR19","unstructured":"D-Wave Systems. (2024). dwave-tabu. https:\/\/docs.ocean.dwavesys.com\/projects\/tabu\/en\/latest. Accessed 07 May 2024"},{"key":"9530_CR20","doi-asserted-by":"publisher","unstructured":"Dash, S.: A note on QUBO instances defined on Chimera graphs. (2013). https:\/\/doi.org\/10.48550\/arXiv.1306.1202","DOI":"10.48550\/arXiv.1306.1202"},{"key":"9530_CR21","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevX.6.031015","volume":"6","author":"VS Denchev","year":"2016","unstructured":"Denchev, V.S., Boixo, S., Isakov, S.V., et al.: What is the computational value of finite-range tunneling? Phys. Rev. X 6, 031015 (2016). https:\/\/doi.org\/10.1103\/PhysRevX.6.031015","journal-title":"Phys. Rev. X"},{"issue":"15","key":"9530_CR22","doi-asserted-by":"publisher","first-page":"5259","DOI":"10.1088\/0305-4470\/30\/15\/013","volume":"30","author":"D Dhar","year":"1997","unstructured":"Dhar, D., Shukla, P., Sethna, J.P.: Zero-temperature hysteresis in the random-field Ising model on a Bethe lattice. J. Phys. A: Math. Gen. 30(15), 5259\u20135267 (1997). https:\/\/doi.org\/10.1088\/0305-4470\/30\/15\/013","journal-title":"J. Phys. A: Math. Gen."},{"issue":"3","key":"9530_CR23","doi-asserted-by":"publisher","first-page":"608","DOI":"10.1287\/ijoc.2017.0798","volume":"30","author":"I Dunning","year":"2018","unstructured":"Dunning, I., Gupta, S., Silberholz, J.: What works best when? A systematic evaluation of heuristics for max-cut and QUBO. INFORMS J. Comput. 30(3), 608\u2013624 (2018). https:\/\/doi.org\/10.1287\/ijoc.2017.0798","journal-title":"INFORMS J. Comput."},{"key":"9530_CR24","doi-asserted-by":"publisher","unstructured":"Farhi, E., Goldstone, J., Gutmann, S., et al.: Quantum computation by adiabatic evolution. (2000). https:\/\/doi.org\/10.48550\/arXiv.quant-ph\/0001106","DOI":"10.48550\/arXiv.quant-ph\/0001106"},{"issue":"5516","key":"9530_CR25","doi-asserted-by":"publisher","first-page":"472","DOI":"10.1126\/science.1057726","volume":"292","author":"E Farhi","year":"2001","unstructured":"Farhi, E., Goldstone, J., Gutmann, S., et al.: A quantum adiabatic evolution algorithm applied to random instances of an NP-complete problem. Science 292(5516), 472\u2013475 (2001). https:\/\/doi.org\/10.1126\/science.1057726","journal-title":"Science"},{"key":"9530_CR26","doi-asserted-by":"publisher","unstructured":"Farhi, E., Goldstone, J., Gutmann, S.: Quantum adiabatic evolution algorithms versus simulated annealing. (2002). https:\/\/doi.org\/10.48550\/arXiv.quant-ph\/0201031","DOI":"10.48550\/arXiv.quant-ph\/0201031"},{"issue":"6","key":"9530_CR27","doi-asserted-by":"publisher","first-page":"467","DOI":"10.1007\/BF02650179","volume":"21","author":"RP Feynman","year":"1982","unstructured":"Feynman, R.P.: Simulating physics with computers. Int. J. Theor. Phys. 21(6), 467\u2013488 (1982). https:\/\/doi.org\/10.1007\/BF02650179","journal-title":"Int. J. Theor. Phys."},{"issue":"5","key":"9530_CR28","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1016\/0009-2614(94)00117-0","volume":"219","author":"A Finnila","year":"1994","unstructured":"Finnila, A., Gomez, M., Sebenik, C., et al.: Quantum annealing: a new method for minimizing multidimensional functions. Chem. Phys. Lett. 219(5), 343\u2013348 (1994). https:\/\/doi.org\/10.1016\/0009-2614(94)00117-0","journal-title":"Chem. Phys. Lett."},{"issue":"5","key":"9530_CR29","doi-asserted-by":"publisher","first-page":"673","DOI":"10.1109\/26.768759","volume":"47","author":"M Fossorier","year":"1999","unstructured":"Fossorier, M., Mihaljevic, M., Imai, H.: Reduced complexity iterative decoding of low-density parity check codes based on belief propagation. IEEE Trans. Commun. 47(5), 673\u2013680 (1999). https:\/\/doi.org\/10.1109\/26.768759","journal-title":"IEEE Trans. Commun."},{"key":"9530_CR30","volume-title":"Statistical Mechanics: A Short Treatise","author":"G Gallavotti","year":"2013","unstructured":"Gallavotti, G.: Statistical Mechanics: A Short Treatise. Springer Science & Business Media, New York (2013)"},{"key":"9530_CR31","unstructured":"Geyer, C.J. (1991). Parallel tempering. In: Keramidas, E.M., Kaufman, S.M. (eds) Computing Science and Statistics Proceedings of the 23rd Symposium on the Interface. American Statistical Association, New York, p 156"},{"issue":"2","key":"9530_CR32","doi-asserted-by":"publisher","first-page":"294","DOI":"10.1063\/1.1703954","volume":"4","author":"RJ Glauber","year":"1963","unstructured":"Glauber, R.J.: Time-dependent statistics of the Ising model. J. Math. Phys. 4(2), 294\u2013307 (1963). https:\/\/doi.org\/10.1063\/1.1703954","journal-title":"J. Math. Phys."},{"key":"9530_CR33","doi-asserted-by":"publisher","unstructured":"Glover, F., Laguna, M. (1998). Tabu Search, Springer US, Boston, MA, pp 2093\u20132229. https:\/\/doi.org\/10.1007\/978-1-4613-0303-9_33","DOI":"10.1007\/978-1-4613-0303-9_33"},{"issue":"4","key":"9530_CR34","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1007\/s10288-019-00424-y","volume":"17","author":"F Glover","year":"2019","unstructured":"Glover, F., Kochenberger, G., Du, Y.: Quantum bridge analytics I: a tutorial on formulating and using QUBO models. 4OR 17(4), 335\u2013371 (2019). https:\/\/doi.org\/10.1007\/s10288-019-00424-y","journal-title":"4OR"},{"issue":"1","key":"9530_CR35","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1007\/s10479-022-04634-2","volume":"314","author":"F Glover","year":"2022","unstructured":"Glover, F., Kochenberger, G., Hennig, R., et al.: Quantum bridge analytics I: a tutorial on formulating and using QUBO models. Ann. Oper. Res. 314(1), 141\u2013183 (2022a). https:\/\/doi.org\/10.1007\/s10479-022-04634-2","journal-title":"Ann. Oper. Res."},{"issue":"1","key":"9530_CR36","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1007\/s10479-022-04695-3","volume":"314","author":"F Glover","year":"2022","unstructured":"Glover, F., Kochenberger, G., Ma, M., et al.: Quantum bridge analytics II: QUBO-Plus, network optimization and combinatorial chaining for asset exchange. Ann. Oper. Res. 314(1), 185\u2013212 (2022b). https:\/\/doi.org\/10.1007\/s10479-022-04695-3","journal-title":"Ann. Oper. Res."},{"issue":"4","key":"9530_CR37","doi-asserted-by":"publisher","first-page":"eaav2372","DOI":"10.1126\/sciadv.aav2372","volume":"5","author":"H Goto","year":"2019","unstructured":"Goto, H., Tatsumura, K., Dixon, A.R.: Combinatorial optimization by simulating adiabatic bifurcations in nonlinear Hamiltonian systems. Sci. Adv. 5(4), eaav2372 (2019). https:\/\/doi.org\/10.1126\/sciadv.aav2372","journal-title":"Sci. Adv."},{"key":"9530_CR38","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevB.82.024511","volume":"82","author":"R Harris","year":"2010","unstructured":"Harris, R., Johnson, M.W., Lanting, T., et al.: Experimental investigation of an eight-qubit unit cell in a superconducting optimization processor. Phys. Rev. B 82, 024511 (2010). https:\/\/doi.org\/10.1103\/PhysRevB.82.024511","journal-title":"Phys. Rev. B"},{"issue":"1","key":"9530_CR39","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1093\/biomet\/57.1.97","volume":"57","author":"WK Hastings","year":"1970","unstructured":"Hastings, W.K.: Monte Carlo sampling methods using Markov chains and their applications. Biometrika 57(1), 97\u2013109 (1970). https:\/\/doi.org\/10.1093\/biomet\/57.1.97","journal-title":"Biometrika"},{"issue":"5","key":"9530_CR40","doi-asserted-by":"publisher","DOI":"10.1088\/1361-6633\/ab85b8","volume":"83","author":"P Hauke","year":"2020","unstructured":"Hauke, P., Katzgraber, H.G., Lechner, W., et al.: Perspectives of quantum annealing: methods and implementations. Rep. Prog. Phys. 83(5), 054401 (2020). https:\/\/doi.org\/10.1088\/1361-6633\/ab85b8","journal-title":"Rep. Prog. Phys."},{"key":"9530_CR41","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.92.042325","volume":"92","author":"I Hen","year":"2015","unstructured":"Hen, I., Job, J., Albash, T., et al.: Probing for quantum speedup in spin-glass problems with planted solutions. Phys. Rev. A 92, 042325 (2015). https:\/\/doi.org\/10.1103\/PhysRevA.92.042325","journal-title":"Phys. Rev. A"},{"issue":"40","key":"9530_CR42","doi-asserted-by":"publisher","first-page":"eabh0952","DOI":"10.1126\/sciadv.abh0952","volume":"7","author":"T Honjo","year":"2021","unstructured":"Honjo, T., Sonobe, T., Inaba, K., et al.: 100,000-spin coherent Ising machine. Sci. Adv. 7(40), eabh0952 (2021). https:\/\/doi.org\/10.1126\/sciadv.abh0952","journal-title":"Sci. Adv."},{"issue":"4","key":"9530_CR43","doi-asserted-by":"publisher","first-page":"479","DOI":"10.1007\/PL00011151","volume":"22","author":"J Houdayer","year":"2001","unstructured":"Houdayer, J.: A cluster Monte Carlo algorithm for 2-dimensional spin glasses. Eur. Phys. J. B 22(4), 479\u2013484 (2001). https:\/\/doi.org\/10.1007\/PL00011151","journal-title":"Eur. Phys. J. B"},{"issue":"6","key":"9530_CR44","doi-asserted-by":"publisher","first-page":"1604","DOI":"10.1143\/JPSJ.65.1604","volume":"65","author":"K Hukushima","year":"1996","unstructured":"Hukushima, K., Nemoto, K.: Exchange Monte Carlo method and application to spin glass simulations. J. Phys. Soc. Jpn. 65(6), 1604\u20131608 (1996). https:\/\/doi.org\/10.1143\/JPSJ.65.1604","journal-title":"J. Phys. Soc. Jpn."},{"issue":"10","key":"9530_CR45","doi-asserted-by":"publisher","DOI":"10.1063\/1.2798382","volume":"48","author":"S Jansen","year":"2007","unstructured":"Jansen, S., Ruskai, M.B., Seiler, R.: Bounds for the adiabatic approximation with applications to quantum computation. J. Math. Phys. 48(10), 102111 (2007). https:\/\/doi.org\/10.1063\/1.2798382","journal-title":"J. Math. Phys."},{"issue":"3","key":"9530_CR46","doi-asserted-by":"publisher","DOI":"10.1088\/2058-9565\/aabd9b","volume":"3","author":"J Job","year":"2018","unstructured":"Job, J., Lidar, D.: Test-driving 1000 qubits. Quant. Sci. Technol. 3(3), 030501 (2018). https:\/\/doi.org\/10.1088\/2058-9565\/aabd9b","journal-title":"Quant. Sci. Technol."},{"issue":"6","key":"9530_CR47","doi-asserted-by":"publisher","DOI":"10.1088\/0953-2048\/23\/6\/065004","volume":"23","author":"MW Johnson","year":"2010","unstructured":"Johnson, M.W., Bunyk, P., Maibaum, F., et al.: A scalable control system for a superconducting adiabatic quantum optimization processor. Supercond. Sci. Technol. 23(6), 065004 (2010). https:\/\/doi.org\/10.1088\/0953-2048\/23\/6\/065004","journal-title":"Supercond. Sci. Technol."},{"issue":"7346","key":"9530_CR48","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1038\/nature10012","volume":"473","author":"MW Johnson","year":"2011","unstructured":"Johnson, M.W., Amin, M.H.S., Gildert, S., et al.: Quantum annealing with manufactured spins. Nature 473(7346), 194\u2013198 (2011). https:\/\/doi.org\/10.1038\/nature10012","journal-title":"Nature"},{"key":"9530_CR49","doi-asserted-by":"publisher","first-page":"5355","DOI":"10.1103\/PhysRevE.58.5355","volume":"58","author":"T Kadowaki","year":"1998","unstructured":"Kadowaki, T., Nishimori, H.: Quantum annealing in the transverse Ising model. Phys. Rev. E 58, 5355\u20135363 (1998). https:\/\/doi.org\/10.1103\/PhysRevE.58.5355","journal-title":"Phys. Rev. E"},{"issue":"6","key":"9530_CR50","doi-asserted-by":"publisher","first-page":"435","DOI":"10.1143\/JPSJ.5.435","volume":"5","author":"T Kato","year":"1950","unstructured":"Kato, T.: On the adiabatic theorem of quantum mechanics. J. Phys. Soc. Jpn. 5(6), 435\u2013439 (1950). https:\/\/doi.org\/10.1143\/JPSJ.5.435","journal-title":"J. Phys. Soc. Jpn."},{"key":"9530_CR51","doi-asserted-by":"publisher","first-page":"P03018","DOI":"10.1088\/1742-5468\/2006\/03\/p03018","volume":"03","author":"HG Katzgraber","year":"2006","unstructured":"Katzgraber, H.G., Trebst, S., Huse, D.A., et al.: Feedback-optimized parallel tempering Monte Carlo. J. Stat. Mech: Theory Exp. 03, P03018\u2013P03018 (2006). https:\/\/doi.org\/10.1088\/1742-5468\/2006\/03\/p03018","journal-title":"J. Stat. Mech: Theory Exp."},{"issue":"11","key":"9530_CR52","doi-asserted-by":"publisher","first-page":"1324","DOI":"10.1038\/s41567-022-01741-6","volume":"18","author":"AD King","year":"2022","unstructured":"King, A.D., Suzuki, S., Raymond, J., et al.: Coherent quantum annealing in a programmable 2,000 qubit Ising chain. Nat. Phys. 18(11), 1324\u20131328 (2022). https:\/\/doi.org\/10.1038\/s41567-022-01741-6","journal-title":"Nat. Phys."},{"key":"9530_CR53","doi-asserted-by":"publisher","unstructured":"King, J., Yarkoni, S., Nevisi, M.M., et al.: Benchmarking a quantum annealing processor with the time-to-target metric. (2015). https:\/\/doi.org\/10.48550\/arXiv.1508.05087","DOI":"10.48550\/arXiv.1508.05087"},{"key":"9530_CR54","doi-asserted-by":"publisher","unstructured":"King, J., Yarkoni, S., Raymond, J., et al.: Quantum annealing amid local ruggedness and global frustration. (2017). https:\/\/doi.org\/10.48550\/arXiv.1701.04579","DOI":"10.48550\/arXiv.1701.04579"},{"key":"9530_CR55","doi-asserted-by":"publisher","first-page":"2349","DOI":"10.1103\/PhysRevD.19.2349","volume":"19","author":"JR Klauder","year":"1979","unstructured":"Klauder, J.R.: Path integrals and stationary-phase approximations. Phys. Rev. D 19, 2349\u20132356 (1979). https:\/\/doi.org\/10.1103\/PhysRevD.19.2349","journal-title":"Phys. Rev. D"},{"issue":"1","key":"9530_CR56","doi-asserted-by":"publisher","first-page":"58","DOI":"10.1007\/s10878-014-9734-0","volume":"28","author":"G Kochenberger","year":"2014","unstructured":"Kochenberger, G., Hao, J.K., Glover, F., et al.: The unconstrained binary quadratic programming problem: a survey. J. Comb. Optim. 28(1), 58\u201381 (2014). https:\/\/doi.org\/10.1007\/s10878-014-9734-0","journal-title":"J. Comb. Optim."},{"issue":"20","key":"9530_CR57","doi-asserted-by":"publisher","DOI":"10.1063\/1.1917749","volume":"122","author":"A Kone","year":"2005","unstructured":"Kone, A., Kofke, D.A.: Selection of temperature intervals for parallel-tempering simulations. J. Chem. Phys. 122(20), 206101 (2005). https:\/\/doi.org\/10.1063\/1.1917749","journal-title":"J. Chem. Phys."},{"issue":"2","key":"9530_CR58","doi-asserted-by":"publisher","DOI":"10.1088\/2058-9565\/ac4d1b","volume":"7","author":"M Kowalsky","year":"2022","unstructured":"Kowalsky, M., Albash, T., Hen, I., et al.: 3-regular three-XORSAT planted solutions benchmark of classical and quantum heuristic optimizers. Quant. Sci. Technol. 7(2), 025008 (2022). https:\/\/doi.org\/10.1088\/2058-9565\/ac4d1b","journal-title":"Quant. Sci. Technol."},{"key":"9530_CR59","doi-asserted-by":"publisher","unstructured":"van Laarhoven, P.J.M., Aarts, E.H.L. (1987). Simulated annealing, Springer Netherlands, Dordrecht, pp 7\u201315. https:\/\/doi.org\/10.1007\/978-94-015-7744-1_2","DOI":"10.1007\/978-94-015-7744-1_2"},{"key":"9530_CR60","doi-asserted-by":"publisher","DOI":"10.3389\/fphy.2014.00005","author":"A Lucas","year":"2014","unstructured":"Lucas, A.: Ising formulations of many NP problems. Front. Phys. (2014). https:\/\/doi.org\/10.3389\/fphy.2014.00005","journal-title":"Front. Phys."},{"issue":"4","key":"9530_CR61","doi-asserted-by":"publisher","first-page":"04LT01","DOI":"10.1088\/2058-9565\/aac8b2","volume":"3","author":"S Mandr\u00e0","year":"2018","unstructured":"Mandr\u00e0, S., Katzgraber, H.G.: A deceptive step towards quantum speedup detection. Quant. Sci. Technol. 3(4), 04LT01 (2018). https:\/\/doi.org\/10.1088\/2058-9565\/aac8b2","journal-title":"Quant. Sci. Technol."},{"key":"9530_CR62","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.94.022337","volume":"94","author":"S Mandr\u00e0","year":"2016","unstructured":"Mandr\u00e0, S., Zhu, Z., Wang, W., et al.: Strengths and weaknesses of weak-strong cluster problems: a detailed overview of state-of-the-art classical heuristics versus quantum approaches. Phys. Rev. A 94, 022337 (2016). https:\/\/doi.org\/10.1103\/PhysRevA.94.022337","journal-title":"Phys. Rev. A"},{"key":"9530_CR63","doi-asserted-by":"publisher","unstructured":"Matsubara, S., Takatsu, M., Miyazawa, T., et\u00a0al (2020) Digital annealer for high-speed solving of combinatorial optimization problems and its applications. In: 2020 25th Asia and South Pacific design automation conference (ASP-DAC), pp 667\u2013672, https:\/\/doi.org\/10.1109\/ASP-DAC47756.2020.9045100","DOI":"10.1109\/ASP-DAC47756.2020.9045100"},{"key":"9530_CR64","unstructured":"McGeoch, C., Farre, P. (2020). The D-wave advantage system: an overview. Technical Report https:\/\/www.dwavesys.com\/media\/s3qbjp3s\/14-1049a-a_the_d-wave_advantage_system_an_overview.pdf"},{"key":"9530_CR65","doi-asserted-by":"publisher","unstructured":"McGeoch, C.C., Wang, C. (2013). Experimental evaluation of an adiabiatic quantum system for combinatorial optimization. In: Proceedings of the ACM International Conference on Computing Frontiers. ACM, New York, CF \u201913, pp. 23:1\u201323:11. https:\/\/doi.org\/10.1145\/2482767.2482797","DOI":"10.1145\/2482767.2482797"},{"issue":"6312","key":"9530_CR66","doi-asserted-by":"publisher","first-page":"614","DOI":"10.1126\/science.aah5178","volume":"354","author":"PL McMahon","year":"2016","unstructured":"McMahon, P.L., Marandi, A., Haribara, Y., et al.: A fully programmable 100-spin coherent Ising machine with all-to-all connections. Science 354(6312), 614\u2013617 (2016). https:\/\/doi.org\/10.1126\/science.aah5178","journal-title":"Science"},{"issue":"6","key":"9530_CR67","doi-asserted-by":"publisher","first-page":"1087","DOI":"10.1063\/1.1699114","volume":"21","author":"N Metropolis","year":"1953","unstructured":"Metropolis, N., Rosenbluth, A.W., Rosenbluth, M.N., et al.: Equation of state calculations by fast computing machines. J. Chem. Phys. 21(6), 1087\u20131092 (1953). https:\/\/doi.org\/10.1063\/1.1699114","journal-title":"J. Chem. Phys."},{"key":"9530_CR68","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198570837.001.0001","volume-title":"Information, Physics, and Computation","author":"M Mezard","year":"2009","unstructured":"Mezard, M., Montanari, A.: Information, Physics, and Computation. Oxford University Press, Oxford (2009)"},{"key":"9530_CR69","doi-asserted-by":"publisher","unstructured":"Mohseni, M., Eppens, D., Strumpfer, J., et al.: Nonequilibrium Monte Carlo for unfreezing variables in hard combinatorial optimization. (2021). https:\/\/doi.org\/10.48550\/arXiv.2111.13628","DOI":"10.48550\/arXiv.2111.13628"},{"key":"9530_CR70","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1109\/TQE.2021.3092710","volume":"2","author":"J Nelson","year":"2021","unstructured":"Nelson, J., Vuffray, M., Lokhov, A.Y., et al.: Single-qubit fidelity assessment of quantum annealing hardware. IEEE Trans. Quant. Eng. 2, 1\u201310 (2021). https:\/\/doi.org\/10.1109\/TQE.2021.3092710","journal-title":"IEEE Trans. Quant. Eng."},{"issue":"1","key":"9530_CR71","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1023\/B:ANOR.0000039522.58036.68","volume":"131","author":"G Palubeckis","year":"2004","unstructured":"Palubeckis, G.: Multistart Tabu search strategies for the unconstrained binary quadratic optimization problem. Ann. Oper. Res. 131(1), 259\u2013282 (2004). https:\/\/doi.org\/10.1023\/B:ANOR.0000039522.58036.68","journal-title":"Ann. Oper. Res."},{"issue":"1","key":"9530_CR72","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10601-020-09315-0","volume":"26","author":"Y Pang","year":"2021","unstructured":"Pang, Y., Coffrin, C., Lokhov, A.Y., et al.: The potential of quantum annealing for rapid solution structure identification. Constraints 26(1), 1\u201325 (2021). https:\/\/doi.org\/10.1007\/s10601-020-09315-0","journal-title":"Constraints"},{"key":"9530_CR73","unstructured":"Puget JF (2013) D-Wave vs CPLEX comparison. Part 2: QUBO. https:\/\/web.archive.org\/web\/20170702140136\/https:\/\/www.ibm.com\/developerworks\/community\/blogs\/jfp\/entry\/d_wave_vs_cplex_comparison_part_2_qubo?lang=en Accessed 27 April 2022"},{"key":"9530_CR74","doi-asserted-by":"publisher","first-page":"11828","DOI":"10.1103\/PhysRevB.39.11828","volume":"39","author":"P Ray","year":"1989","unstructured":"Ray, P., Chakrabarti, B.K., Chakrabarti, A.: Sherrington-Kirkpatrick model in a transverse field: absence of replica symmetry breaking due to quantum fluctuations. Phys. Rev. B 39, 11828\u201311832 (1989). https:\/\/doi.org\/10.1103\/PhysRevB.39.11828","journal-title":"Phys. Rev. B"},{"key":"9530_CR75","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.100.043311","volume":"100","author":"I Rozada","year":"2019","unstructured":"Rozada, I., Aramon, M., Machta, J., et al.: Effects of setting temperatures in the parallel tempering Monte Carlo algorithm. Phys. Rev. E 100, 043311 (2019). https:\/\/doi.org\/10.1103\/PhysRevE.100.043311","journal-title":"Phys. Rev. E"},{"issue":"6195","key":"9530_CR76","doi-asserted-by":"publisher","first-page":"420","DOI":"10.1126\/science.1252319","volume":"345","author":"TF R\u00f8nnow","year":"2014","unstructured":"R\u00f8nnow, T.F., Wang, Z., Job, J., et al.: Defining and detecting quantum speedup. Science 345(6195), 420\u2013424 (2014). https:\/\/doi.org\/10.1126\/science.1252319","journal-title":"Science"},{"issue":"5564","key":"9530_CR77","doi-asserted-by":"publisher","first-page":"2427","DOI":"10.1126\/science.1068774","volume":"295","author":"GE Santoro","year":"2002","unstructured":"Santoro, G.E., Marto\u0148\u00e1k, R., Tosatti, E., et al.: Theory of quantum annealing of an Ising spin glass. Science 295(5564), 2427\u20132430 (2002). https:\/\/doi.org\/10.1126\/science.1068774","journal-title":"Science"},{"key":"9530_CR78","unstructured":"Selby A (2013) QUBO-Chimera. https:\/\/github.com\/alex1770\/QUBO-Chimera"},{"key":"9530_CR79","doi-asserted-by":"publisher","unstructured":"Selby, A.: Efficient subgraph-based sampling of Ising-type models with frustration. (2014). https:\/\/doi.org\/10.48550\/arXiv.1409.3934","DOI":"10.48550\/arXiv.1409.3934"},{"issue":"1","key":"9530_CR80","doi-asserted-by":"publisher","first-page":"427","DOI":"10.1287\/ijoc.2021.1065","volume":"34","author":"T Serra","year":"2022","unstructured":"Serra, T., Huang, T., Raghunathan, A.U., et al.: Template-based minor embedding for adiabatic quantum optimization. INFORMS J. Comput. 34(1), 427\u2013439 (2022). https:\/\/doi.org\/10.1287\/ijoc.2021.1065","journal-title":"INFORMS J. Comput."},{"key":"9530_CR81","doi-asserted-by":"publisher","unstructured":"Shin, S.W., Smith, G., Smolin, J.A., et\u00a0al. (2014). How \u201cquantum\u201d is the D-Wave machine? https:\/\/doi.org\/10.48550\/arXiv.1401.7087","DOI":"10.48550\/arXiv.1401.7087"},{"key":"9530_CR82","doi-asserted-by":"publisher","first-page":"2607","DOI":"10.1103\/PhysRevLett.57.2607","volume":"57","author":"RH Swendsen","year":"1986","unstructured":"Swendsen, R.H., Wang, J.S.: Replica Monte Carlo simulation of spin-glasses. Phys. Rev. Lett. 57, 2607\u20132609 (1986). https:\/\/doi.org\/10.1103\/PhysRevLett.57.2607","journal-title":"Phys. Rev. Lett."},{"key":"9530_CR83","unstructured":"Vuffray, M.: The cavity method in coding theory. Tech. rep, EPFL (2014)"},{"key":"9530_CR84","doi-asserted-by":"publisher","DOI":"10.1103\/PRXQuantum.3.020317","volume":"3","author":"M Vuffray","year":"2022","unstructured":"Vuffray, M., Coffrin, C., Kharkov, Y.A., et al.: Programmable quantum annealers as noisy Gibbs samplers. PRX Quantum 3, 020317 (2022). https:\/\/doi.org\/10.1103\/PRXQuantum.3.020317","journal-title":"PRX Quantum"},{"key":"9530_CR85","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1109\/TQE.2021.3050449","volume":"2","author":"T Zaborniak","year":"2021","unstructured":"Zaborniak, T., de Sousa, R.: Benchmarking Hamiltonian noise in the D-Wave quantum annealer. IEEE Trans. Quant. Eng. 2, 1\u20136 (2021). https:\/\/doi.org\/10.1109\/TQE.2021.3050449","journal-title":"IEEE Trans. Quant. Eng."},{"key":"9530_CR86","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.115.077201","volume":"115","author":"B Zhu","year":"2015","unstructured":"Zhu, B., Ochoa, A.J., Katzgraber, H.G.: Efficient cluster algorithm for spin glasses in any space dimension. Phys. Rev. Lett. 115, 077201 (2015). https:\/\/doi.org\/10.1103\/PhysRevLett.115.077201","journal-title":"Phys. Rev. Lett."}],"container-title":["Journal of Heuristics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10732-024-09530-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10732-024-09530-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10732-024-09530-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,16]],"date-time":"2024-10-16T07:08:36Z","timestamp":1729062516000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10732-024-09530-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,8,2]]},"references-count":86,"journal-issue":{"issue":"5-6","published-print":{"date-parts":[[2024,12]]}},"alternative-id":["9530"],"URL":"https:\/\/doi.org\/10.1007\/s10732-024-09530-5","relation":{},"ISSN":["1381-1231","1572-9397"],"issn-type":[{"value":"1381-1231","type":"print"},{"value":"1572-9397","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,8,2]]},"assertion":[{"value":"14 May 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 June 2024","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 June 2024","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 August 2024","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no Conflict of interest to declare that are relevant to the content of this article.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}