{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,21]],"date-time":"2026-03-21T00:10:49Z","timestamp":1774051849354,"version":"3.50.1"},"reference-count":26,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2024,7,10]],"date-time":"2024-07-10T00:00:00Z","timestamp":1720569600000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Foundation for Polish Science through TEAM-NET project","award":["POIR.04.04.00-00- 17C1\/18-00"],"award-info":[{"award-number":["POIR.04.04.00-00- 17C1\/18-00"]}]},{"name":"European Union\u2019s Horizon 2020 research and innovation programme","award":["101017733"],"award-info":[{"award-number":["101017733"]}]},{"name":"Swiss National Science Foundation through the Sinergia grant","award":["CRSII5-186364"],"award-info":[{"award-number":["CRSII5-186364"]}]}],"content-domain":{"domain":["quantum-journal.org"],"crossmark-restriction":false},"short-container-title":["Quantum"],"abstract":"<jats:p>The classical embeddability problem asks whether a given stochastic matrix <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>T<\/mml:mi><\/mml:math>, describing transition probabilities of a <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>d<\/mml:mi><\/mml:math>-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 <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>T<\/mml:mi><\/mml:math>. 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.<\/jats:p>","DOI":"10.22331\/q-2024-07-10-1404","type":"journal-article","created":{"date-parts":[[2024,7,10]],"date-time":"2024-07-10T15:03:32Z","timestamp":1720623812000},"page":"1404","update-policy":"https:\/\/doi.org\/10.22331\/q-crossmark-policy-page","source":"Crossref","is-referenced-by-count":4,"title":["Quantum-embeddable stochastic matrices"],"prefix":"10.22331","volume":"8","author":[{"given":"Fereshte","family":"Shahbeigi","sequence":"first","affiliation":[{"name":"Faculty of Physics, Astronomy and Applied Computer Science, Jagiellonian University, 30-348 Krakow, Poland"}]},{"given":"Christopher T.","family":"Chubb","sequence":"additional","affiliation":[{"name":"Institute for Theoretical Physics, ETH Z\u00fcrich, 8093 Z\u00fcrich, Switzerland"}]},{"given":"Ryszard","family":"Kukulski","sequence":"additional","affiliation":[{"name":"Institute of Theoretical and Applied Informatics, Polish Academy of Sciences, Ba\u0142tycka 5, 44-100 Gliwice, Poland"},{"name":"Faculty of Physics, Astronomy and Applied Computer Science, Jagiellonian University, 30-348 Krakow, Poland"}]},{"given":"\u0141ukasz","family":"Pawela","sequence":"additional","affiliation":[{"name":"Institute of Theoretical and Applied Informatics, Polish Academy of Sciences, Ba\u0142tycka 5, 44-100 Gliwice, Poland"}]},{"given":"Kamil","family":"Korzekwa","sequence":"additional","affiliation":[{"name":"Faculty of Physics, Astronomy and Applied Computer Science, Jagiellonian University, 30-348 Krakow, Poland"}]}],"member":"9598","published-online":{"date-parts":[[2024,7,10]]},"reference":[{"key":"0","unstructured":"G. Elfving. ``Zur theorie der Markoffschen Ketten&apos;&apos;. Acta Soc. Sci. Fennicae, n. Ser. A2 8, 1\u201317 (1937)."},{"key":"1","doi-asserted-by":"publisher","unstructured":"E. B. Davies. ``Embeddable Markov matrices&apos;&apos;. Electron. J. Probab. 15, 1474\u20131486 (2010).","DOI":"10.1214\/EJP.v15-733"},{"key":"2","doi-asserted-by":"publisher","unstructured":"J. F. C. Kingman. ``The imbedding problem for finite Markov chains&apos;&apos;. Probab. Theory Relat. Fields 1, 14\u201324 (1962).","DOI":"10.1007\/BF00531768"},{"key":"3","doi-asserted-by":"publisher","unstructured":"J. R. Cuthbert. ``The logarithm function for finite-state Markov semi-groups&apos;&apos;. J. London Math. Soc. 2, 524\u2013532 (1973).","DOI":"10.1112\/jlms\/s2-6.3.524"},{"key":"4","doi-asserted-by":"publisher","unstructured":"S. Johansen. ``Some results on the imbedding problem for finite Markov chains&apos;&apos;. J. London Math. Soc. 2, 345\u2013351 (1974).","DOI":"10.1112\/jlms\/s2-8.2.345"},{"key":"5","unstructured":"P. Carette. ``Characterizations of embeddable 3$\\times$ 3 stochastic matrices with a negative eigenvalue&apos;&apos;. New York J. Math 1, 129 (1995). url: https:\/\/www.emis.de\/journals\/NYJM\/NYJM\/nyjm\/j\/1995\/1-8.pdf."},{"key":"6","unstructured":"M. Casanellas, J. Fern\u00e1ndez-S\u00e1nchez, and J. Roca-Lacostena. ``The embedding problem for Markov matrices&apos;&apos; (2020). url: https:\/\/arxiv.org\/abs\/2005.00818."},{"key":"7","doi-asserted-by":"publisher","unstructured":"G. S. Goodman. ``An intrinsic time for non-stationary finite Markov chains&apos;&apos;. Probab. Theory Relat. Fields 16, 165\u2013180 (1970).","DOI":"10.1007\/BF00534594"},{"key":"8","doi-asserted-by":"publisher","unstructured":"K. Korzekwa and M. Lostaglio. ``Quantum advantage in simulating stochastic processes&apos;&apos;. Phys. Rev. X 11, 021019 (2021).","DOI":"10.1103\/PhysRevX.11.021019"},{"key":"9","doi-asserted-by":"publisher","unstructured":"M. M. Wolf, J. Eisert, T. S. Cubitt, and J. I. Cirac. ``Assessing non-Markovian quantum dynamics&apos;&apos;. Phys. Rev. Lett. 101, 150402 (2008).","DOI":"10.1103\/PhysRevLett.101.150402"},{"key":"10","doi-asserted-by":"publisher","unstructured":"V. Gorini, A. Kossakowski, and E. C. G. Sudarshan. ``Completely positive dynamical semigroups of N-level systems&apos;&apos;. J. Math. Phys. 17, 821\u2013825 (1976).","DOI":"10.1063\/1.522979"},{"key":"11","doi-asserted-by":"publisher","unstructured":"G. Lindblad. ``On the generators of quantum dynamical semigroups&apos;&apos;. Commun. Math. Phys. 48, 119\u2013130 (1976).","DOI":"10.1007\/BF01608499"},{"key":"12","doi-asserted-by":"publisher","unstructured":"D. H. Wolpert, A. Kolchinsky, and J. A. Owen. ``A space\u2013time tradeoff for implementing a function with master equation dynamics&apos;&apos;. Nat. Commun. 10, 1727 (2019).","DOI":"10.1038\/s41467-019-09542-x"},{"key":"13","unstructured":"I. Bengtsson. ``The importance of being unistochastic&apos;&apos; (2004). url: https:\/\/arxiv.org\/abs\/quant-ph\/0403088."},{"key":"14","doi-asserted-by":"publisher","unstructured":"M. M. Wolf and J. I. Cirac. ``Dividing quantum channels&apos;&apos;. Commun. Math. Phys. 279, 147\u2013168 (2008).","DOI":"10.1007\/s00220-008-0411-y"},{"key":"15","doi-asserted-by":"publisher","unstructured":"D. Davalos, M. Ziman, and C. Pineda. ``Divisibility of qubit channels and dynamical maps&apos;&apos;. Quantum 3, 144 (2019).","DOI":"10.22331\/q-2019-05-20-144"},{"key":"16","doi-asserted-by":"publisher","unstructured":"D. Braun, O. Giraud, I. Nechita, C. Pellegrini, and M. \u017dnidari\u010d. ``A universal set of qubit quantum channels&apos;&apos;. J. Phys. A 47, 135302 (2014).","DOI":"10.1088\/1751-8113\/47\/13\/135302"},{"key":"17","doi-asserted-by":"publisher","unstructured":"C. A. Fuchs and J. van de Graaf. ``Cryptographic distinguishability measures for quantum-mechanical states&apos;&apos;. IEEE Trans. Inf. Theory 45, 1216\u20131227 (1999).","DOI":"10.1109\/18.761271"},{"key":"18","doi-asserted-by":"publisher","unstructured":"Z. Pucha\u0142a and J. A. Miszczak. ``Bound on trace distance based on superfidelity&apos;&apos;. Phys. Rev. A 79, 024302 (2009).","DOI":"10.1103\/PhysRevA.79.024302"},{"key":"19","doi-asserted-by":"publisher","unstructured":"M. Gu, K. Wiesner, E. Rieperand, and V. Vedral. ``Quantum mechanics can reduce the complexity of classical models&apos;&apos;. Nat. Commun. 3, 762 (2012).","DOI":"10.1038\/ncomms1761"},{"key":"20","doi-asserted-by":"publisher","unstructured":"R. Tan, J. Thompson, V. Vedral, and M. Gu. ``Towards quantifying complexity with quantum mechanics&apos;&apos;. Eur. Phys. J. Plus 129, 191 (2014).","DOI":"10.1140\/epjp\/i2014-14191-2"},{"key":"21","doi-asserted-by":"publisher","unstructured":"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&apos;&apos;. Phys. Rev. X 9, 041013 (2019).","DOI":"10.1103\/PhysRevX.9.041013"},{"key":"22","doi-asserted-by":"publisher","unstructured":"F. C. Binder, J. Thompson, and M. Gu. ``Practical unitary simulator for non-Markovian complex processes&apos;&apos;. Phys. Rev. Lett. 120, 240502 (2018).","DOI":"10.1103\/PhysRevLett.120.240502"},{"key":"23","unstructured":"https:\/\/github.com\/rkukulski\/ quantum-embeddable-stochastic-matrices. Permanent link to code\/repository, Accessed: 2024-03-25."},{"key":"24","doi-asserted-by":"publisher","unstructured":"S. J. Akhtarshenas. ``Concurrence vectors in arbitrary multipartite quantum systems&apos;&apos;. J. Phys. A 38, 6777 (2005).","DOI":"10.1088\/0305-4470\/38\/30\/011"},{"key":"25","doi-asserted-by":"publisher","unstructured":"Benjamin Dive, Florian Mintert, and Daniel Burgarth. ``Quantum simulations of dissipative dynamics: Time dependence instead of size&apos;&apos;. Phys. Rev. A 92, 032111 (2015).","DOI":"10.1103\/PhysRevA.92.032111"}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2024-07-10-1404\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2024,7,10]],"date-time":"2024-07-10T15:03:49Z","timestamp":1720623829000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2024-07-10-1404\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,7,10]]},"references-count":26,"URL":"https:\/\/doi.org\/10.22331\/q-2024-07-10-1404","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,7,10]]},"article-number":"1404"}}