Faster quantum mixing for slowly evolving sequences of Markov chains

Davide Orsucci; Hans J. Briegel; Vedran Dunjko

doi:10.22331/q-2018-11-09-105

Faster quantum mixing for slowly evolving sequences of Markov chains

Davide Orsucci¹, Hans J. Briegel^1,2, and Vedran Dunjko^1,3,4

¹Institute for Theoretical Physics, University of Innsbruck, Technikerstraße 21a, 6020 Innsbruck, Austria
²Department of Philosophy, University of Konstanz, Fach 17, 78457 Konstanz, Germany
³Max-Planck-Institut für Quantenoptik, Hans-Kopfermann-Str. 1, 85748 Garching, Germany
⁴LIACS, Leiden University, Niels Bohrweg 1, 2333 CA Leiden, The Netherlands

Published:	2018-11-09, volume 2, page 105
Eprint:	arXiv:1503.01334v4
Doi:	https://doi.org/10.22331/q-2018-11-09-105
Citation:	Quantum 2, 105 (2018).

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

Abstract

Markov chain methods are remarkably successful in computational physics, machine learning, and combinatorial optimization. The cost of such methods often reduces to the mixing time, i.e., the time required to reach the steady state of the Markov chain, which scales as $δ^{-1}$, the inverse of the spectral gap. It has long been conjectured that quantum computers offer nearly generic quadratic improvements for mixing problems. However, except in special cases, quantum algorithms achieve a run-time of $\mathcal{O}(\sqrt{δ^{-1}} \sqrt{N})$, which introduces a costly dependence on the Markov chain size $N,$ not present in the classical case. Here, we re-address the problem of mixing of Markov chains when these form a slowly evolving sequence. This setting is akin to the simulated annealing setting and is commonly encountered in physics, material sciences and machine learning. We provide a quantum memory-efficient algorithm with a run-time of $\mathcal{O}(\sqrt{δ^{-1}} \sqrt[4]{N})$, neglecting logarithmic terms, which is an important improvement for large state spaces. Moreover, our algorithms output quantum encodings of distributions, which has advantages over classical outputs. Finally, we discuss the run-time bounds of mixing algorithms and show that, under certain assumptions, our algorithms are optimal.

► BibTeX data

