Quantized Markov Chain Couplings that Prepare Qsamples
Summarize this article with:
AbstractWe present a novel approach to quantizing Markov chains. The approach is based on the Markov chain coupling method, which is frequently used to prove fast mixing. Given a particular coupling, e.g., a grand coupling, we construct a completely positive and trace preserving map. This quantum map has a unique fixed point, which corresponds to the quantum sample (qsample) of the classical Markov chain's stationary distribution. We show that the convergence time of the quantum map is directly related to the coupling time of the Markov chain coupling.► BibTeX data@article{Temme2025quantizedmarkov, doi = {10.22331/q-2025-12-18-1951}, url = {https://doi.org/10.22331/q-2025-12-18-1951}, title = {Quantized {M}arkov {C}hain {C}ouplings that {P}repare {Q}samples}, author = {Temme, Kristan and Wocjan, Pawel}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {9}, pages = {1951}, month = dec, year = {2025} }► References [1] Andrew M. Childs and Jeffrey Goldstone. ``Spatial search by quantum walk''. Phys. Rev. A 70, 022314 (2004). https://doi.org/10.1103/PhysRevA.70.022314 [2] Mario Szegedy. ``Quantum speed-up of Markov chain based algorithms''. In 45th Annual IEEE Symposium on Foundations of Computer Science. Pages 32–41. (2004). https://doi.org/10.1109/FOCS.2004.53 [3] Michael M. Wolf. ``Quantum channels and operations – guided tour''. Lecture notes (2012). [4] Frank Verstraete, Michael M. Wolf, and J. Ignacio Cirac. ``Quantum computation and quantum-state engineering driven by dissipation''. Nature Physics 5, 633–636 (2009). https://doi.org/10.1038/nphys1342 [5] Sebastian Diehl, Andrea Micheli, Alexej Kantian, Christina Kraus, Hans Peter Büchler, and Peter Zoller. ``Quantum states and phases in driven open quantum systems with cold atoms''. Nature Physics 4, 878–883 (2008). https://doi.org/10.1038/nphys1073 [6] Kristan Temme, Tobias J. Osborne, Karl Gerd H. Vollbrecht, David Poulin, and Frank Verstraete. ``Quantum Metropolis sampling''. Nature 471, 87–90 (2011). https://doi.org/10.1038/nature09770 [7] Patrick Rall, Chunhao Wang, and Pawel Wocjan. ``Thermal State Preparation via Rounding Promises''. Quantum 7, 1132 (2023). https://doi.org/10.22331/q-2023-10-10-1132 [8] Chi-Fang Chen, Michael J. Kastoryano, Fernando G. S. L. Brandão, and András Gilyén. ``Quantum thermal state preparation'' (2023). arXiv:2303.18224. arXiv:2303.18224 [9] Jiaqing Jiang and Sandy Irani. ``Quantum Metropolis sampling via weak measurement'' (2024). arXiv:2406.16023. arXiv:2406.16023 [10] David A. Levin and Yuval Perez. ``Markov chains and mixing times: Second edition''.
American Mathematical Society. (2017). url: https://pages.uoregon.edu/dlevin/MARKOV/markovmixing.pdf. https://pages.uoregon.edu/dlevin/MARKOV/markovmixing.pdf [11] Dorit Aharonov and Amnon Ta-Shma. ``Adiabatic quantum state generation''. SIAM Journal on Computing 37, 47–82 (2007). https://doi.org/10.1137/060648829 [12] James Gary Propp and David Bruce Wilson. ``Exact sampling with coupled Markov chains and applications to statistical mechanics''. Random Struct. Algorithms 9, 223–252 (1996). [13] Charles H. Bennett, Ethan Bernstein, Gilles Brassard, and Umesh Vazirani. ``Strengths and weaknesses of quantum computing''. SIAM Journal on Computing 26, 1510–1523 (1997). https://doi.org/10.1137/S0097539796300933 [14] Srinivasan Arunachalam, Vojtech Havlicek, Giacomo Nannicini, Kristan Temme, and Pawel Wocjan. ``Simpler (classical) and faster (quantum) algorithms for Gibbs partition functions''. Quantum 6, 789 (2022). arXiv:2009.11270v5. https://doi.org/10.22331/q-2022-09-01-789 arXiv:2009.11270v5 [15] Aram W. Harrow and Annie Y. Wei. ``Adaptive quantum simulated annealing for Bayesian inference and estimating partition functions''. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms. Pages 193–212. SIAM (2023). https://doi.org/10.1137/1.9781611975994.12 [16] 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, 1–60 (2023). https://doi.org/10.1145/3588579 [17] Andrew M. Childs, Tongyang Li, Jin-Peng Liu, Chunhao Wang, and Ruizhe Zhang. ``Quantum algorithms for sampling log-concave distributions and estimating normalizing constants''. In Proceedings of the 36th International Conference on Neural Information Processing Systems. Pages 1–13. NIPS '22.
Curran Associates Inc. (2022). url: https://arxiv.org/abs/2210.06539. arXiv:2210.06539 [18] Guneykan Ozgul, Xiantao Li, Mehrdad Mahdavi, and Chunhao Wang. ``Stochastic quantum sampling for non-logconcave distributions and estimating partition functions''. In Proceedings of the 41st International Conference on Machine Learning. Volume 235 of Proceedings of Machine Learning Research, pages 38953–38982. PMLR (2024). url: https://proceedings.mlr.press/v235/ozgul24a.html. https://proceedings.mlr.press/v235/ozgul24a.html [19] Jiaqi Leng, Zhiyan Ding, Zherui Chen, and Lin Lin. ``Operator-level quantum acceleration of non-logconcave sampling'' (2025). arXiv:2505.05301. arXiv:2505.05301 [20] Pawel Wocjan and Anura Abeyesinghe. ``Speedup via quantum sampling''. Phys. Rev. A 78, 042336 (2008). https://doi.org/10.1103/PhysRevA.78.042336 [21] Kristan Temme, Michael J. Kastoryano, Mary Beth Ruskai, Michael M. Wolf, and Frank Verstraete. ``The $\chi^2$-divergence and mixing times of quantum markov processes''. Journal of Mathematical Physics 51, 122201 (2010). https://doi.org/10.1063/1.3511335 [22] Kristan Temme. ``Thermalization time bounds for Pauli stabilizer hamiltonians''. Communications in Mathematical Physics 350, 603–637 (2017). https://doi.org/10.1007/s00220-016-2746-0 [23] Igor Bardet and Cambyse Rouzé. ``Hypercontractivity and logarithmic Sobolev inequality for non-primitive quantum Markov semigroups and estimation of decoherence rates''.
Annales Henri Poincaré 23, 3839–3903 (2022). https://doi.org/10.1007/s00023-022-01196-8 [24] Ivan Bardet, Ángela Capel, Angelo Lucia, David Pérez-García, and Cambyse Rouzé. ``On the modified logarithmic Sobolev inequality for the heat-bath dynamics for 1d systems''. Journal of Mathematical Physics 62, 061901 (2021). https://doi.org/10.1063/1.5142186 [25] Ivan Bardet, Ángela Capel, Lin Gao, Angelo Lucia, David Pérez-García, and Cambyse Rouzé. ``Entropy decay for davies semigroups of a one dimensional quantum lattice''. Communications in Mathematical Physics 405, 42 (2024). https://doi.org/10.1007/s00220-023-04869-5 [26] Raffaele Carbone and Fabio Girotti. ``Absorption in invariant domains for semigroups of quantum channels''.
Annales Henri Poincaré 22, 2497–2530 (2021). https://doi.org/10.1007/s00023-021-01016-5 [27] Alberto Frigerio. ``Stationary states of quantum dynamical semigroups''. Communications in Mathematical Physics 63, 269–276 (1978). https://doi.org/10.1007/BF01196936 [28] John Dengis, Robert König, and Fernando Pastawski. ``An optimal dissipative encoder for the toric code''. New Journal of Physics 16, 013023 (2014). https://doi.org/10.1088/1367-2630/16/1/013023 [29] Mark M. Wilde. ``Quantum information theory''.
Cambridge University Press. (2013). https://doi.org/10.1017/CBO9781139525343 [30] Xiantao Li and Chunhao Wang. ``Simulating Markovian Open Quantum Systems Using Higher-Order Series Expansion''.
In Kousha Etessami, Uriel Feige, and Gabriele Puppis, editors, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Volume 261 of Leibniz International Proceedings in Informatics (LIPIcs), pages 87:1–87:20. Dagstuhl, Germany (2023). Schloss Dagstuhl – Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ICALP.2023.87 [31] Dominic W. Berry, Andrew M. Childs, Richard Cleve, Robin Kothari, and Rolando D. Somma. ``Exponential improvement in precision for simulating sparse hamiltonians''. In Proceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing. Page 283–292. STOC '14New York, NY, USA (2014). Association for Computing Machinery. https://doi.org/10.1145/2591796.2591854 [32] Daan Camps, Lin Lin, Roel Van Beeumen, and Chao Yang. ``Explicit quantum circuits for block encodings of certain sparse matrices''. SIAM Journal on Matrix Analysis and Applications 45, 801–827 (2024). arXiv:https://doi.org/10.1137/22M1484298. https://doi.org/10.1137/22M1484298 arXiv:https://doi.org/10.1137/22M1484298 [33] András Gilyén, Yuan Su, Guang Hao Low, and Nathan Wiebe. ``Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics''. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. Pages 193–204. STOC 2019New York, NY, USA (2019). Association for Computing Machinery. https://doi.org/10.1145/3313276.3316366 [34] Pawel Wocjan and Kristan Temme. ``Szegedy walk unitaries for quantum maps''. Communications in Mathematical Physics 402, 3201–3231 (2023). https://doi.org/10.1007/s00220-023-04797-4 [35] E. B. Davies. ``Quantum theory of open systems''. Academic Press. (1976).Cited byCould not fetch Crossref cited-by data during last attempt 2025-12-18 14:37:43: Could not fetch cited-by data for 10.22331/q-2025-12-18-1951 from Crossref. This is normal if the DOI was registered recently. Could not fetch ADS cited-by data during last attempt 2025-12-18 14:37:44: No response from ADS or unable to decode the received json data when getting the list of citing works.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. AbstractWe present a novel approach to quantizing Markov chains. The approach is based on the Markov chain coupling method, which is frequently used to prove fast mixing. Given a particular coupling, e.g., a grand coupling, we construct a completely positive and trace preserving map. This quantum map has a unique fixed point, which corresponds to the quantum sample (qsample) of the classical Markov chain's stationary distribution. We show that the convergence time of the quantum map is directly related to the coupling time of the Markov chain coupling.► BibTeX data@article{Temme2025quantizedmarkov, doi = {10.22331/q-2025-12-18-1951}, url = {https://doi.org/10.22331/q-2025-12-18-1951}, title = {Quantized {M}arkov {C}hain {C}ouplings that {P}repare {Q}samples}, author = {Temme, Kristan and Wocjan, Pawel}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {9}, pages = {1951}, month = dec, year = {2025} }► References [1] Andrew M. Childs and Jeffrey Goldstone. ``Spatial search by quantum walk''. Phys. Rev. A 70, 022314 (2004). https://doi.org/10.1103/PhysRevA.70.022314 [2] Mario Szegedy. ``Quantum speed-up of Markov chain based algorithms''. In 45th Annual IEEE Symposium on Foundations of Computer Science. Pages 32–41. (2004). https://doi.org/10.1109/FOCS.2004.53 [3] Michael M. Wolf. ``Quantum channels and operations – guided tour''. Lecture notes (2012). [4] Frank Verstraete, Michael M. Wolf, and J. Ignacio Cirac. ``Quantum computation and quantum-state engineering driven by dissipation''. Nature Physics 5, 633–636 (2009). https://doi.org/10.1038/nphys1342 [5] Sebastian Diehl, Andrea Micheli, Alexej Kantian, Christina Kraus, Hans Peter Büchler, and Peter Zoller. ``Quantum states and phases in driven open quantum systems with cold atoms''. Nature Physics 4, 878–883 (2008). https://doi.org/10.1038/nphys1073 [6] Kristan Temme, Tobias J. Osborne, Karl Gerd H. Vollbrecht, David Poulin, and Frank Verstraete. ``Quantum Metropolis sampling''. Nature 471, 87–90 (2011). https://doi.org/10.1038/nature09770 [7] Patrick Rall, Chunhao Wang, and Pawel Wocjan. ``Thermal State Preparation via Rounding Promises''. Quantum 7, 1132 (2023). https://doi.org/10.22331/q-2023-10-10-1132 [8] Chi-Fang Chen, Michael J. Kastoryano, Fernando G. S. L. Brandão, and András Gilyén. ``Quantum thermal state preparation'' (2023). arXiv:2303.18224. arXiv:2303.18224 [9] Jiaqing Jiang and Sandy Irani. ``Quantum Metropolis sampling via weak measurement'' (2024). arXiv:2406.16023. arXiv:2406.16023 [10] David A. Levin and Yuval Perez. ``Markov chains and mixing times: Second edition''.
American Mathematical Society. (2017). url: https://pages.uoregon.edu/dlevin/MARKOV/markovmixing.pdf. https://pages.uoregon.edu/dlevin/MARKOV/markovmixing.pdf [11] Dorit Aharonov and Amnon Ta-Shma. ``Adiabatic quantum state generation''. SIAM Journal on Computing 37, 47–82 (2007). https://doi.org/10.1137/060648829 [12] James Gary Propp and David Bruce Wilson. ``Exact sampling with coupled Markov chains and applications to statistical mechanics''. Random Struct. Algorithms 9, 223–252 (1996). [13] Charles H. Bennett, Ethan Bernstein, Gilles Brassard, and Umesh Vazirani. ``Strengths and weaknesses of quantum computing''. SIAM Journal on Computing 26, 1510–1523 (1997). https://doi.org/10.1137/S0097539796300933 [14] Srinivasan Arunachalam, Vojtech Havlicek, Giacomo Nannicini, Kristan Temme, and Pawel Wocjan. ``Simpler (classical) and faster (quantum) algorithms for Gibbs partition functions''. Quantum 6, 789 (2022). arXiv:2009.11270v5. https://doi.org/10.22331/q-2022-09-01-789 arXiv:2009.11270v5 [15] Aram W. Harrow and Annie Y. Wei. ``Adaptive quantum simulated annealing for Bayesian inference and estimating partition functions''. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms. Pages 193–212. SIAM (2023). https://doi.org/10.1137/1.9781611975994.12 [16] 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, 1–60 (2023). https://doi.org/10.1145/3588579 [17] Andrew M. Childs, Tongyang Li, Jin-Peng Liu, Chunhao Wang, and Ruizhe Zhang. ``Quantum algorithms for sampling log-concave distributions and estimating normalizing constants''. In Proceedings of the 36th International Conference on Neural Information Processing Systems. Pages 1–13. NIPS '22.
Curran Associates Inc. (2022). url: https://arxiv.org/abs/2210.06539. arXiv:2210.06539 [18] Guneykan Ozgul, Xiantao Li, Mehrdad Mahdavi, and Chunhao Wang. ``Stochastic quantum sampling for non-logconcave distributions and estimating partition functions''. In Proceedings of the 41st International Conference on Machine Learning. Volume 235 of Proceedings of Machine Learning Research, pages 38953–38982. PMLR (2024). url: https://proceedings.mlr.press/v235/ozgul24a.html. https://proceedings.mlr.press/v235/ozgul24a.html [19] Jiaqi Leng, Zhiyan Ding, Zherui Chen, and Lin Lin. ``Operator-level quantum acceleration of non-logconcave sampling'' (2025). arXiv:2505.05301. arXiv:2505.05301 [20] Pawel Wocjan and Anura Abeyesinghe. ``Speedup via quantum sampling''. Phys. Rev. A 78, 042336 (2008). https://doi.org/10.1103/PhysRevA.78.042336 [21] Kristan Temme, Michael J. Kastoryano, Mary Beth Ruskai, Michael M. Wolf, and Frank Verstraete. ``The $\chi^2$-divergence and mixing times of quantum markov processes''. Journal of Mathematical Physics 51, 122201 (2010). https://doi.org/10.1063/1.3511335 [22] Kristan Temme. ``Thermalization time bounds for Pauli stabilizer hamiltonians''. Communications in Mathematical Physics 350, 603–637 (2017). https://doi.org/10.1007/s00220-016-2746-0 [23] Igor Bardet and Cambyse Rouzé. ``Hypercontractivity and logarithmic Sobolev inequality for non-primitive quantum Markov semigroups and estimation of decoherence rates''.
Annales Henri Poincaré 23, 3839–3903 (2022). https://doi.org/10.1007/s00023-022-01196-8 [24] Ivan Bardet, Ángela Capel, Angelo Lucia, David Pérez-García, and Cambyse Rouzé. ``On the modified logarithmic Sobolev inequality for the heat-bath dynamics for 1d systems''. Journal of Mathematical Physics 62, 061901 (2021). https://doi.org/10.1063/1.5142186 [25] Ivan Bardet, Ángela Capel, Lin Gao, Angelo Lucia, David Pérez-García, and Cambyse Rouzé. ``Entropy decay for davies semigroups of a one dimensional quantum lattice''. Communications in Mathematical Physics 405, 42 (2024). https://doi.org/10.1007/s00220-023-04869-5 [26] Raffaele Carbone and Fabio Girotti. ``Absorption in invariant domains for semigroups of quantum channels''.
Annales Henri Poincaré 22, 2497–2530 (2021). https://doi.org/10.1007/s00023-021-01016-5 [27] Alberto Frigerio. ``Stationary states of quantum dynamical semigroups''. Communications in Mathematical Physics 63, 269–276 (1978). https://doi.org/10.1007/BF01196936 [28] John Dengis, Robert König, and Fernando Pastawski. ``An optimal dissipative encoder for the toric code''. New Journal of Physics 16, 013023 (2014). https://doi.org/10.1088/1367-2630/16/1/013023 [29] Mark M. Wilde. ``Quantum information theory''.
Cambridge University Press. (2013). https://doi.org/10.1017/CBO9781139525343 [30] Xiantao Li and Chunhao Wang. ``Simulating Markovian Open Quantum Systems Using Higher-Order Series Expansion''.
In Kousha Etessami, Uriel Feige, and Gabriele Puppis, editors, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Volume 261 of Leibniz International Proceedings in Informatics (LIPIcs), pages 87:1–87:20. Dagstuhl, Germany (2023). Schloss Dagstuhl – Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ICALP.2023.87 [31] Dominic W. Berry, Andrew M. Childs, Richard Cleve, Robin Kothari, and Rolando D. Somma. ``Exponential improvement in precision for simulating sparse hamiltonians''. In Proceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing. Page 283–292. STOC '14New York, NY, USA (2014). Association for Computing Machinery. https://doi.org/10.1145/2591796.2591854 [32] Daan Camps, Lin Lin, Roel Van Beeumen, and Chao Yang. ``Explicit quantum circuits for block encodings of certain sparse matrices''. SIAM Journal on Matrix Analysis and Applications 45, 801–827 (2024). arXiv:https://doi.org/10.1137/22M1484298. https://doi.org/10.1137/22M1484298 arXiv:https://doi.org/10.1137/22M1484298 [33] András Gilyén, Yuan Su, Guang Hao Low, and Nathan Wiebe. ``Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics''. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. Pages 193–204. STOC 2019New York, NY, USA (2019). Association for Computing Machinery. https://doi.org/10.1145/3313276.3316366 [34] Pawel Wocjan and Kristan Temme. ``Szegedy walk unitaries for quantum maps''. Communications in Mathematical Physics 402, 3201–3231 (2023). https://doi.org/10.1007/s00220-023-04797-4 [35] E. B. Davies. ``Quantum theory of open systems''. Academic Press. (1976).Cited byCould not fetch Crossref cited-by data during last attempt 2025-12-18 14:37:43: Could not fetch cited-by data for 10.22331/q-2025-12-18-1951 from Crossref. This is normal if the DOI was registered recently. Could not fetch ADS cited-by data during last attempt 2025-12-18 14:37:44: No response from ADS or unable to decode the received json data when getting the list of citing works.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.