Arute, F. et al. Quantum supremacy using a programmable superconducting processor. Nature 574, 505–510 (2019).
Wu, Y. et al. Strong quantum computational advantage using a superconducting quantum processor. Phys. Rev. Lett. 127, 180501 (2021).
Zhong, H.-S. et al. Phase-programmable Gaussian boson sampling using stimulated squeezed light. Phys. Rev. Lett. 127, 180502 (2021).
Dongarra, J. & Sullivan, F. Guest editors’ introduction to the top 10 algorithms. Comput. Sci. Eng. 2, 22–23 (2000).
Ackley, D. H., Hinton, G. E. & Sejnowski, T. J. A learning algorithm for Boltzmann machines. Cogn. Sci. 9, 147–169 (1985).
Huang, K. Statistical Mechanics (Wiley, 2008).
Kirkpatrick, S., Gelatt, C. D. & Vecchi, M. P. Optimization by simulated annealing. Science 220, 671–680 (1983).
Ising, E. Beitrag zur Theorie des Ferromagnetismus. Z. Phys. 31, 253–258 (1925).
& Lucas, A. Ising formulations of many NP problems. Front. Phys. 2, 5 (2014).
Barahona, F. On the computational complexity of Ising spin glass models. J. Phys. A 15, 3241–3253 (1982).
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).
Hastings, W. K. Monte Carlo sampling methods using Markov chains and their applications. Biometrika 57, 97–109 (1970).
Andrieu, C., de Freitas, N., Doucet, A. & Jordan, M. I. An introduction to MCMC for machine learning. Mach. Learn. 50, 5–43 (2003).
Swendsen, R. H. & Wang, J.-S. Nonuniversal critical dynamics in Monte Carlo simulations. Phys. Rev. Lett. 58, 86–88 (1987).
Wolff, U. Collective Monte Carlo updating for spin systems. Phys. Rev. Lett. 62, 361–364 (1989).
Houdayer, J. A cluster Monte Carlo algorithm for 2-dimensional spin glasses. Eur. Phys. J. B 22, 479–484 (2001).
Zhu, Z., Ochoa, A. J. & Katzgraber, H. G. Efficient cluster algorithm for spin glasses in any space dimension. Phys. Rev. Lett. 115, 077201 (2015).
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).
Lloyd, S. Universal quantum simulators. Science 273, 1073–1078 (1996).
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).
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).
Somma, R. D., Boixo, S., Barnum, H. & Knill, E. Quantum simulations of classical annealing processes. Phys. Rev. Lett. 101, 130504 (2008).
Wocjan, P. & Abeyesinghe, A. Speedup via quantum sampling. Phys. Rev. A 78, 042336 (2008).
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).
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).
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).
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).
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).
Cerezo, M. et al. Variational quantum algorithms. Nat. Rev. Phys. 3, 625–644 (2021).
Bharti, K. et al. Noisy intermediate-scale quantum algorithms. Rev. Mod. Phys. 94, 015004 (2022).
Babbush, R. et al. Focus beyond quadratic speedups for error-corrected quantum advantage. PRX Quantum 2, 010103 (2021).
Swendsen, R. H. & Wang, J.-S. Replica Monte Carlo simulation of spin-glasses. Phys. Rev. Lett. 57, 2607–2609 (1986).
Baldwin, C. L. & Laumann, C. R. Quantum algorithm for energy matching in hard optimization problems. Phys. Rev. B 97, 224201 (2018).
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).
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).
Mazzola, G. Sampling, rates, and reaction currents through reverse stochastic quantization on quantum computers. Phys. Rev. A 104, 022431 (2021).
Sherrington, D. & Kirkpatrick, S. Solvable model of a spin-glass. Phys. Rev. Lett. 35, 1792–1796 (1975).
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).
Wallman, J. J. & Emerson, J. Noise tailoring for scalable quantum computation via randomized compiling. Phys. Rev. A 94, 052325 (2016).
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).
Leave a comment