Quantum-enhanced Markov chain Monte Carlo – Nature

0
45


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

    Article 
    CAS 
    PubMed 
    ADS 

    Google Scholar
     

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

    Article 
    CAS 
    PubMed 
    ADS 

    Google Scholar
     

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

    Article 
    CAS 
    PubMed 
    ADS 

    Google Scholar
     

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

    Article 

    Google Scholar
     

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

    Article 

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

    Article 
    MathSciNet 
    CAS 
    PubMed 
    MATH 
    ADS 

    Google Scholar
     

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

    Article 
    CAS 
    MATH 
    ADS 

    Google Scholar
     

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

    Article 

    Google Scholar
     

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

    Article 
    MathSciNet 
    ADS 

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

    CAS 
    MATH 

    Google Scholar
     

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

    Article 
    MathSciNet 
    MATH 

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

    Article 
    MATH 

    Google Scholar
     

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

    Article 
    CAS 
    PubMed 
    ADS 

    Google Scholar
     

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

    Article 
    CAS 
    PubMed 
    ADS 

    Google Scholar
     

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

    Article 
    CAS 
    ADS 

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

    Article 
    PubMed 
    ADS 

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

    Article 
    MathSciNet 

    Google Scholar
     

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

    Article 
    MathSciNet 
    CAS 
    PubMed 
    MATH 
    ADS 

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

    Article 
    ADS 

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

    Article 
    ADS 

    Google Scholar
     

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

    Article 
    CAS 
    PubMed 
    ADS 

    Google Scholar
     

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

    Article 
    ADS 

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

    Article 

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

    Article 
    ADS 

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

    Article 
    CAS 
    ADS 

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

    Article 
    CAS 
    PubMed 
    ADS 

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

    Article 
    MathSciNet 
    CAS 
    ADS 

    Google Scholar
     

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

    Article 

    Google Scholar
     

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

    Article 
    MathSciNet 
    CAS 
    ADS 

    Google Scholar
     

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

    Article 

    Google Scholar
     

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

    Article 
    MathSciNet 
    CAS 
    PubMed 
    ADS 

    Google Scholar
     

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

    Article 
    CAS 
    ADS 

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

    CAS 

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

    Article 
    MathSciNet 

    Google Scholar
     

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

    Article 
    MathSciNet 
    CAS 
    ADS 

    Google Scholar
     

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

    Article 
    ADS 

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

    Article 
    MathSciNet 
    CAS 
    MATH 
    ADS 

    Google Scholar
     

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

    Article 
    ADS 

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

    Article 
    CAS 

    Google Scholar
     



  • Source link