Quantum-enhanced Markov chain Monte Carlo (2024)

1. Arute, F. et al. Quantum supremacy using a programmable superconducting processor. Nature 574, 505–510 (2019).

   Article ADS CAS PubMed Google Scholar

2. Wu, Y. et al. Strong quantum computational advantage using a superconducting quantum processor. Phys. Rev. Lett. 127, 180501 (2021).

   Article ADS CAS PubMed Google Scholar

3. Zhong, H.-S. et al. Phase-programmable Gaussian boson sampling using stimulated squeezed light. Phys. Rev. Lett. 127, 180502 (2021).

   Article ADS CAS PubMed Google Scholar

4. Dongarra, J. & Sullivan, F. Guest editors’ introduction to the top 10 algorithms. Comput. Sci. Eng. 2, 22–23 (2000).

   Article Google Scholar

5. Ackley, D. H., Hinton, G. E. & Sejnowski, T. J. A learning algorithm for Boltzmann machines. Cogn. Sci. 9, 147–169 (1985).

   Article Google Scholar

6. Huang, K. Statistical Mechanics (Wiley, 2008).

7. Kirkpatrick, S., Gelatt, C. D. & Vecchi, M. P. Optimization by simulated annealing. Science 220, 671–680 (1983).

   Article ADS MathSciNet CAS PubMed MATH Google Scholar

8. Ising, E. Beitrag zur Theorie des Ferromagnetismus. Z. Phys. 31, 253–258 (1925).

   Article ADS CAS MATH Google Scholar

9. & Lucas, A. Ising formulations of many NP problems. Front. Phys. 2, 5 (2014).

   Article Google Scholar

10. Barahona, F. On the computational complexity of Ising spin glass models. J. Phys. A 15, 3241–3253 (1982).

    Article ADS MathSciNet Google Scholar

11. Levin, D. and Peres, Y. Markov Chains and Mixing Times (American Mathematical Society, 2017).

    See Also

    Monte Carlo Markov Chain (MCMC) explainedChapter 17 Introduction to Markov Chain Monte Carlo (MCMC) Simulation | An Introduction to Bayesian Reasoning and MethodsA Zero-Math Introduction to Markov Chain Monte Carlo MethodsMarkov chain Monte Carlo (MCMC) Sampling, Part 1: The Basics

12. 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).

    CAS MATH Google Scholar

13. Hastings, W. K. Monte Carlo sampling methods using Markov chains and their applications. Biometrika 57, 97–109 (1970).

    Article MathSciNet MATH Google Scholar

14. Andrieu, C., de Freitas, N., Doucet, A. & Jordan, M. I. An introduction to MCMC for machine learning. Mach. Learn. 50, 5–43 (2003).

    Article MATH Google Scholar

15. Swendsen, R. H. & Wang, J.-S. Nonuniversal critical dynamics in Monte Carlo simulations. Phys. Rev. Lett. 58, 86–88 (1987).

    Article ADS CAS PubMed Google Scholar

16. Wolff, U. Collective Monte Carlo updating for spin systems. Phys. Rev. Lett. 62, 361–364 (1989).

    Article ADS CAS PubMed Google Scholar

17. Houdayer, J. A cluster Monte Carlo algorithm for 2-dimensional spin glasses. Eur. Phys. J. B 22, 479–484 (2001).

    Article ADS CAS Google Scholar

18. Zhu, Z., Ochoa, A. J. & Katzgraber, H. G. Efficient cluster algorithm for spin glasses in any space dimension. Phys. Rev. Lett. 115, 077201 (2015).

    Article ADS PubMed Google Scholar

19. Goodfellow, I., Bengio, Y. & Courville, A. Deep Learning (MIT Press, 2016).

20. Callison, A., Chancellor, N., Mintert, F. & Kendon, V. Finding spin glass ground states using quantum walks. New J. Phys. 21, 123022 (2019).

    Article MathSciNet Google Scholar

