Faster quantum mixing for slowly evolving sequences of Markov chains

Davide Orsucci1, Hans J. Briegel1,2, and Vedran Dunjko1,3,4

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

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

► 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

[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

[54] Montanaro, A., Quantum speedup of Monte Carlo methods. Proceedings of the Royal Society A 471(2181), 0301 (2015) [arXiv:1504.06987].
arXiv:1504.06987

► Cited by (beta)

Crossref's cited-by service has no data on citing works. Unfortunately not all publishers provide suitable citation data.