@article{Orsucci2018fasterquantummixing,
  doi = {10.22331/q-2018-11-09-105},
  url = {https://doi.org/10.22331/q-2018-11-09-105},
  title = {Faster quantum mixing for slowly evolving sequences of {M}arkov chains},
  author = {Orsucci, Davide and Briegel, Hans J. and Dunjko, Vedran},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {2},
  pages = {105},
  month = nov,
  year = {2018}
}

► References

[1] Newman, M. E. J. and Barkema, G. T., Monte Carlo Methods in Statistical Physics. Oxford University Press (1999).

[2] Sinclair, A., Algorithms for random generation and counting: a Markov chain approach. Springer (1993).

[3] Bellman, R., A Markovian decision process. Journal of Mathematics and Mechanics 6(5), 679–684 (1957).
https://www.jstor.org/stable/24900506?seq=1#page_scan_tab_contents

[4] Gilks, W. R., Richardson, S. and Spiegelhalter, D. Markov chain Monte Carlo in practice. CRC press (1995).

[5] Hastings, W. K., Monte Carlo sampling methods using Markov chains and their applications. Biometrika 57(1), 97–109 (1970).
https://doi.org/10.1093/biomet/57.1.97

[6] Geman, S. and Geman, D., Stochastic relaxation, Gibbs distributions, and the Bayesian restoration of images. Readings in Computer Vision, 564–584 (1987).
https://doi.org/10.1109/TPAMI.1984.4767596

[7] Martinelli, F., Lectures on Glauber dynamics for discrete spin models. Lectures on probability theory and statistics, Springer, 93–191 (1999).
https://doi.org/10.1007/978-3-540-48115-7_2

[8] Norris, J. R., Markov chains. Cambridge University Press (1998).

[9] Levin, D. A. and Peres, Y., Markov chains and mixing times. American Mathematical Soc. (2017).

[10] Aldous, D., László, L. and Winkler, P., Mixing times for uniformly ergodic Markov chains. Stochastic Processes and their Applications 71(2), 165–182 (1995).
https://doi.org/10.1016/S0304-4149(97)00037-9

[11] Kirkpatrick, S., Gelatt, C. D. and Vecchi, M. P., Optimization by simulated annealing. Science 220(4598), 671–680 (1983).
https://doi.org/10.1126/science.220.4598.671

[12] Van Laarhoven, P. J., and Aarts, E. H., Simulated annealing. Simulated annealing: Theory and applications 37 (1987).
https://doi.org/10.1007/978-94-015-7744-1_2

[13] Richter, P. C., Quantum speedup of classical mixing processes. Phys. Rev. A 76, 042306 (2007) [arXiv:0609204].
https://doi.org/10.1103/PhysRevA.76.042306
arXiv:quant-ph/0609204

[14] Nayak, A. and Vishwanath, A., Quantum walk on the line. arXiv:quant-ph/0010117 (2000).
arXiv:quant-ph/0010117

[15] Ambainis, A., Bach, E., Nayak, A., Vishwanath, A. and Watrous, J., One-dimensional quantum walks. Proceedings of the 33rd Annual ACM Symposium on Theory of Computing, 37–49 (2001).
https://doi.org/10.1145/380752.380757

[16] Aharonov, D., Ambainis, A., Kempe, J. and Vazirani, U., Quantum walks on graphs. Proceedings of the 33rd Annual ACM Symposium on Theory of Computing, 50–59 (2001) [arXiv:0012090].
https://doi.org/10.1145/380752.380758
arXiv:quant-ph/0012090

[17] Richter, P. C., Almost uniform sampling via quantum walks. New J. Phys. 9(72) (2007) [arXiv:0606202].
https://doi.org/10.1088/1367-2630/9/3/072
arXiv:quant-ph/0606202

[18] Dunjko, V. and Briegel, H. J., Quantum mixing of Markov chains for special distributions. New J. Phys. 17(7), 073004 (2015) [arXiv:1502.05511].
https://doi.org/10.1088/1367-2630/17/7/073004
arXiv:1502.05511

[19] Kempe, J., Quantum random walks - an introductory overview. Contemp. Phys. 44(4), 307–327 (2003) [arXiv:0303081].
https://doi.org/10.1080/00107151031000110776
arXiv:quant-ph/0303081

[20] Reitzner, D., Nagaj, D. and Bužek, V., Quantum Walks. Acta Phys. Slovaca 61(6), 603–725 (2011) [arXiv:1207.7283].
https://doi.org/10.2478/v10155-011-0006-6
arXiv:1207.7283

[21] Somma, R. D., Boixo, S., Barnum, H. and Knill, E., Quantum simulations of classical annealing processes. Phys. Rev. Lett. 101, 130504 (2008) [arXiv:0804.1571].
https://doi.org/10.1103/PhysRevLett.101.130504
arXiv:0804.1571

[22] Wocjan, P. and Abeyesinghe, A., Speedup via quantum sampling. Phys. Rev. A 78, 042336 (2008) [arXiv:0804.4259].
https://doi.org/10.1103/PhysRevA.78.042336
arXiv:0804.4259

[23] Wocjan, P., Chiang, C., Nagaj, D. and Abeyesinghe, A., Quantum algorithm for approximating partition functions. Phys. Rev. A 80, 022340 (2009) [arXiv:1405.2749].
https://doi.org/10.1103/PhysRevA.80.022340
arXiv:1405.2749

[24] Childs, A., Quantum information processing in continuous time. Ph. D. Thesis, Massachusetts Institute of Technology (2004).
http://hdl.handle.net/1721.1/16663

[25] Nishimori, H. and Ortiz, G., Elements of phase transitions and critical phenomena. OUP Oxford (2010).

[26] Sutton, R. S. & Barto, A. G. Reinforcement learning: An introduction. MIT Press, Cambridge Massachusetts (1998).

[27] Bishop, C. M., Pattern recognition and machine learning. Springer-Verlag, New York (2016).

[28] Szegedy, M., Quantum speed-up of Markov chain based algorithms. 45th Annual IEEE Symposium on Foundations of Computer Science, 32–41(2004).
https://doi.org/10.1109/FOCS.2004.53

[29] Magniez, F., Nayak, A., Roland, J. and Santha, M., Search via quantum walk. SIAM Journal on Computing 40(1), 142–164 (2011) [arXiv:0608026].
https://doi.org/10.1137/090745854
arXiv:quant-ph/0608026

[30] Kitaev, A. Y., Quantum measurements and the Abelian Stabilizer Problem. arXiv preprint quant-ph/9511026 (1995).
arXiv:quant-ph/9511026

[31] Svore, K. M., Hastings, M. B. and Freedman, M., Faster Phase Estimation. Quantum Information & Computation 14(3-4), 306–328 (2014) [arXiv:1304.0741].
arXiv:1304.0741
https://dl.acm.org/citation.cfm?id=2600515

[32] Wiebe, N. and Granade, C. E., Efficient Bayesian Phase Estimation Phys. Rev. Lett. 117, 010503 (2016) [arXiv:1508.00869].
https://doi.org/10.1103/PhysRevLett.117.010503
arXiv:1508.00869

[33] Grover, L. K., A fast quantum mechanical algorithm for database search. Proceedings of the 28th annual ACM Symposium on the Theory of Computing, 212–219 (1996) [arXiv:9605043].
https://doi.org/10.1145/237814.237866
arXiv:quant-ph/9605043

[34] Brassard, G., Hoyer, P., Mosca, M. and Tapp, A., Quantum Amplitude Amplification and Estimation. Contemporary Mathematics 305, 53–74 (2002) [arXiv:0005055].
https://doi.org/10.1090/conm/305/05215
arXiv:quant-ph/0005055

[35] Grover, L. K., Fixed-Point Quantum Search. Phys. Rev. Lett. 95, 150501 (2005) [arXiv:0503205].
https://doi.org/10.1103/PhysRevLett.95.150501
arXiv:quant-ph/0503205

[36] Yoder, T. J., Low, G. H. and Chuang, I. L., Fixed-Point Quantum Search with an Optimal Number of Queries. Phys. Rev. Lett. 113, 210501 (2014).
https://doi.org/10.1103/PhysRevLett.113.210501

[37] Grover, L. and Rudolph, T., Creating superpositions that correspond to efficiently integrable probability distributions. arXiv preprint quant-ph/0208112 (2002).
arXiv:quant-ph/0208112

[38] Paparo, G. D., Dunjko, V., Makmal, A., Matrin-Delgado, MA. and Briegel, H. J. Quantum speedup for active learning agents. Phys. Rev. X 4, 031002 (2014) [arXiv:1401.4997].
https://doi.org/10.1103/PhysRevX.4.031002
arXiv:1401.4997

[39] Sly, A. Computational transition at the uniqueness threshold. 51st Annual IEEE Symposium on Foundations of Computer Science, 287–296 (2010) [arXiv:1005.5584].
https://doi.org/10.1109/FOCS.2010.34
arXiv:1005.5584

[40] Boyer, M., Brassard, G., Høyer, P. and Tapp, A., Tight bounds on quantum searching. Progress of Physics 46(4-5), 493–505 (1998) [arXiv:9605034].
https://doi.org/10.1002/(SICI)1521-3978(199806)46:4/5<493::AID-PROP493>3.0.CO;2-P
arXiv:quant-ph/9605034

[41] Aharonov, D. and Ta-Shma, A., Adiabatic Quantum State Generation and Statistical Zero Knowledge. Proceedings of the 35th annual ACM symposium on Theory of computing, 20–29 (2003) [arXiv:0301023].
https://doi.org/10.1145/780542.780546
arXiv:quant-ph/0301023

[42] Ambainis, A., Quantum walk algorithms for element distinctness. SIAM Journal on Computing 37(1), 22–31 (2004) [arXiv:0311001].
https://doi.org/10.1137/S0097539705447311
arXiv:quant-ph/0311001

[43] Magniez, F., Santha, M. and Szegedy, M., Quantum Algorithms for the Triangle Problem. SIAM Journal on Computing 37(2), 413–424 (2007) [arXiv:0310134].
https://doi.org/10.1137/050643684
arXiv:quant-ph/0310134

[44] Krovi, H., Magniez, F., Ozols, M. and Roland, J., Quantum walks can find a marked element on any graph. Algorithmica 74(2), 851–907 (2016) [arXiv:1002.2419].
https://doi.org/10.1007/s00453-015-9979-8
arXiv:1002.2419

[45] Temme, K., Osborne, T. J., Vollbrecht, K. G. H., Poulin, D. and Verstraete, F., Quantum metropolis sampling. Nature 471, 87–90 (2011), [arXiv:0911.3635].
https://doi.org/10.1038/nature09770
arXiv:0911.3635

[46] Yung, M.-H. and Aspuru-Guzik, A., A quantum-quantum metropolis algorithm. Proceedings of the National Academy of Sciences 109(3), 754–759 (2012) [arXiv:1011.1468].
https://doi.org/10.1073/pnas.1111758109
arXiv:1011.1468

[47] Aaronson, S. and Christiano, P., Quantum Money from Hidden Subspaces. Theory of Computing 9(9), 349-401 (2013) [arXiv:1203.4740].
https://doi.org/10.1145/2213977.2213983
arXiv:1203.4740

[48] Briegel, H. J. and De las Cuevas, G., Projective simulation for artificial intelligence. Sci. Rep. 2, 400 (2012).
https://doi.org/10.1038/srep00400

[49] Mautner, J., Makmal, A., Manzano, D., Tiersch, M. and Briegel, H. J., Projective simulation for classical learning agents: a comprehensive investigation. New Generat. Comput. 33(1), 69–114 (2015) [arXiv:1305.1578].
https://doi.org/10.1007/s00354-015-0102-0
arXiv:1305.1578

[50] Dunjko, V. and Briegel, H. J., Machine learning & artificial intelligence in the quantum domain: a review of recent progress. Reports on Progress in Physics 81(7), 074001 (2018) [arXiv:1709.02779].
https://doi.org/10.1088/1361-6633/aab406
arXiv:1709.02779

[51] Fischer, A. and Christian, I., An introduction to restricted Boltzmann machines. Iberoamerican Congress on Pattern Recognition, 14–36 (2012).
https://doi.org/10.1007/978-3-642-33275-3_2

[52] Tieleman, T., Training restricted Boltzmann machines using approximations to the likelihood gradient. Proceedings of the 25th international conference on Machine learning, 1064–1071 (2008).
https://doi.org/10.1145/1390156.1390290

[53] Wiebe, N., Kapoor, A. and Svore, K. M., Quantum deep learning. Quantum Information & Computation 16(7-8), 541–587 (2016) [arXiv:1412.3489].
arXiv:1412.3489
http://dl.acm.org/citation.cfm?id=3179466.3179467

[54] Montanaro, A., Quantum speedup of Monte Carlo methods. Proceedings of the Royal Society A 471(2181), 0301 (2015) [arXiv:1504.06987].
https://doi.org/10.1098/rspa.2015.0301
arXiv:1504.06987

Cited by

[1] Shantanav Chakraborty, Kyle Luh, and Jérémie Roland, "How Fast Do Quantum Walks Mix?", Physical Review Letters 124 5, 050501 (2020).

[2] Sofiene Jerbi, Lea M. Trenkwalder, Hendrik Poulsen Nautrup, Hans J. Briegel, and Vedran Dunjko, "Quantum Enhancements for Deep Reinforcement Learning in Large Spaces", PRX Quantum 2 1, 010328 (2021).

[3] Yaoyao JIANG, Pengcheng CHU, Yulin MA, and Hongyang MA, "Search Algorithm Based on Permutation Group by Quantum Walk on Hypergraphes", Chinese Journal of Electronics 31 4, 626 (2022).

[4] Wenda Zhou, "Review on Quantum Walk Algorithm", Journal of Physics: Conference Series 1748 3, 032022 (2021).

[5] Shouvanik Chakrabarti, Andrew M. Childs, Shih-Han Hung, Tongyang Li, Chunhao Wang, and Xiaodi Wu, "Quantum Algorithm for Estimating Volumes of Convex Bodies", ACM Transactions on Quantum Computing 4 3, 1 (2023).

[6] Yao-Yao Jiang, Peng-Cheng Chu, Wen-Bin Zhang, and Hong-Yang Ma, "Quantum walk search algorithm for multi-objective searching with iteration auto-controlling on hypercube", Chinese Physics B 31 4, 040307 (2022).

[7] Xinying Li and Yun Shang, "Faster quantum sampling of Markov chains in nonregular graphs with fewer qubits", Physical Review A 107 2, 022432 (2023).

[8] Yao-Yao Jiang, Wen-Bin Zhang, Peng-Cheng Chu, and Hong-Yang Ma, "Feedback search algorithm for multi-particle quantum walks over a ring based on permutation groups", Acta Physica Sinica 71 3, 030201 (2022).

[9] Khadeejah Bepari, Sarah Malik, Michael Spannowsky, and Simon Williams, "Quantum walk approach to simulating parton showers", Physical Review D 106 5, 056002 (2022).

[10] Shantanav Chakraborty, Kyle Luh, and Jérémie Roland, "Analog quantum algorithms for the mixing of Markov chains", Physical Review A 102 2, 022423 (2020).

[11] Gösta Gustafson, Stefan Prestel, Michael Spannowsky, and Simon Williams, "Collider events on a quantum computer", Journal of High Energy Physics 2022 11, 35 (2022).

[12] Farrukh Mukhamedov and Ahmed Al-Rawashdeh, "Approximations of non-homogeneous Markov chains on abstract states spaces", Bulletin of Mathematical Sciences 11 03, 2150002 (2021).

[13] Yassine Hamoudi, "Preparing many copies of a quantum state in the black-box model", Physical Review A 105 6, 062440 (2022).

[14] Vedran Dunjko and Hans J. Briegel, "Machine learning & artificial intelligence in the quantum domain: a review of recent progress", Reports on Progress in Physics 81 7, 074001 (2018).

[15] Ashley Montanaro, "Quantum speedup of Monte Carlo methods: Table 1.", Proceedings of the Royal Society of London Series A 471 2181, 20150301 (2015).

[16] Vedran Dunjko and Hans J. Briegel, "Machine learning \& artificial intelligence in the quantum domain", arXiv:1709.02779, (2017).

[17] Shouvanik Chakrabarti, Andrew M. Childs, Shih-Han Hung, Tongyang Li, Chunhao Wang, and Xiaodi Wu, "Quantum algorithm for estimating volumes of convex bodies", arXiv:1908.03903, (2019).

[18] V. Dunjko and H. J. Briegel, "Quantum mixing of Markov chains for special distributions", New Journal of Physics 17 7, 073004 (2015).

[19] Aram W. Harrow and Annie Y. Wei, "Adaptive Quantum Simulated Annealing for Bayesian Inference and Estimating Partition Functions", arXiv:1907.09965, (2019).

[20] Tongyang Li and Ruizhe Zhang, "Quantum Speedups of Optimizing Approximately Convex Functions with Applications to Logarithmic Regret Stochastic Convex Bandits", arXiv:2209.12897, (2022).

[21] Simon Apers, "Quantum Walk Sampling by Growing Seed Sets", arXiv:1904.11446, (2019).

The above citations are from Crossref's cited-by service (last updated successfully 2024-08-10 21:07:22) and SAO/NASA ADS (last updated successfully 2024-08-10 21:07:23). The list may be incomplete as not all publishers provide suitable and complete citation data.

This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.