21. Lloyd, S. Universal quantum simulators. Science 273, 1073–1078 (1996).

    Article ADS MathSciNet CAS PubMed MATH Google Scholar

22. Anis Sajid, M. et al. Qiskit: An open-source framework for quantum computing https://doi.org/10.5281/zenodo.2573505 (2021).

23. Ambegaokar, V. & Troyer, M. Estimating errors reliably in Monte Carlo simulations of the Ehrenfest model. Am. J. Phys. 78, 150–157 (2010).

    Article ADS Google Scholar

24. Szegedy, M. in 45th Annual IEEE Symposium on Foundations of Computer Science 32–41 (IEEE, 2004).

    See Also

    A Beginner's Guide to Markov Chain Monte Carlo, Machine Learning & Markov Blankets

25. Richter, P. C. Quantum speedup of classical mixing processes. Phys. Rev. A 76, 042306 (2007).

    Article ADS Google Scholar

26. Somma, R. D., Boixo, S., Barnum, H. & Knill, E. Quantum simulations of classical annealing processes. Phys. Rev. Lett. 101, 130504 (2008).

    Article ADS CAS PubMed Google Scholar

27. Wocjan, P. & Abeyesinghe, A. Speedup via quantum sampling. Phys. Rev. A 78, 042336 (2008).

    Article ADS Google Scholar

28. Harrow, A. W. & Wei, A. Y. in Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms 193–212 (SIAM, 2020).

29. Lemieux, J., Heim, B., Poulin, D., Svore, K. & Troyer, M. Efficient quantum walk circuits for Metropolis-Hastings algorithm. Quantum 4, 287 (2020).

    Article Google Scholar

30. 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).

31. 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).

32. 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).

    Article ADS Google Scholar

33. 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).

    Article ADS CAS Google Scholar

34. 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).

    Article ADS CAS PubMed Google Scholar

35. 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).

    Article ADS MathSciNet CAS Google Scholar

36. Cerezo, M. et al. Variational quantum algorithms. Nat. Rev. Phys. 3, 625–644 (2021).

    Article Google Scholar

37. Bharti, K. et al. Noisy intermediate-scale quantum algorithms. Rev. Mod. Phys. 94, 015004 (2022).

    Article ADS MathSciNet CAS Google Scholar

38. Babbush, R. et al. Focus beyond quadratic speedups for error-corrected quantum advantage. PRX Quantum 2, 010103 (2021).

    Article Google Scholar

39. Swendsen, R. H. & Wang, J.-S. Replica Monte Carlo simulation of spin-glasses. Phys. Rev. Lett. 57, 2607–2609 (1986).

    Article ADS MathSciNet CAS PubMed Google Scholar

40. Baldwin, C. L. & Laumann, C. R. Quantum algorithm for energy matching in hard optimization problems. Phys. Rev. B 97, 224201 (2018).

    Article ADS CAS Google Scholar

41. 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).

    CAS Google Scholar

42. 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).

43. Brooks, S., Gelman, A., Jones, G. & Meng, X.-L. Handbook of Markov Chain Monte Carlo (CRC Press, 2011).

44. Andrieu, C. & Thoms, J. A tutorial on adaptive MCMC. Stat. Comput. 18, 343–373 (2008).

    Article MathSciNet Google Scholar

45. Mazzola, G. Sampling, rates, and reaction currents through reverse stochastic quantization on quantum computers. Phys. Rev. A 104, 022431 (2021).

    Article ADS MathSciNet CAS Google Scholar

46. Sherrington, D. & Kirkpatrick, S. Solvable model of a spin-glass. Phys. Rev. Lett. 35, 1792–1796 (1975).

    Article ADS Google Scholar

47. 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).

    Article ADS MathSciNet CAS MATH Google Scholar

48. Wallman, J. J. & Emerson, J. Noise tailoring for scalable quantum computation via randomized compiling. Phys. Rev. A 94, 052325 (2016).

    Article ADS Google Scholar

49. 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).

    Article CAS Google Scholar

Download references