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

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

[6] Geman, S. and Geman, D., Stochastic relaxation, Gibbs distributions, and the Bayesian restoration of images. Readings in Computer Vision, 564-584 (1987).

[7] Martinelli, F., Lectures on Glauber dynamics for discrete spin models. Lectures on probability theory and statistics, Springer, 93-191 (1999).

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

[11] Kirkpatrick, S., Gelatt, C. D. and Vecchi, M. P., Optimization by simulated annealing. Science 220(4598), 671-680 (1983).

[12] Van Laarhoven, P. J., and Aarts, E. H., Simulated annealing. Simulated annealing: Theory and applications 37 (1987).

[13] Richter, P. C., Quantum speedup of classical mixing processes. Phys. Rev. A 76, 042306 (2007) [arXiv:0609204].

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

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

[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].

[17] Richter, P. C., Almost uniform sampling via quantum walks. New J. Phys. 9(72) (2007) [arXiv: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].

[19] Kempe, J., Quantum random walks - an introductory overview. Contemp. Phys. 44(4), 307-327 (2003) [arXiv:0303081].

[20] Reitzner, D., Nagaj, D. and Bužek, V., Quantum Walks. Acta Phys. Slovaca 61(6), 603-725 (2011) [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].

[22] Wocjan, P. and Abeyesinghe, A., Speedup via quantum sampling. Phys. Rev. A 78, 042336 (2008) [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].

[24] Childs, A., Quantum information processing in continuous time. Ph. D. Thesis, Massachusetts Institute of Technology (2004).

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

[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].

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

[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].

[32] Wiebe, N. and Granade, C. E., Efficient Bayesian Phase Estimation Phys. Rev. Lett. 117, 010503 (2016) [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].

[34] Brassard, G., Hoyer, P., Mosca, M. and Tapp, A., Quantum Amplitude Amplification and Estimation. Contemporary Mathematics 305, 53-74 (2002) [arXiv:0005055].

[35] Grover, L. K., Fixed-Point Quantum Search. Phys. Rev. Lett. 95, 150501 (2005) [arXiv: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).

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

[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].

[39] Sly, A. Computational transition at the uniqueness threshold. 51st Annual IEEE Symposium on Foundations of Computer Science, 287-296 (2010) [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].<493::AID-PROP493>3.0.CO;2-P

[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].

[42] Ambainis, A., Quantum walk algorithms for element distinctness. SIAM Journal on Computing 37(1), 22-31 (2004) [arXiv: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].

[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].

[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].

[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].

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

[48] Briegel, H. J. and De las Cuevas, G., Projective simulation for artificial intelligence. Sci. Rep. 2, 400 (2012).

[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].

[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].

[51] Fischer, A. and Christian, I., An introduction to restricted Boltzmann machines. Iberoamerican Congress on Pattern Recognition, 14-36 (2012).

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

[53] Wiebe, N., Kapoor, A. and Svore, K. M., Quantum deep learning. Quantum Information & Computation 16(7-8), 541-587 (2016) [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].

Cited by

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

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

[3] 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).

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

The above citations are from SAO/NASA ADS (last updated 2019-01-23 05:16:56). The list may be incomplete as not all publishers provide suitable and complete citation data.

On Crossref's cited-by service no data on citing works was found (last attempt 2019-01-23 05:16:55).