Arute, F. et al. Quantum supremacy using a programmable superconducting processor. Nature 574, 505–510 (2019).
Google Scholar
Wu, Y. et al. Strong quantum computational advantage using a superconducting quantum processor. Phys. Rev. Lett. 127, 180501 (2021).
Google Scholar
Zhong, H.-S. et al. Phase-programmable Gaussian boson sampling using stimulated squeezed light. Phys. Rev. Lett. 127, 180502 (2021).
Google Scholar
Dongarra, J. & Sullivan, F. Guest editors’ introduction to the top 10 algorithms. Comput. Sci. Eng. 2, 22–23 (2000).
Google Scholar
Ackley, D. H., Hinton, G. E. & Sejnowski, T. J. A learning algorithm for Boltzmann machines. Cogn. Sci. 9, 147–169 (1985).
Google Scholar
Huang, K. Statistical Mechanics (Wiley, 2008).
Kirkpatrick, S., Gelatt, C. D. & Vecchi, M. P. Optimization by simulated annealing. Science 220, 671–680 (1983).
Google Scholar
Ising, E. Beitrag zur Theorie des Ferromagnetismus. Z. Phys. 31, 253–258 (1925).
Google Scholar
& Lucas, A. Ising formulations of many NP problems. Front. Phys. 2, 5 (2014).
Google Scholar
Barahona, F. On the computational complexity of Ising spin glass models. J. Phys. A 15, 3241–3253 (1982).
Google Scholar
Levin, D. and Peres, Y. Markov Chains and Mixing Times (American Mathematical Society, 2017).
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–1092 (1953).
Google Scholar
Hastings, W. K. Monte Carlo sampling methods using Markov chains and their applications. Biometrika 57, 97–109 (1970).
Google Scholar
Andrieu, C., de Freitas, N., Doucet, A. & Jordan, M. I. An introduction to MCMC for machine learning. Mach. Learn. 50, 5–43 (2003).
Google Scholar
Swendsen, R. H. & Wang, J.-S. Nonuniversal critical dynamics in Monte Carlo simulations. Phys. Rev. Lett. 58, 86–88 (1987).
Google Scholar
Wolff, U. Collective Monte Carlo updating for spin systems. Phys. Rev. Lett. 62, 361–364 (1989).
Google Scholar
Houdayer, J. A cluster Monte Carlo algorithm for 2-dimensional spin glasses. Eur. Phys. J. B 22, 479–484 (2001).
Google Scholar
Zhu, Z., Ochoa, A. J. & Katzgraber, H. G. Efficient cluster algorithm for spin glasses in any space dimension. Phys. Rev. Lett. 115, 077201 (2015).
Google Scholar
Goodfellow, I., Bengio, Y. & Courville, A. Deep Learning (MIT Press, 2016).
Callison, A., Chancellor, N., Mintert, F. & Kendon, V. Finding spin glass ground states using quantum walks. New J. Phys. 21, 123022 (2019).
Google Scholar
Lloyd, S. Universal quantum simulators. Science 273, 1073–1078 (1996).
Google Scholar
Anis Sajid, M. et al. Qiskit: An open-source framework for quantum computing https://doi.org/10.5281/zenodo.2573505 (2021).
Ambegaokar, V. & Troyer, M. Estimating errors reliably in Monte Carlo simulations of the Ehrenfest model. Am. J. Phys. 78, 150–157 (2010).
Google Scholar
Szegedy, M. in 45th Annual IEEE Symposium on Foundations of Computer Science 32–41 (IEEE, 2004).
Richter, P. C. Quantum speedup of classical mixing processes. Phys. Rev. A 76, 042306 (2007).
Google Scholar
Somma, R. D., Boixo, S., Barnum, H. & Knill, E. Quantum simulations of classical annealing processes. Phys. Rev. Lett. 101, 130504 (2008).
Google Scholar
Wocjan, P. & Abeyesinghe, A. Speedup via quantum sampling. Phys. Rev. A 78, 042336 (2008).
Google Scholar
Harrow, A. W. & Wei, A. Y. in Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms 193–212 (SIAM, 2020).
Lemieux, J., Heim, B., Poulin, D., Svore, K. & Troyer, M. Efficient quantum walk circuits for Metropolis-Hastings algorithm. Quantum 4, 287 (2020).
Google Scholar
Arunachalam, S., Havlicek, V., Nannicini, G., Temme, K. & Wocjan, P. in 2021 IEEE International Conference on Quantum Computing and Engineering (QCE) 112–122 (IEEE, 2021).
Dumoulin, V., Goodfellow, I. J., Courville, A. & Bengio, Y. in Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence 1199–1205 (AAAI Press, 2014).
Benedetti, M., Realpe-Gómez, 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).
Google Scholar
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).
Google Scholar
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).
Google Scholar
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).
Google Scholar
Cerezo, M. et al. Variational quantum algorithms. Nat. Rev. Phys. 3, 625–644 (2021).
Google Scholar
Bharti, K. et al. Noisy intermediate-scale quantum algorithms. Rev. Mod. Phys. 94, 015004 (2022).
Google Scholar
Babbush, R. et al. Focus beyond quadratic speedups for error-corrected quantum advantage. PRX Quantum 2, 010103 (2021).
Google Scholar
Swendsen, R. H. & Wang, J.-S. Replica Monte Carlo simulation of spin-glasses. Phys. Rev. Lett. 57, 2607–2609 (1986).
Google Scholar
Baldwin, C. L. & Laumann, C. R. Quantum algorithm for energy matching in hard optimization problems. Phys. Rev. B 97, 224201 (2018).
Google Scholar
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).
Google Scholar
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).
Brooks, S., Gelman, A., Jones, G. & Meng, X.-L. Handbook of Markov Chain Monte Carlo (CRC Press, 2011).
Andrieu, C. & Thoms, J. A tutorial on adaptive MCMC. Stat. Comput. 18, 343–373 (2008).
Google Scholar
Mazzola, G. Sampling, rates, and reaction currents through reverse stochastic quantization on quantum computers. Phys. Rev. A 104, 022431 (2021).
Google Scholar
Sherrington, D. & Kirkpatrick, S. Solvable model of a spin-glass. Phys. Rev. Lett. 35, 1792–1796 (1975).
Google Scholar
Suzuki, M. Decomposition formulas of exponential operators and Lie exponentials with some applications to quantum mechanics and statistical physics. J. Math. Phys. 26, 601–612 (1985).
Google Scholar
Wallman, J. J. & Emerson, J. Noise tailoring for scalable quantum computation via randomized compiling. Phys. Rev. A 94, 052325 (2016).
Google Scholar
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).
Google Scholar