{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,11]],"date-time":"2026-04-11T04:10:32Z","timestamp":1775880632078,"version":"3.50.1"},"reference-count":49,"publisher":"Springer Science and Business Media LLC","issue":"7969","license":[{"start":{"date-parts":[[2023,7,12]],"date-time":"2023-07-12T00:00:00Z","timestamp":1689120000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,7,12]],"date-time":"2023-07-12T00:00:00Z","timestamp":1689120000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Nature"],"published-print":{"date-parts":[[2023,7,13]]},"DOI":"10.1038\/s41586-023-06095-4","type":"journal-article","created":{"date-parts":[[2023,7,12]],"date-time":"2023-07-12T16:01:59Z","timestamp":1689177719000},"page":"282-287","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":65,"title":["Quantum-enhanced Markov chain Monte Carlo"],"prefix":"10.1038","volume":"619","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1292-9007","authenticated-orcid":false,"given":"David","family":"Layden","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8982-5169","authenticated-orcid":false,"given":"Guglielmo","family":"Mazzola","sequence":"additional","affiliation":[]},{"given":"Ryan V.","family":"Mishmash","sequence":"additional","affiliation":[]},{"given":"Mario","family":"Motta","sequence":"additional","affiliation":[]},{"given":"Pawel","family":"Wocjan","sequence":"additional","affiliation":[]},{"given":"Jin-Sung","family":"Kim","sequence":"additional","affiliation":[]},{"given":"Sarah","family":"Sheldon","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,7,12]]},"reference":[{"key":"6095_CR1","doi-asserted-by":"publisher","first-page":"505","DOI":"10.1038\/s41586-019-1666-5","volume":"574","author":"F Arute","year":"2019","unstructured":"Arute, F. et al. Quantum supremacy using a programmable superconducting processor. Nature 574, 505\u2013510 (2019).","journal-title":"Nature"},{"key":"6095_CR2","doi-asserted-by":"publisher","first-page":"180501","DOI":"10.1103\/PhysRevLett.127.180501","volume":"127","author":"Y Wu","year":"2021","unstructured":"Wu, Y. et al. Strong quantum computational advantage using a superconducting quantum processor. Phys. Rev. Lett. 127, 180501 (2021).","journal-title":"Phys. Rev. Lett."},{"key":"6095_CR3","doi-asserted-by":"publisher","first-page":"180502","DOI":"10.1103\/PhysRevLett.127.180502","volume":"127","author":"H-S Zhong","year":"2021","unstructured":"Zhong, H.-S. et al. Phase-programmable Gaussian boson sampling using stimulated squeezed light. Phys. Rev. Lett. 127, 180502 (2021).","journal-title":"Phys. Rev. Lett."},{"key":"6095_CR4","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1109\/MCISE.2000.814652","volume":"2","author":"J Dongarra","year":"2000","unstructured":"Dongarra, J. & Sullivan, F. Guest editors\u2019 introduction to the top 10 algorithms. Comput. Sci. Eng. 2, 22\u201323 (2000).","journal-title":"Comput. Sci. Eng."},{"key":"6095_CR5","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1207\/s15516709cog0901_7","volume":"9","author":"DH Ackley","year":"1985","unstructured":"Ackley, D. H., Hinton, G. E. & Sejnowski, T. J. A learning algorithm for Boltzmann machines. Cogn. Sci. 9, 147\u2013169 (1985).","journal-title":"Cogn. Sci."},{"key":"6095_CR6","unstructured":"Huang, K. Statistical Mechanics (Wiley, 2008)."},{"key":"6095_CR7","doi-asserted-by":"publisher","first-page":"671","DOI":"10.1126\/science.220.4598.671","volume":"220","author":"S Kirkpatrick","year":"1983","unstructured":"Kirkpatrick, S., Gelatt, C. D. & Vecchi, M. P. Optimization by simulated annealing. Science 220, 671\u2013680 (1983).","journal-title":"Science"},{"key":"6095_CR8","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1007\/BF02980577","volume":"31","author":"E Ising","year":"1925","unstructured":"Ising, E. Beitrag zur Theorie des Ferromagnetismus. Z. Phys. 31, 253\u2013258 (1925).","journal-title":"Z. Phys."},{"key":"6095_CR9","doi-asserted-by":"publisher","first-page":"5","DOI":"10.3389\/fphy.2014.00005","volume":"2","author":"A Lucas","year":"2014","unstructured":"& Lucas, A. Ising formulations of many NP problems. Front. Phys. 2, 5 (2014).","journal-title":"Front. Phys."},{"key":"6095_CR10","doi-asserted-by":"publisher","first-page":"3241","DOI":"10.1088\/0305-4470\/15\/10\/028","volume":"15","author":"F Barahona","year":"1982","unstructured":"Barahona, F. On the computational complexity of Ising spin glass models. J. Phys. A 15, 3241\u20133253 (1982).","journal-title":"J. Phys. A"},{"key":"6095_CR11","doi-asserted-by":"crossref","unstructured":"Levin, D. and Peres, Y. Markov Chains and Mixing Times (American Mathematical Society, 2017).","DOI":"10.1090\/mbk\/107"},{"key":"6095_CR12","first-page":"1087","volume":"21","author":"N Metropolis","year":"1953","unstructured":"Metropolis, N., Rosenbluth, A. W., Rosenbluth, M. N., Teller, A. H. & Teller, E. Equation of state calculations by fast computing machines. J. Comp. Phys. 21, 1087\u20131092 (1953).","journal-title":"J. Comp. Phys."},{"key":"6095_CR13","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, 97\u2013109 (1970).","journal-title":"Biometrika"},{"key":"6095_CR14","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1023\/A:1020281327116","volume":"50","author":"C Andrieu","year":"2003","unstructured":"Andrieu, C., de Freitas, N., Doucet, A. & Jordan, M. I. An introduction to MCMC for machine learning. Mach. Learn. 50, 5\u201343 (2003).","journal-title":"Mach. Learn."},{"key":"6095_CR15","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1103\/PhysRevLett.58.86","volume":"58","author":"RH Swendsen","year":"1987","unstructured":"Swendsen, R. H. & Wang, J.-S. Nonuniversal critical dynamics in Monte Carlo simulations. Phys. Rev. Lett. 58, 86\u201388 (1987).","journal-title":"Phys. Rev. Lett."},{"key":"6095_CR16","doi-asserted-by":"publisher","first-page":"361","DOI":"10.1103\/PhysRevLett.62.361","volume":"62","author":"U Wolff","year":"1989","unstructured":"Wolff, U. Collective Monte Carlo updating for spin systems. Phys. Rev. Lett. 62, 361\u2013364 (1989).","journal-title":"Phys. Rev. Lett."},{"key":"6095_CR17","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, 479\u2013484 (2001).","journal-title":"Eur. Phys. J. B"},{"key":"6095_CR18","doi-asserted-by":"publisher","first-page":"077201","DOI":"10.1103\/PhysRevLett.115.077201","volume":"115","author":"Z Zhu","year":"2015","unstructured":"Zhu, Z., Ochoa, A. J. & Katzgraber, H. G. Efficient cluster algorithm for spin glasses in any space dimension. Phys. Rev. Lett. 115, 077201 (2015).","journal-title":"Phys. Rev. Lett."},{"key":"6095_CR19","unstructured":"Goodfellow, I., Bengio, Y. & Courville, A. Deep Learning (MIT Press, 2016)."},{"key":"6095_CR20","doi-asserted-by":"publisher","first-page":"123022","DOI":"10.1088\/1367-2630\/ab5ca2","volume":"21","author":"A Callison","year":"2019","unstructured":"Callison, A., Chancellor, N., Mintert, F. & Kendon, V. Finding spin glass ground states using quantum walks. New J. Phys. 21, 123022 (2019).","journal-title":"New J. Phys."},{"key":"6095_CR21","doi-asserted-by":"publisher","first-page":"1073","DOI":"10.1126\/science.273.5278.1073","volume":"273","author":"S Lloyd","year":"1996","unstructured":"Lloyd, S. Universal quantum simulators. Science 273, 1073\u20131078 (1996).","journal-title":"Science"},{"key":"6095_CR22","doi-asserted-by":"publisher","unstructured":"Anis Sajid, M. et al. Qiskit: An open-source framework for quantum computing https:\/\/doi.org\/10.5281\/zenodo.2573505 (2021).","DOI":"10.5281\/zenodo.2573505"},{"key":"6095_CR23","doi-asserted-by":"publisher","first-page":"150","DOI":"10.1119\/1.3247985","volume":"78","author":"V Ambegaokar","year":"2010","unstructured":"Ambegaokar, V. & Troyer, M. Estimating errors reliably in Monte Carlo simulations of the Ehrenfest model. Am. J. Phys. 78, 150\u2013157 (2010).","journal-title":"Am. J. Phys."},{"key":"6095_CR24","unstructured":"Szegedy, M. in 45th Annual IEEE Symposium on Foundations of Computer Science 32\u201341 (IEEE, 2004)."},{"key":"6095_CR25","doi-asserted-by":"publisher","first-page":"042306","DOI":"10.1103\/PhysRevA.76.042306","volume":"76","author":"PC Richter","year":"2007","unstructured":"Richter, P. C. Quantum speedup of classical mixing processes. Phys. Rev. A 76, 042306 (2007).","journal-title":"Phys. Rev. A"},{"key":"6095_CR26","doi-asserted-by":"publisher","first-page":"130504","DOI":"10.1103\/PhysRevLett.101.130504","volume":"101","author":"RD Somma","year":"2008","unstructured":"Somma, R. D., Boixo, S., Barnum, H. & Knill, E. Quantum simulations of classical annealing processes. Phys. Rev. Lett. 101, 130504 (2008).","journal-title":"Phys. Rev. Lett."},{"key":"6095_CR27","doi-asserted-by":"publisher","first-page":"042336","DOI":"10.1103\/PhysRevA.78.042336","volume":"78","author":"P Wocjan","year":"2008","unstructured":"Wocjan, P. & Abeyesinghe, A. Speedup via quantum sampling. Phys. Rev. A 78, 042336 (2008).","journal-title":"Phys. Rev. A"},{"key":"6095_CR28","doi-asserted-by":"crossref","unstructured":"Harrow, A. W. & Wei, A. Y. in Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms 193\u2013212 (SIAM, 2020).","DOI":"10.1137\/1.9781611975994.12"},{"key":"6095_CR29","doi-asserted-by":"publisher","first-page":"287","DOI":"10.22331\/q-2020-06-29-287","volume":"4","author":"J Lemieux","year":"2020","unstructured":"Lemieux, J., Heim, B., Poulin, D., Svore, K. & Troyer, M. Efficient quantum walk circuits for Metropolis-Hastings algorithm. Quantum 4, 287 (2020).","journal-title":"Quantum"},{"key":"6095_CR30","doi-asserted-by":"crossref","unstructured":"Arunachalam, S., Havlicek, V., Nannicini, G., Temme, K. & Wocjan, P. in 2021 IEEE International Conference on Quantum Computing and Engineering (QCE) 112\u2013122 (IEEE, 2021).","DOI":"10.1109\/QCE52317.2021.00027"},{"key":"6095_CR31","unstructured":"Dumoulin, V., Goodfellow, I. J., Courville, A. & Bengio, Y. in Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence 1199\u20131205 (AAAI Press, 2014)."},{"key":"6095_CR32","doi-asserted-by":"publisher","first-page":"022308","DOI":"10.1103\/PhysRevA.94.022308","volume":"94","author":"M Benedetti","year":"2016","unstructured":"Benedetti, M., Realpe-G\u00f3mez, J., Biswas, R. & Perdomo-Ortiz, A. Estimation of effective temperatures in quantum annealers for sampling applications: a case study with possible applications in deep learning. Phys. Rev. A 94, 022308 (2016).","journal-title":"Phys. Rev. A"},{"key":"6095_CR33","doi-asserted-by":"publisher","first-page":"044046","DOI":"10.1103\/PhysRevApplied.17.044046","volume":"17","author":"J Nelson","year":"2022","unstructured":"Nelson, J., Vuffray, M., Lokhov, A. Y., Albash, T. & Coffrin, C. High-quality thermal Gibbs sampling with quantum annealing hardware. Phys. Rev. Appl. 17, 044046 (2022).","journal-title":"Phys. Rev. Appl."},{"key":"6095_CR34","doi-asserted-by":"publisher","first-page":"100504","DOI":"10.1103\/PhysRevLett.127.100504","volume":"127","author":"DS Wild","year":"2021","unstructured":"Wild, D. S., Sels, D., Pichler, H., Zanoci, C. & Lukin, M. D. Quantum sampling algorithms for near-term devices. Phys. Rev. Lett. 127, 100504 (2021).","journal-title":"Phys. Rev. Lett."},{"key":"6095_CR35","doi-asserted-by":"publisher","first-page":"032602","DOI":"10.1103\/PhysRevA.104.032602","volume":"104","author":"DS Wild","year":"2021","unstructured":"Wild, D. S., Sels, D., Pichler, H., Zanoci, C. & Lukin, M. D. Quantum sampling algorithms, phase transitions, and computational complexity. Phys. Rev. A 104, 032602 (2021).","journal-title":"Phys. Rev. A"},{"key":"6095_CR36","doi-asserted-by":"publisher","first-page":"625","DOI":"10.1038\/s42254-021-00348-9","volume":"3","author":"M Cerezo","year":"2021","unstructured":"Cerezo, M. et al. Variational quantum algorithms. Nat. Rev. Phys. 3, 625\u2013644 (2021).","journal-title":"Nat. Rev. Phys."},{"key":"6095_CR37","doi-asserted-by":"publisher","first-page":"015004","DOI":"10.1103\/RevModPhys.94.015004","volume":"94","author":"K Bharti","year":"2022","unstructured":"Bharti, K. et al. Noisy intermediate-scale quantum algorithms. Rev. Mod. Phys. 94, 015004 (2022).","journal-title":"Rev. Mod. Phys."},{"key":"6095_CR38","doi-asserted-by":"publisher","first-page":"010103","DOI":"10.1103\/PRXQuantum.2.010103","volume":"2","author":"R Babbush","year":"2021","unstructured":"Babbush, R. et al. Focus beyond quadratic speedups for error-corrected quantum advantage. PRX Quantum 2, 010103 (2021).","journal-title":"PRX Quantum"},{"key":"6095_CR39","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).","journal-title":"Phys. Rev. Lett."},{"key":"6095_CR40","doi-asserted-by":"publisher","first-page":"224201","DOI":"10.1103\/PhysRevB.97.224201","volume":"97","author":"CL Baldwin","year":"2018","unstructured":"Baldwin, C. L. & Laumann, C. R. Quantum algorithm for energy matching in hard optimization problems. Phys. Rev. B 97, 224201 (2018).","journal-title":"Phys. Rev. B"},{"key":"6095_CR41","first-page":"011017","volume":"10","author":"VN Smelyanskiy","year":"2020","unstructured":"Smelyanskiy, V. N. et al. Nonergodic delocalized states for efficient population transfer within a narrow band of the energy landscape. Phys. Rev. X 10, 011017 (2020).","journal-title":"Phys. Rev. X"},{"key":"6095_CR42","unstructured":"Smelyanskiy, V. N., Kechedzhi, K., Boixo, S., Neven, H. & Altshuler, B. Intermittency of dynamical phases in a quantum spin glass. Preprint at https:\/\/arxiv.org\/abs\/1907.01609 (2019)."},{"key":"6095_CR43","doi-asserted-by":"crossref","unstructured":"Brooks, S., Gelman, A., Jones, G. & Meng, X.-L. Handbook of Markov Chain Monte Carlo (CRC Press, 2011).","DOI":"10.1201\/b10905"},{"key":"6095_CR44","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1007\/s11222-008-9110-y","volume":"18","author":"C Andrieu","year":"2008","unstructured":"Andrieu, C. & Thoms, J. A tutorial on adaptive MCMC. Stat. Comput. 18, 343\u2013373 (2008).","journal-title":"Stat. Comput."},{"key":"6095_CR45","doi-asserted-by":"publisher","first-page":"022431","DOI":"10.1103\/PhysRevA.104.022431","volume":"104","author":"G Mazzola","year":"2021","unstructured":"Mazzola, G. Sampling, rates, and reaction currents through reverse stochastic quantization on quantum computers. Phys. Rev. A 104, 022431 (2021).","journal-title":"Phys. Rev. A"},{"key":"6095_CR46","doi-asserted-by":"publisher","first-page":"1792","DOI":"10.1103\/PhysRevLett.35.1792","volume":"35","author":"D Sherrington","year":"1975","unstructured":"Sherrington, D. & Kirkpatrick, S. Solvable model of a spin-glass. Phys. Rev. Lett. 35, 1792\u20131796 (1975).","journal-title":"Phys. Rev. Lett."},{"key":"6095_CR47","doi-asserted-by":"publisher","first-page":"601","DOI":"10.1063\/1.526596","volume":"26","author":"M Suzuki","year":"1985","unstructured":"Suzuki, M. Decomposition formulas of exponential operators and Lie exponentials with some applications to quantum mechanics and statistical physics. J. Math. Phys. 26, 601\u2013612 (1985).","journal-title":"J. Math. Phys."},{"key":"6095_CR48","doi-asserted-by":"publisher","first-page":"052325","DOI":"10.1103\/PhysRevA.94.052325","volume":"94","author":"JJ Wallman","year":"2016","unstructured":"Wallman, J. J. & Emerson, J. Noise tailoring for scalable quantum computation via randomized compiling. Phys. Rev. A 94, 052325 (2016).","journal-title":"Phys. Rev. A"},{"key":"6095_CR49","doi-asserted-by":"publisher","first-page":"043088","DOI":"10.1103\/PhysRevResearch.3.043088","volume":"3","author":"N Earnest","year":"2021","unstructured":"Earnest, N., Tornow, C. & Egger, D. J. Pulse-efficient circuit transpilation for quantum applications on cross-resonance-based hardware. Phys. Rev. Res. 3, 043088 (2021).","journal-title":"Phys. Rev. Res."}],"container-title":["Nature"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.nature.com\/articles\/s41586-023-06095-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.nature.com\/articles\/s41586-023-06095-4","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.nature.com\/articles\/s41586-023-06095-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,24]],"date-time":"2024-10-24T01:03:09Z","timestamp":1729731789000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.nature.com\/articles\/s41586-023-06095-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,7,12]]},"references-count":49,"journal-issue":{"issue":"7969","published-print":{"date-parts":[[2023,7,13]]}},"alternative-id":["6095"],"URL":"https:\/\/doi.org\/10.1038\/s41586-023-06095-4","relation":{},"ISSN":["0028-0836","1476-4687"],"issn-type":[{"value":"0028-0836","type":"print"},{"value":"1476-4687","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,7,12]]},"assertion":[{"value":"6 May 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 April 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 July 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Elements of this algorithm are included in a patent filed by the International Business Machines Corporation with the US Patent and Trademark Office, for which D.L., R.V.M. and P.W. are inventors.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}]}}