×

zbMATH — the first resource for mathematics

Reachability analysis of quantum Markov decision processes. (English) Zbl 1407.68341
Summary: We introduce the notion of quantum Markov decision process (qMDP) as a semantic model of nondeterministic and concurrent quantum programs. It is shown by examples that qMDPs can be used in analysis of quantum algorithms and protocols. We study various reachability problems of qMDPs both for the finite-horizon and for the infinite-horizon. The (un)decidability and complexity of these problems are settled, and the relationship between one of them and the joint spectral radius problem, a long-standing open problem in matrix analysis and control theory, is clarified. Some of these results show a certain separation between the MDP and qMDP models. We also develop an algorithm for finding an optimal scheduler for a large class of qMDPs. Finally, the results of reachability problems are applied in the analysis of the safety problem for qMDPs.

MSC:
68Q85 Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)
68Q12 Quantum algorithms and complexity in the theory of computing
68Q87 Probability in computer science (algorithm analysis, random structures, phase transitions, etc.)
Software:
LIQUi; Quipper; ScaffCC
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Sanders, J.; Zuliani, P., Quantum programming, (Backhouse, R.; Oliveira, J., Mathematics of Program Construction, Lecture Notes in Computer Science, vol. 1837, (2000), Springer: Springer Berlin, Heidelberg), 80-99 · Zbl 0963.68037
[2] Selinger, P., Towards a quantum programming language, Math. Struct. Comput. Sci., 14, 4, 527-586, (2004) · Zbl 1085.68014
[3] D’Hondt, E.; Panangaden, P., Quantum weakest preconditions, Math. Struct. Comput. Sci., 16, 429-451, (2006) · Zbl 1122.68058
[4] Ying, M., Floyd-Hoare logic for quantum programs, ACM Trans. Program. Lang. Syst., 33, 6, (2012)
[5] Green, A. S.; Lumsdaine, P. L.; Ross, N. J.; Selinger, P.; Valiron, B., Quipper: a scalable quantum programming language, (Proceedings of the 34th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI’13, (2013), ACM: ACM New York, NY, USA), 333-342
[6] JavadiAbhari, A.; Patil, S.; Kudrow, D.; Heckey, J.; Lvov, A.; Chong, F. T.; Martonosi, M., ScaffCC: scalable compilation and analysis of quantum programs, Parallel Comput., 45, 2-17, (2015)
[7] Wecker, D.; Svore, K. M., LIQUi|>: a software design architecture and domain-specific language for quantum computing
[8] Gay, S. J., Quantum programming languages: survey and bibliography, Math. Struct. Comput. Sci., 16, 4, 581-600, (2006) · Zbl 1122.68021
[9] Selinger, P., A brief survey of quantum programming languages, (Kameyama, Y.; Stuckey, P. J., Proceedings of the 7th International Symposium on Functional and Logic Programming, FLOPS 2004, Nara, Japan, April 7-9, 2004, (2004), Springer: Springer Berlin, Heidelberg), 1-6 · Zbl 1122.68359
[10] Ying, M., Foundations of Quantum Programming, (2016), Morgan Kaufmann
[11] Baier, C.; Katoen, J.-P., Principles of Model Checking, (2008), The MIT Press: The MIT Press Cambridge
[12] Ying, M.; Yu, N.; Feng, Y.; Duan, R., Verification of quantum programs, Sci. Comput. Program., 78, 9, 1679-1700, (2013)
[13] Ying, S.; Feng, Y.; Yu, N.; Ying, M., Reachability probabilities of quantum Markov chains, (D’Argenio, P.; Melgratti, H., CONCUR 2013 - Concurrency Theory, Lecture Notes in Computer Science, vol. 8052, (2013), Springer: Springer Berlin, Heidelberg), 334-348 · Zbl 1390.68444
[14] Yu, N.; Ying, M., Reachability and termination analysis of concurrent quantum programs, (Koutny, M.; Ulidowski, I., CONCUR 2012 - Concurrency Theory, Lecture Notes in Computer Science, vol. 7454, (2012), Springer: Springer Berlin, Heidelberg), 69-83 · Zbl 1364.68145
[15] Zuliani, P., Non-deterministic quantum programming, (Proceedings of the 2nd International Workshop on Quantum Programming Languages, no. 33, (2004)), 179-195
[16] Papadimitriou, C. H.; Tsitsiklis, J. N., The complexity of Markov decision processes, Math. Oper. Res., 12, 3, 441-450, (1987) · Zbl 0638.90099
[17] Chatterjee, K.; Doyen, L.; Henzinger, T., Qualitative analysis of partially-observable Markov decision processes, (Hliněný, P.; Kučera, A., Mathematical Foundations of Computer Science 2010, Lecture Notes in Computer Science, vol. 6281, (2010), Springer: Springer Berlin, Heidelberg), 258-269 · Zbl 1287.68104
[18] Nielsen, M. A.; Chuang, I. L., Quantum Computation and Quantum Information, (2010), Cambridge University Press · Zbl 1288.81001
[19] Rota, G.-C.; Strang, W., A note on the joint spectral radius, Indag. Math., 22, 4, 379-381, (1960) · Zbl 0095.09701
[20] Barry, J.; Barry, D. T.; Aaronson, S., Quantum partially observable Markov decision processes, Phys. Rev. A, 90, (2014)
[21] Ambainis, A.; Bach, E.; Nayak, A.; Vishwanath, A.; Watrous, J., One-dimensional quantum walks, (Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing, (2001), ACM), 37-49 · Zbl 1323.81021
[22] Gudder, S., Quantum Markov chains, J. Math. Phys., 49, 7, (2008) · Zbl 1152.81457
[23] Feng, Y.; Yu, N.; Ying, M., Model checking quantum Markov chains, J. Comput. Syst. Sci., 79, 7, 1181-1198, (2013) · Zbl 1311.68086
[24] Li, L.; Feng, Y., Quantum Markov chains: description of hybrid systems, decidability of equivalence, and model checking linear-time properties, Inf. Comput., 244, 229-244, (2015) · Zbl 1329.68119
[25] Feng, Y.; Yu, N.; Ying, M., Reachability analysis of recursive quantum Markov chains, (Chatterjee, K.; Sgall, J., Mathematical Foundations of Computer Science 2013: 38th International Symposium, MFCS 2013, (2013), Springer: Springer Berlin, Heidelberg), 385-396 · Zbl 1400.68073
[26] Lloyd, S.; Mohseni, M.; Rebentrost, P., Quantum principal component analysis, Nat. Phys., 10, 9, 631-633, (2014)
[27] Rebentrost, P.; Mohseni, M.; Lloyd, S., Quantum support vector machine for big data classification, Phys. Rev. Lett., 113, (2014)
[28] Paparo, G. D.; Dunjko, V.; Makmal, A.; Martin-Delgado, M. A.; Briegel, H. J., Quantum speedup for active learning agents, Phys. Rev. X, 4, (2014)
[29] Dong, D.; Chen, C.; Li, H.; Tarn, T.-J., Quantum reinforcement learning, IEEE Trans. Syst. Man Cybern., Part B, 38, 5, 1207-1220, (2008)
[30] Farhi, E.; Gutmann, S., Quantum computation and decision trees, Phys. Rev. A, 58, 915-928, (1998)
[31] Temme, K.; Osborne, T.; Vollbrecht, K. G.; Poulin, D.; Verstraete, F., Quantum Metropolis sampling, Nature, 471, 7336, 87-90, (2011)
[32] Blondel, V. D.; Jeandel, E.; Koiran, P.; Portier, N., Decidable and undecidable problems about quantum automata, SIAM J. Comput., 34, 6, 1464-1473, (2005) · Zbl 1078.81012
[33] Chatterjee, K.; Henzinger, T., Probabilistic automata on infinite words: decidability and undecidability results, (Bouajjani, A.; Chin, W.-N., Automated Technology for Verification and Analysis, Lecture Notes in Computer Science, vol. 6252, (2010), Springer: Springer Berlin, Heidelberg), 1-16 · Zbl 1305.68112
[34] Baier, C.; Bertrand, N.; Grosser, M., On decision problems for probabilistic Buchi automata, Lecture Notes in Computer Science, 4962, 287-301, (2008) · Zbl 1139.68030
[35] Paz, A., Introduction to Probabilistic Automata, Computer Science and Applied Mathematics, (1971), Academic Press, Inc.: Academic Press, Inc. Orlando, FL, USA · Zbl 0234.94055
[36] Gurvits, L., Stability of discrete linear inclusion, Linear Algebra Appl., 231, 47-85, (1995) · Zbl 0845.68067
[37] Tsitsiklis, J. N.; Blondel, V. D., The Lyapunov exponent and joint spectral radius of pairs of matrices are hard - when not impossible - to compute and to approximate, Math. Control Signals Syst., 10, 1, 31-40, (1997) · Zbl 0888.65044
[38] Cheban, D. N.; Mammana, C., Absolute asymptotic stability of discrete linear inclusions, Bul. Acad. Ştiinţe Repub. Mold., 1, 43-68, (2005) · Zbl 1081.39002
[39] Blondel, V. D.; Tsitsiklis, J. N., The boundedness of all products of a pair of matrices is undecidable, Syst. Control Lett., 41, 2, 135-140, (2000) · Zbl 0985.93042
[40] de Alfaro, L., The Verification of Probabilistic Systems Under Memoryless Partial-Information Policies Is Hard, (1999), California Univ. Berkeley, Dept. of Electrical Engineering and Computer Science, Tech. rep.
[41] Knill, E., Conventions for Quantum Pseudocode, (1996), Los Alamos National Laboratory, Tech. rep.
[42] Hirvensalo, M., Various aspects of finite quantum automata, (Ito, M.; Toyama, M., Developments in Language Theory, Lecture Notes in Computer Science, vol. 5257, (2008), Springer: Springer Berlin, Heidelberg), 21-33 · Zbl 1161.68535
[43] Halava, V., Decidable and Undecidable Problems in Matrix Theory, (1997), Turku Centre for Computer Science, Tech. rep.
[44] Gimbert, H.; Oualhadj, Y., Probabilistic automata on finite words: decidable and undecidable problems, (Abramsky, S.; Gavoille, C.; Kirchner, C.; Meyer auf der Heide, F.; Spirakis, P., Automata, Languages and Programming, Lecture Notes in Computer Science, vol. 6199, (2010), Springer: Springer Berlin, Heidelberg), 527-538 · Zbl 1288.68156
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.