{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,3]],"date-time":"2026-06-03T18:28:51Z","timestamp":1780511331056,"version":"3.54.1"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2021,3,20]],"date-time":"2021-03-20T00:00:00Z","timestamp":1616198400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,3,20]],"date-time":"2021-03-20T00:00:00Z","timestamp":1616198400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Int. J. Autom. Comput."],"published-print":{"date-parts":[[2021,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Markov decision process (MDP) offers a general framework for modelling sequential decision making where outcomes are random. In particular, it serves as a mathematical framework for reinforcement learning. This paper introduces an extension of MDP, namely quantum MDP (qMDP), that can serve as a mathematical model of decision making about quantum systems. We develop dynamic programming algorithms for policy evaluation and finding optimal policies for qMDPs in the case of finite-horizon. The results obtained in this paper provide some useful mathematical tools for reinforcement learning techniques applied to the quantum world.<\/jats:p>","DOI":"10.1007\/s11633-021-1278-z","type":"journal-article","created":{"date-parts":[[2021,3,19]],"date-time":"2021-03-19T19:02:51Z","timestamp":1616180571000},"page":"410-421","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":14,"title":["Optimal Policies for Quantum Markov Decision Processes"],"prefix":"10.1007","volume":"18","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4847-702X","authenticated-orcid":false,"given":"Ming-Sheng","family":"Ying","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3097-3896","authenticated-orcid":false,"given":"Yuan","family":"Feng","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5052-5142","authenticated-orcid":false,"given":"Sheng-Gang","family":"Ying","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2021,3,20]]},"reference":[{"key":"1278_CR1","volume-title":"Markov Decision Processes: Discrete Stochastic Dynamic Programming","author":"M L Puterman","year":"2005","unstructured":"M. L. Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programming, Hoboken, USA: John Wiley, 2005."},{"issue":"1\u20132","key":"1278_CR2","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/S0004-3702(98)00023-X","volume":"101","author":"L P Kaelbling","year":"1998","unstructured":"L. P. Kaelbling, M. L. Littman, A. R. Cassandra. Planning and acting in partially observable stochastic domains. Artificial Intelligence, vol. 101, no. 1\u20132, pp. 99\u2013134, 1998. DOI: https:\/\/doi.org\/10.1016\/S0004-3702(98)00023-X.","journal-title":"Artificial Intelligence"},{"issue":"3","key":"1278_CR3","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.90.032311","volume":"90","year":"2014","unstructured":"J. Barry, D. T. Barry, S. Aaronson. Quantum partially observable Markov decision processes. Physical Review A, vol. 90, no. 3, Article number 032311, 2014. DOI: https:\/\/doi.org\/10.1103\/PhysRevA.90.032311.","journal-title":"Physical Review A"},{"key":"1278_CR4","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1016\/j.ic.2018.09.001","volume":"263","author":"S G Ying","year":"2018","unstructured":"S. G. Ying, M. S. Ying. Reachability analysis of quantum Markov decision processes. Information and Computation, vol. 263, pp. 31\u201351, 2018. DOI: https:\/\/doi.org\/10.1016\/j.ic.2018.09.001.","journal-title":"Information and Computation"},{"key":"1278_CR5","volume-title":"Foundations of Quantum Programming","author":"M S Ying","year":"2016","unstructured":"M. S. Ying. Foundations of Quantum Programming, Amsterdam, Netherlands: Morgan Kaufmann, 2016."},{"issue":"9","key":"1278_CR6","doi-asserted-by":"publisher","first-page":"1679","DOI":"10.1016\/j.scico.2013.03.016","volume":"78","author":"M S Ying","year":"2013","unstructured":"M. S. Ying, N. K. Yu, Y. Feng, R. Y. Duan. Verification of quantum programs. Science of Computer Programming, vol. 78, no. 9, pp. 1679\u20131700, 2013. DOI: https:\/\/doi.org\/10.1016\/j.scico.2013.03.016.","journal-title":"Science of Computer Programming"},{"key":"1278_CR7","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1016\/j.jcss.2018.01.005","volume":"95","author":"J Guan","year":"2018","unstructured":"J. Guan, Y. Feng, M. S. Ying. Decomposition of quantum Markov chains and its applications. Journal of Computer and System Sciences, vol. 95, pp. 55\u201368, 2018. DOI: https:\/\/doi.org\/10.1016\/j.jcss.2018.01.005.","journal-title":"Journal of Computer and System Sciences"},{"key":"1278_CR8","doi-asserted-by":"publisher","DOI":"10.1017\/9781108613323","volume-title":"Model Checking Quantum Systems: Principles and Algorithms","author":"M S Ying","year":"2021","unstructured":"M. S. Ying, Y. Feng. Model Checking Quantum Systems: Principles and Algorithms, Cambridge, USA: Cambridge University Press, 2021."},{"key":"1278_CR9","doi-asserted-by":"publisher","first-page":"334","DOI":"10.1007\/978-3-642-40184-8_24","volume-title":"Reachability probabilities of quantum Markov chains","author":"S G Ying","year":"2013","unstructured":"S. G. Ying, Y. Feng, N. K. Yu, M. S. Ying. Reachability probabilities of quantum Markov chains. In Proceedings of the 24th International Conference on Concurrency Theory, Springer, Buenos Aires, Argentina, pp. 334\u2013348, 2013. DOI: https:\/\/doi.org\/10.1007\/978-3-642-40184-8_24."},{"key":"1278_CR10","unstructured":"D. Powell. Quantum boost for artificial intelligence. Nature, to be published."},{"issue":"2","key":"1278_CR11","doi-asserted-by":"publisher","first-page":"162","DOI":"10.1016\/j.artint.2009.11.009","volume":"174","author":"M S Ying","year":"2010","unstructured":"M. S. Ying. Quantum computation, quantum theory and AI). Artificial Intelligence, vol. 174, no. 2, pp. 162\u2013176, 2010. DOI: https:\/\/doi.org\/10.1016\/j.artint.2009.11.009.","journal-title":"Artificial Intelligence"},{"issue":"7671","key":"1278_CR12","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1038\/nature23474","volume":"549","author":"J Biamonte","year":"2017","unstructured":"J. Biamonte, P. Wittek, N. Pancotti, P. Rebentrost, N. Wiebe, S. Lloyd. Quantum machine learning. Nature, vol. 549, no. 7671, pp. 195\u2013202, 2017. DOI: https:\/\/doi.org\/10.1038\/nature23474.","journal-title":"Nature"},{"issue":"7","key":"1278_CR13","doi-asserted-by":"publisher","DOI":"10.1088\/1361-6633\/aab406","volume":"81","year":"2018","unstructured":"V. Dunjko, H. J. Briegel. Machine learning & artificial intelligence in the quantum domain: A review of recent progress. Reports on Progress in Physics, vol. 81, no. 7, Article number 074001, 2018. DOI: https:\/\/doi.org\/10.1088\/1361-6633\/aab406.","journal-title":"Reports on Progress in Physics"},{"issue":"3","key":"1278_CR14","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1063\/PT.3.4164","volume":"72","author":"S D Sarma","year":"2019","unstructured":"S. D. Sarma, D. L. Deng, L. M. Duan. Machine learning meets quantum physics. Physics Today, vol. 72, no. 3, pp. 48\u201354, 2019. DOI: https:\/\/doi.org\/10.1063\/PT.3.4164.","journal-title":"Physics Today"},{"key":"1278_CR15","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1613\/jair.301","volume":"4","author":"L P Kaelbling","year":"1996","unstructured":"L. P. Kaelbling, M. L. Littman, A. W. Moore. Reinforcement learning: A survey. Journal of Artificial Intelligence Research, vol. 4, pp. 237\u2013285, 1996. DOI: https:\/\/doi.org\/10.1613\/jair.301.","journal-title":"Journal of Artificial Intelligence Research"},{"key":"1278_CR16","volume-title":"Reinforcement Learning: An Introduction","author":"R S Sutton","year":"1998","unstructured":"R. S. Sutton, A. G. Barto. Reinforcement Learning: An Introduction, Cambridge, USA: MIT Press, 1998."},{"key":"1278_CR17","doi-asserted-by":"publisher","first-page":"686","DOI":"10.1007\/11539117_97","volume-title":"Quantum reinforcement learning","author":"D Y Dong","year":"2005","unstructured":"D. Y. Dong, C. L. Chen, Z. H. Chen. Quantum reinforcement learning. In Proceedings of the 1st International Conference on Advances in Natural Computation, Springer, Changsha, China, pp. 686\u2013689, 2005. DOI: https:\/\/doi.org\/10.1007\/11539117_97."},{"issue":"5","key":"1278_CR18","doi-asserted-by":"publisher","first-page":"1207","DOI":"10.1109\/TSMCB.2008.925743","volume":"38","author":"D Y Dong","year":"2008","unstructured":"D. Y. Dong, C. L. Chen, H. X. Li, T. J. Tarn. Quantum reinforcement learning. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), vol. 38, no. 5, pp. 1207\u20131220, 2008. DOI: https:\/\/doi.org\/10.1109\/TSMCB.2008.925743.","journal-title":"IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics)"},{"issue":"13","key":"1278_CR19","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.117.130501","volume":"117","year":"2016","unstructured":"V. Dunjko, J. M. Taylor, H. J. Briegel. Quantum-enhanced machine learning. Physical Review Letters, vol. 117, no. 13, Article number 130501, 2016. DOI: https:\/\/doi.org\/10.1103\/PhysRevLett.117.130501.","journal-title":"Physical Review Letters"},{"key":"1278_CR20","doi-asserted-by":"publisher","first-page":"282","DOI":"10.1109\/SMC.2017.8122616","volume-title":"Advances in quantum reinforcement learning","author":"V Dunjko","year":"2017","unstructured":"V. Dunjko, J. M. Taylor, H. J. Briegel. Advances in quantum reinforcement learning. Proceedings of 2017 IEEE International Conference on Systems, Man, and Cybernetics, IEEE, Banff, Canada, pp. 282\u2013287, 2017. DOI: https:\/\/doi.org\/10.1109\/SMC.2017.8122616."},{"key":"1278_CR21","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1145\/380752.380757","volume-title":"One-dimensional quantum walks","author":"A Ambainis","year":"2001","unstructured":"A. Ambainis, E. Bach, A. Nayak, A. Vishwanath, J. Watrous. One-dimensional quantum walks. In Proceedings of the 33rd ACM Symposium on Theory of Computing, ACM, Heraklion, Greece, pp.37\u201349, 2001. DOI: https:\/\/doi.org\/10.1145\/380752.380757."},{"issue":"3\u20134","key":"1278_CR22","doi-asserted-by":"publisher","first-page":"407","DOI":"10.1006\/spmi.1997.0519","volume":"23","author":"P Benioff","year":"1998","unstructured":"P. Benioff. Some foundational aspects of quantum computers and quantum robots. Superlattices and Microstructures, vol. 23, no. 3\u20134, pp. 407\u2013417, 1998. DOI: https:\/\/doi.org\/10.1006\/spmi.1997.0519.","journal-title":"Superlattices and Microstructures"},{"issue":"2","key":"1278_CR23","doi-asserted-by":"publisher","first-page":"893","DOI":"10.1103\/PhysRevA.58.893","volume":"58","author":"P Benioff","year":"1998","unstructured":"P. Benioff. Quantum robots and environments. Physical Review A, vol. 58, no. 2, pp. 893\u2013904, 1998. DOI: https:\/\/doi.org\/10.1103\/PhysRevA.58.893.","journal-title":"Physical Review A"},{"issue":"4","key":"1278_CR24","doi-asserted-by":"publisher","first-page":"513","DOI":"10.1017\/S0263574705002596","volume":"24","author":"D Y Dong","year":"2006","unstructured":"D. Y. Dong, C. L. Chen, C. B. Zhang, Z. H. Chen. Quantum robot: Structure, algorithms and applications. Robotica, vol. 24, no. 4, pp. 513\u2013521, 2006. DOI: https:\/\/doi.org\/10.1017\/S0263574705002596.","journal-title":"Robotica"},{"issue":"4","key":"1278_CR25","doi-asserted-by":"publisher","first-page":"681","DOI":"10.1145\/347476.347480","volume":"47","author":"M Mundhenk","year":"2000","unstructured":"M. Mundhenk, J. Goldsmith, C. Lusena, E. Allender. Complexity of finite-horizon Markov decision process problems. Journal of the ACM, vol. 47, no. 4, pp. 681\u2013720, 2000. DOI: https:\/\/doi.org\/10.1145\/347476.347480.","journal-title":"Journal of the ACM"},{"issue":"3","key":"1278_CR26","doi-asserted-by":"publisher","first-page":"441","DOI":"10.1287\/moor.12.3.441","volume":"12","author":"C H Papadimitriou","year":"1987","unstructured":"C. H. Papadimitriou, J. N. Tsitsiklis. The complexity of Markov decision processes. Mathematics of Operations Research, vol. 12, no. 3, pp. 441\u2013450, 1987. DOI: https:\/\/doi.org\/10.1287\/moor.12.3.441.","journal-title":"Mathematics of Operations Research"},{"key":"1278_CR27","first-page":"174","volume-title":"Methods for computing state similarity in Markov decision processes","author":"N Ferns","year":"2006","unstructured":"N. Ferns, P. S. Castro, D. Precup, P. Panangaden. Methods for computing state similarity in Markov decision processes. In Proceedings of the 22nd Conference on Uncertainty in Artificial Intelligence, AUAI, Cambridge, USA, pp. 174\u2013181, 2006."},{"key":"1278_CR28","unstructured":"N. Ferns, P. Panangaden, D. Precup. Metrics for Markov decision processes with infinite state spaces. In Proceedings of the 21st Conference on Uncertainty in Artificial Intelligence, Edinburgh, Scotland, pp. 201\u2013208, 2005."}],"container-title":["International Journal of Automation and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11633-021-1278-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11633-021-1278-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11633-021-1278-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,12]],"date-time":"2021-05-12T17:21:54Z","timestamp":1620840114000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11633-021-1278-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,3,20]]},"references-count":28,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,6]]}},"alternative-id":["1278"],"URL":"https:\/\/doi.org\/10.1007\/s11633-021-1278-z","relation":{},"ISSN":["1476-8186","1751-8520"],"issn-type":[{"value":"1476-8186","type":"print"},{"value":"1751-8520","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,3,20]]},"assertion":[{"value":"22 July 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 January 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 March 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}