{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,19]],"date-time":"2026-03-19T23:56:30Z","timestamp":1773964590074,"version":"3.50.1"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"10","license":[{"start":{"date-parts":[[2023,10,4]],"date-time":"2023-10-04T00:00:00Z","timestamp":1696377600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,10,4]],"date-time":"2023-10-04T00:00:00Z","timestamp":1696377600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100018624","name":"Universities Space Research Association","doi-asserted-by":"publisher","award":["NNA16BD14C"],"award-info":[{"award-number":["NNA16BD14C"]}],"id":[{"id":"10.13039\/100018624","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006502","name":"Defense Sciences Office, DARPA","doi-asserted-by":"publisher","award":["F4HBKC4162G001"],"award-info":[{"award-number":["F4HBKC4162G001"]}],"id":[{"id":"10.13039\/100006502","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100011039","name":"Intelligence Advanced Research Projects Activity","doi-asserted-by":"publisher","award":["IAA 145483"],"award-info":[{"award-number":["IAA 145483"]}],"id":[{"id":"10.13039\/100011039","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006034","name":"University of Southern California","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100006034","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Quantum Inf Process"],"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We compare the performance of four quantum annealers, the D-Wave <jats:italic>Two<\/jats:italic>, <jats:italic>2X<\/jats:italic>, <jats:italic>2000Q<\/jats:italic>, and <jats:italic>Advantage<\/jats:italic> in solving an identical ensemble of a parametrized family of scheduling problems. These problems are NP-complete and, in fact, equivalent to vertex coloring problems. They are also practically motivated and closely connected to planning problems from artificial intelligence. We examine factors contributing to the performance differences while separating the contributions from hardware upgrades, support for shorter anneal times, and possible optimization of ferromagnetic couplings. While shorter anneal times can improve the time to solution (TTS) at any given problem size, the scaling of TTS with respect to the problem size worsens for shorter anneal times. In contrast, optimizing the ferromagnetic coupling improves both the absolute TTS and the scaling. There is a statistically significant improvement in performance between D-Wave Two and 2X and from all older generation annealers to Advantage, even when operated under identical anneal time and ferromagnetic couplings. However, the performance improvement from 2X to 2000Q requires the anneal time and ferromagnetic couplings to be optimized. Overall, owing to these inter-generational hardware improvements and optimizations, the scaling exponent reduces from <jats:inline-formula><jats:alternatives><jats:tex-math>$$1.01 \\pm 0.01$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mn>1.01<\/mml:mn>\n                    <mml:mo>\u00b1<\/mml:mo>\n                    <mml:mn>0.01<\/mml:mn>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> on Two to <jats:inline-formula><jats:alternatives><jats:tex-math>$$0.259 \\pm 0.008$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mn>0.259<\/mml:mn>\n                    <mml:mo>\u00b1<\/mml:mo>\n                    <mml:mn>0.008<\/mml:mn>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> on Advantage.\n<\/jats:p>","DOI":"10.1007\/s11128-023-04077-z","type":"journal-article","created":{"date-parts":[[2023,10,4]],"date-time":"2023-10-04T09:02:22Z","timestamp":1696410142000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Inter-generational comparison of quantum annealers in solving hard scheduling problems"],"prefix":"10.1007","volume":"22","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4284-1353","authenticated-orcid":false,"given":"Bibek","family":"Pokharel","sequence":"first","affiliation":[]},{"given":"Zoe Gonzalez","family":"Izquierdo","sequence":"additional","affiliation":[]},{"given":"P. Aaron","family":"Lott","sequence":"additional","affiliation":[]},{"given":"Elena","family":"Strbac","sequence":"additional","affiliation":[]},{"given":"Krzysztof","family":"Osiewalski","sequence":"additional","affiliation":[]},{"given":"Emmanuel","family":"Papathanasiou","sequence":"additional","affiliation":[]},{"given":"Alexei","family":"Kondratyev","sequence":"additional","affiliation":[]},{"given":"Davide","family":"Venturelli","sequence":"additional","affiliation":[]},{"given":"Eleanor","family":"Rieffel","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,10,4]]},"reference":[{"key":"4077_CR1","volume-title":"A Gentle Introduction to Quantum Computing","author":"EG Rieffel","year":"2011","unstructured":"Rieffel, E.G., Polak, W.: A Gentle Introduction to Quantum Computing. MIT Press, Cambridge (2011)"},{"key":"4077_CR2","volume-title":"Quantum Computing and Quantum Information","author":"M Nielsen","year":"2001","unstructured":"Nielsen, M., Chuang, I.L.: Quantum Computing and Quantum Information. Cambridge University Press, Cambridge (2001)"},{"issue":"1","key":"4077_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s11128-014-0892-x","volume":"14","author":"EG Rieffel","year":"2015","unstructured":"Rieffel, E.G., Venturelli, D., O\u2019Gorman, B., Do, M.B., Prystay, E.M., Smelyanskiy, V.N.: A case study in programming a quantum annealer for hard operational planning problems. Quantum Inf. Process. 14(1), 1 (2015)","journal-title":"Quantum Inf. Process."},{"issue":"3","key":"4077_CR4","first-page":"031040","volume":"5","author":"D Venturelli","year":"2015","unstructured":"Venturelli, D., Mandr\u00e0, S., Knysh, S., O\u2019Gorman, B., Biswas, R., Smelyanskiy, V.: Quantum optimization of fully-connected spin glasses. Phys. Rev. X 5(3), 031040 (2015)","journal-title":"Phys. Rev. X"},{"key":"4077_CR5","doi-asserted-by":"crossref","unstructured":"Kim, M., Venturelli, D., Jamieson, K.: Leveraging quantum annealing for large MIMO processing in centralized radio access networks, in Proceedings of the ACM special interest group on data communication (Association for Computing Machinery, New York, NY, USA, 2019), SIGCOMM \u201919, pp. 241-255","DOI":"10.1145\/3341302.3342072"},{"key":"4077_CR6","doi-asserted-by":"publisher","first-page":"044083","DOI":"10.1103\/PhysRevApplied.11.044083","volume":"11","author":"J Marshall","year":"2019","unstructured":"Marshall, J., Venturelli, D., Hen, I., Rieffel, E.G.: Power of pausing: advancing understanding of thermalization in experimental quantum annealers. Phys. Rev. Appl. 11, 044083 (2019)","journal-title":"Phys. Rev. Appl."},{"key":"4077_CR7","doi-asserted-by":"publisher","first-page":"044013","DOI":"10.1103\/PhysRevApplied.15.044013","volume":"15","author":"Z Gonzalez Izquierdo","year":"2021","unstructured":"Gonzalez Izquierdo, Z., Grabbe, S., Hadfield, S., Marshall, J., Wang, Z., Rieffel, E.: Ferromagnetically shifting the power of pausing. Phys. Rev. Appl. 15, 044013 (2021)","journal-title":"Phys. Rev. Appl."},{"key":"4077_CR8","unstructured":"Farhi, E., Goldstone, J., Gutmann, S., Sipser, M.: Quantum computation by adiabatic evolution. arXiv:quant-ph\/0001106 (2000)"},{"key":"4077_CR9","unstructured":"Smelyanskiy, V.N., Rieffel, E.G., Knysh, S.I., Williams, C.P., Johnson, M.W., Thom, M.C., Macready, W.G., Pudenz, K.L.: A near-term quantum computing approach for hard computational problems in space exploration. arXiv:1204.2821 (2012)"},{"key":"4077_CR10","unstructured":"McGeoch, C., Farr\u00e9, P.: The D-Wave Advantage system: an overview, the d-wave advantage system: an overview. Tecnhical report 14-1049A-A, D-Wave Sys (2020)"},{"key":"4077_CR11","unstructured":"Error sources for problem representation. https:\/\/docs.dwavesys.com\/docs\/latest\/c_qpu_ice.html"},{"key":"4077_CR12","doi-asserted-by":"crossref","unstructured":"Willsch, D., Willsch, M., Calaza, C.D.G., Jin, F., Raedt, H.D., Svensson, M., Michielsen, K.: Benchmarking advantage and D-Wave 2000Q quantum annealers with exact cover problems, arXiv:2105.02208 (2021)","DOI":"10.1007\/s11128-022-03476-y"},{"issue":"5\u20136","key":"4077_CR13","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., Stenson, C., Doll, J.: Quantum annealing: a new method for minimizing multidimensional functions. Chem. Phys. Lett. 219(5\u20136), 343 (1994)","journal-title":"Chem. Phys. Lett."},{"key":"4077_CR14","unstructured":"The QPU timing. https:\/\/docs.dwavesys.com\/docs\/latest\/c_qpu_timing.html"},{"issue":"5","key":"4077_CR15","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 (2008)","journal-title":"Quantum Inf. Process."},{"key":"4077_CR16","doi-asserted-by":"crossref","unstructured":"Lucas, A.: Ising formulations of many NP problems. arXiv:1302.5843 (2013)","DOI":"10.3389\/fphy.2014.00005"},{"key":"4077_CR17","unstructured":"Shin, S.W., Smith, G., Smolin, J.A., Vazirani, U.: Comment on \u201cDistinguishing classical and quantum models for the D-Wave device\". arXiv:1404.6499 (2014)"},{"key":"4077_CR18","doi-asserted-by":"crossref","unstructured":"Pudenz, K.L.: Parameter setting for quantum annealers, arXiv e-prints arXiv:1611.07552 (2016)","DOI":"10.1109\/HPEC.2016.7761619"},{"issue":"7346","key":"4077_CR19","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1038\/nature10012","volume":"473","author":"M Johnson","year":"2011","unstructured":"Johnson, M., Amin, M., Gildert, S., Lanting, T., Hamze, F., Dickson, N., Harris, R., Berkley, A., Johansson, J., Bunyk, P., et al.: Quantum annealing with manufactured spins. Nature 473(7346), 194 (2011)","journal-title":"Nature"},{"issue":"3","key":"4077_CR20","first-page":"030501","volume":"3","author":"J Job","year":"2018","unstructured":"Job, J., Lidar, D.: Test-driving 1000 qubits, quantum. Sci. Technol. 3(3), 030501 (2018)","journal-title":"Sci. Technol."},{"key":"4077_CR21","unstructured":"Boothby, K., Enderud, C., Lanting, T., Molavi, R., Tsai, N., Volkmann, M.H., Altomare, F., Amin, M.H., Babcock, M., Berkley, A.J., Baron Aznar, C., Boschnak, M., Christiani, H., Ejtemaee, S., Evert, B., Gullen, M., Hager, M., Harris, R., Hoskinson, E., Hilton, J.P., Jooya, K., Huang, A., Johnson, M.W., King, A.D., Ladizinsky, E., Li, R., MacDonald, A., Medina Fernandez, T., Neufeld, R., Norouzpour, M., Oh, T., Ozfidan, I., Paddon, P., Perminov, I., Poulin-Lamarre, G., Prescott, T., Raymond, J., Reis, M., Rich, C., Roy, A., Sadeghi Esfahani, H., Sato, Y., Sheldan, B., Smirnov, A., Swenson, L.J., Whittaker, J., Yao, J., Yarovoy, A., Bunyk, P.I.: Architectural considerations in the design of a third-generation superconducting quantum annealing processor, arXiv e-prints arXiv:2108.02322 (2021)"},{"key":"4077_CR22","unstructured":"Chien, S., Rabideau, G., Knight, R., Sherwood, R., Engelhardt, B., Mutz, D., Estlin, T., Smith, B., Fisher, F., Barrett, T., Stebbins, G., Tran, D.: in Proceedings of SpaceOps (2000)"},{"issue":"1","key":"4077_CR23","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1002\/(SICI)1098-2418(1999010)14:1<63::AID-RSA3>3.0.CO;2-7","volume":"14","author":"D Achlioptas","year":"1999","unstructured":"Achlioptas, D., Friedgut, E.: A sharp threshold for k-colorability. Random Struct. Algorithms 14(1), 63 (1999)","journal-title":"Random Struct. Algorithms"},{"key":"4077_CR24","doi-asserted-by":"crossref","unstructured":"Coja-Oghlan, A.: Upper-bounding the k-colorability threshold by counting covers, upper-bounding the k-colorability threshold by counting covers. arXiv:1305.0177 (2013)","DOI":"10.37236\/3337"},{"key":"4077_CR25","doi-asserted-by":"crossref","unstructured":"Rieffel, E.G., Venturelli, D., Hen, I., Do, M., Frank, J.: Parametrized families of hard planning problems from phase transitions, in Proceedings of the twenty-eighth aaai conference on artificial intelligence (AAAI-14), pp. 2337 \u2013 2343 (2014)","DOI":"10.1609\/aaai.v28i1.9044"},{"key":"4077_CR26","unstructured":"Culberson, J., Beacham, A., Papp, D.: in Proceedings of the CP95 workshop on studying and solving really hard problems, pp. 31\u201342 (1995)"},{"issue":"1","key":"4077_CR27","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s11128-014-0892-x","volume":"14","author":"EG Rieffel","year":"2015","unstructured":"Rieffel, E.G., Venturelli, D., O\u2019Gorman, B., Do, M.B., Prystay, E.M., Smelyanskiy, V.N.: A case study in programming a quantum annealer for hard operational planning problems. Quantum Inf. Process. 14(1), 1 (2015)","journal-title":"Quantum Inf. Process."},{"key":"4077_CR28","unstructured":"Cai, J., Macready, W.G., Roy, A.: A practical heuristic for finding graph minors, arXiv preprint arXiv:1406.2741 (2014)"},{"issue":"2","key":"4077_CR29","doi-asserted-by":"publisher","first-page":"025008","DOI":"10.1088\/2058-9565\/ac4d1b","volume":"7","author":"M Kowalsky","year":"2022","unstructured":"Kowalsky, M., Albash, T., Hen, I., Lidar, D.A.: 3-regular three-XORSAT planted solutions benchmark of classical and quantum heuristic optimizers. Quantum Sci. Technol. 7(2), 025008 (2022)","journal-title":"Quantum Sci. Technol."},{"key":"4077_CR30","unstructured":"Boothby, K., Bunyk, P., Raymond, J., Roy, A.: Next-generation topology of d-wave quantum processors. Technical report 14-1026A-C, D-Wave Sys (2019)"},{"key":"4077_CR31","unstructured":"Izquierdo, Z.G., Grabbe, S., Idris, H., Wang, Z., Marshall, J., Rieffel, E.: The advantage of pausing: parameter setting for quantum annealers, arXiv preprint arXiv:2205.12936 (2022)"},{"issue":"4","key":"4077_CR32","doi-asserted-by":"publisher","first-page":"040322","DOI":"10.1103\/PRXQuantum.2.040322","volume":"2","author":"MS K\u00f6nz","year":"2021","unstructured":"K\u00f6nz, M.S., Lechner, W., Katzgraber, H.G., Troyer, M.: Embedding overhead scaling of optimization problems in quantum annealing. PRX Quantum 2(4), 040322 (2021)","journal-title":"PRX Quantum"},{"key":"4077_CR33","doi-asserted-by":"crossref","unstructured":"Fang, Y.L., Warburton, P.: Minimizing minor embedding energy: an application in quantum annealing. Quantum Inf. Process. 19(7), 191 (2020)","DOI":"10.1007\/s11128-020-02681-x"}],"container-title":["Quantum Information Processing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11128-023-04077-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11128-023-04077-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11128-023-04077-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,31]],"date-time":"2023-10-31T18:11:10Z","timestamp":1698775870000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11128-023-04077-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,10,4]]},"references-count":33,"journal-issue":{"issue":"10","published-online":{"date-parts":[[2023,10]]}},"alternative-id":["4077"],"URL":"https:\/\/doi.org\/10.1007\/s11128-023-04077-z","relation":{},"ISSN":["1573-1332"],"issn-type":[{"value":"1573-1332","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,10,4]]},"assertion":[{"value":"19 June 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 July 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 October 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that the research was conducted in the absence of any commercial or financial relationships that could be construed as a potential conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"364"}}