Quantum-embeddable stochastic matrices
1Faculty of Physics, Astronomy and Applied Computer Science, Jagiellonian University, 30-348 Krakow, Poland
2Institute for Theoretical Physics, ETH Zürich, 8093 Zürich, Switzerland
3Institute of Theoretical and Applied Informatics, Polish Academy of Sciences, Bałtycka 5, 44-100 Gliwice, Poland
| Published: | 2024-07-10, volume 8, page 1404 |
| Eprint: | arXiv:2305.17163v2 |
| Doi: | https://doi.org/10.22331/q-2024-07-10-1404 |
| Citation: | Quantum 8, 1404 (2024). |
Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.
Abstract
The classical embeddability problem asks whether a given stochastic matrix $T$, describing transition probabilities of a $d$-level system, can arise from the underlying homogeneous continuous-time Markov process. Here, we investigate the quantum version of this problem, asking of the existence of a Markovian quantum channel generating state transitions described by a given $T$. More precisely, we aim at characterising the set of quantum-embeddable stochastic matrices that arise from memoryless continuous-time quantum evolution. To this end, we derive both upper and lower bounds on that set, providing new families of stochastic matrices that are quantum-embeddable but not classically-embeddable, as well as families of stochastic matrices that are not quantum-embeddable. As a result, we demonstrate that a larger set of transition matrices can be explained by memoryless models if the dynamics is allowed to be quantum, but we also identify a non-zero measure set of random processes that cannot be explained by either classical or quantum memoryless dynamics. Finally, we fully characterise extreme stochastic matrices (with entries given only by zeros and ones) that are quantum-embeddable.
► BibTeX data
► References
[1] G. Elfving. ``Zur theorie der Markoffschen Ketten''. Acta Soc. Sci. Fennicae, n. Ser. A2 8, 1–17 (1937).
[2] E. B. Davies. ``Embeddable Markov matrices''. Electron. J. Probab. 15, 1474–1486 (2010).
https://doi.org/10.1214/EJP.v15-733
[3] J. F. C. Kingman. ``The imbedding problem for finite Markov chains''. Probab. Theory Relat. Fields 1, 14–24 (1962).
https://doi.org/10.1007/BF00531768
[4] J. R. Cuthbert. ``The logarithm function for finite-state Markov semi-groups''. J. London Math. Soc. 2, 524–532 (1973).
https://doi.org/10.1112/jlms/s2-6.3.524
[5] S. Johansen. ``Some results on the imbedding problem for finite Markov chains''. J. London Math. Soc. 2, 345–351 (1974).
https://doi.org/10.1112/jlms/s2-8.2.345
[6] P. Carette. ``Characterizations of embeddable 3$\times$ 3 stochastic matrices with a negative eigenvalue''. New York J. Math 1, 129 (1995). url: https://www.emis.de/journals/NYJM/NYJM/nyjm/j/1995/1-8.pdf.
https://www.emis.de/journals/NYJM/NYJM/nyjm/j/1995/1-8.pdf
[7] M. Casanellas, J. Fernández-Sánchez, and J. Roca-Lacostena. ``The embedding problem for Markov matrices'' (2020). url: https://arxiv.org/abs/2005.00818.
arXiv:2005.00818
[8] G. S. Goodman. ``An intrinsic time for non-stationary finite Markov chains''. Probab. Theory Relat. Fields 16, 165–180 (1970).
https://doi.org/10.1007/BF00534594
[9] K. Korzekwa and M. Lostaglio. ``Quantum advantage in simulating stochastic processes''. Phys. Rev. X 11, 021019 (2021).
https://doi.org/10.1103/PhysRevX.11.021019
[10] M. M. Wolf, J. Eisert, T. S. Cubitt, and J. I. Cirac. ``Assessing non-Markovian quantum dynamics''. Phys. Rev. Lett. 101, 150402 (2008).
https://doi.org/10.1103/PhysRevLett.101.150402
[11] V. Gorini, A. Kossakowski, and E. C. G. Sudarshan. ``Completely positive dynamical semigroups of N-level systems''. J. Math. Phys. 17, 821–825 (1976).
https://doi.org/10.1063/1.522979
[12] G. Lindblad. ``On the generators of quantum dynamical semigroups''. Commun. Math. Phys. 48, 119–130 (1976).
https://doi.org/10.1007/BF01608499
[13] D. H. Wolpert, A. Kolchinsky, and J. A. Owen. ``A space–time tradeoff for implementing a function with master equation dynamics''. Nat. Commun. 10, 1727 (2019).
https://doi.org/10.1038/s41467-019-09542-x
[14] I. Bengtsson. ``The importance of being unistochastic'' (2004). url: https://arxiv.org/abs/quant-ph/0403088.
arXiv:quant-ph/0403088
[15] M. M. Wolf and J. I. Cirac. ``Dividing quantum channels''. Commun. Math. Phys. 279, 147–168 (2008).
https://doi.org/10.1007/s00220-008-0411-y
[16] D. Davalos, M. Ziman, and C. Pineda. ``Divisibility of qubit channels and dynamical maps''. Quantum 3, 144 (2019).
https://doi.org/10.22331/q-2019-05-20-144
[17] D. Braun, O. Giraud, I. Nechita, C. Pellegrini, and M. Žnidarič. ``A universal set of qubit quantum channels''. J. Phys. A 47, 135302 (2014).
https://doi.org/10.1088/1751-8113/47/13/135302
[18] C. A. Fuchs and J. van de Graaf. ``Cryptographic distinguishability measures for quantum-mechanical states''. IEEE Trans. Inf. Theory 45, 1216–1227 (1999).
https://doi.org/10.1109/18.761271
[19] Z. Puchała and J. A. Miszczak. ``Bound on trace distance based on superfidelity''. Phys. Rev. A 79, 024302 (2009).
https://doi.org/10.1103/PhysRevA.79.024302
[20] M. Gu, K. Wiesner, E. Rieperand, and V. Vedral. ``Quantum mechanics can reduce the complexity of classical models''. Nat. Commun. 3, 762 (2012).
https://doi.org/10.1038/ncomms1761
[21] R. Tan, J. Thompson, V. Vedral, and M. Gu. ``Towards quantifying complexity with quantum mechanics''. Eur. Phys. J. Plus 129, 191 (2014).
https://doi.org/10.1140/epjp/i2014-14191-2
[22] F. Ghafari, N. Tischler, J. Thompson, M. Gu, L. K. Shalm, V. B. Verma, S. W. Nam, R. B. Patel, H. M. Wiseman, and G. J. Pryde. ``Dimensional quantum memory advantage in the simulation of stochastic processes''. Phys. Rev. X 9, 041013 (2019).
https://doi.org/10.1103/PhysRevX.9.041013
[23] F. C. Binder, J. Thompson, and M. Gu. ``Practical unitary simulator for non-Markovian complex processes''. Phys. Rev. Lett. 120, 240502 (2018).
https://doi.org/10.1103/PhysRevLett.120.240502
[24] https://github.com/rkukulski/ quantum-embeddable-stochastic-matrices. Permanent link to code/repository, Accessed: 2024-03-25.
https://github.com/rkukulski/quantum-embeddable-stochastic-matrices
[25] S. J. Akhtarshenas. ``Concurrence vectors in arbitrary multipartite quantum systems''. J. Phys. A 38, 6777 (2005).
https://doi.org/10.1088/0305-4470/38/30/011
[26] Benjamin Dive, Florian Mintert, and Daniel Burgarth. ``Quantum simulations of dissipative dynamics: Time dependence instead of size''. Phys. Rev. A 92, 032111 (2015).
https://doi.org/10.1103/PhysRevA.92.032111
Cited by
[1] Albert Rico, Moisés Bermejo Morán, Fereshte Shahbeigi, and Karol Życzkowski, "Certifying nonlocal properties of noisy quantum operations", Quantum 9, 1807 (2025).
[2] Fabio Benatti, Dariusz Chruściński, and Giovanni Nichele, "Quantum versus classical P -divisibility", Physical Review A 110 5, 052212 (2024).
[3] M. Çarboğa and Y. Yaylı, "Geometry of umbrella matrices in Galilean space", International Journal of Geometric Methods in Modern Physics 22 12, 2550102 (2025).
[4] Albert Rico, Moisés Bermejo Morán, Fereshte Shahbeigi, and Karol Życzkowski, "Channel Nonlocality under Decoherence", Physical Review Letters 136 11, 110202 (2026).
[5] A de Oliveira Junior, "Geometric and information-theoretic aspects of quantum thermodynamics", arXiv:2404.00617, (2024).
[6] Frederik Vom Ende, "Finite-Dimensional Stinespring Curves Can Approximate Any Dynamics", Open Systems and Information Dynamics 31 1, 2450004 (2024).
The above citations are from Crossref's cited-by service (last updated successfully 2026-07-17 08:54:51) and SAO/NASA ADS (last updated successfully 2026-07-16 19:32:21). The list may be incomplete as not all publishers provide suitable and complete citation data.
Could not fetch ADS cited-by data during last attempt 2026-07-17 08:54:51: Cannot retrieve data from ADS due to rate limitations.
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.