×

Decomposition of quantum Markov chains and its applications. (English) Zbl 1391.68079

Summary: Markov chains have been widely employed as a fundamental model in the studies of probabilistic and stochastic communicating and concurrent systems. It is well-understood that decomposition techniques play a key role in reachability analysis and model-checking of Markov chains. (Discrete-time) quantum Markov chains have been introduced as a model of quantum communicating systems and also a semantic model of quantum programs. The BSCC (Bottom Strongly Connected Component) and stationary coherence decompositions of quantum Markov chains were introduced in [V. Umanità, Probab. Theory Relat. Fields 134, No. 4, 603–623 (2006; Zbl 1130.46039); S. Ying et al., Lect. Notes Comput. Sci. 8052, 334–348 (2013; Zbl 1390.68444); B. Baumgartner and H. Narnhofer, Rev. Math. Phys. 24, No. 2, 1250001, 30 p. (2012; Zbl 1258.81056)]. This paper presents a new decomposition technique, namely periodic decomposition, for quantum Markov chains. We further establish a limit theorem for them. As an application, an algorithm to find a maximum dimensional noiseless subsystem of a quantum communicating system is given using decomposition techniques of quantum Markov chains.

MSC:

68Q60 Specification and verification (program logics, model checking, etc.)
60J10 Markov chains (discrete-time Markov processes on discrete state spaces)
68Q12 Quantum algorithms and complexity in the theory of computing
68Q85 Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)
68Q87 Probability in computer science (algorithm analysis, random structures, phase transitions, etc.)
81P68 Quantum computation
81S25 Quantum stochastic calculus
PDFBibTeX XMLCite
Full Text: DOI arXiv Link

References:

[1] Wolf, M. M., Quantum channels & operations: guided tour, Lecture notes, available at
[2] Ying, M.; Yu, N.; Feng, Y.; Duan, R., Verification of quantum programs, Sci. Comput. Program., 78, 1679-1700 (2013)
[3] Umanità, V., Classification and decomposition of quantum Markov semigroups, Probab. Theory Relat. Fields, 134, 4, 603-623 (2006) · Zbl 1130.46039
[4] Ying, S.; Feng, Y.; Yu, N.; Ying, M., Reachability probabilities of quantum Markov chains, (International Conference on Concurrency Theory (2013), Springer), 334-348 · Zbl 1390.68444
[5] Baumgartner, B.; Narnhofer, H., The structures of state space concerning quantum dynamical semigroups, Rev. Math. Phys., 24, 02, Article 1250001 pp. (2012) · Zbl 1258.81056
[6] Grimmett, G.; Stirzaker, D., Probability and Random Processes (2001), Oxford University Press · Zbl 1015.60002
[7] Baier, C.; Katoen, J.-P.; Larsen, K. G., Principles of Model Checking (2008), MIT Press
[8] Davies, E., Quantum stochastic processes, Commun. Math. Phys., 15, 4, 277-304 (1969) · Zbl 0184.54102
[9] Davies, E., Quantum stochastic processes ii, Commun. Math. Phys., 19, 2, 83-105 (1970) · Zbl 0199.28202
[10] Lindblad, G., On the generators of quantum dynamical semigroups, Commun. Math. Phys., 48, 2, 119-130 (1976) · Zbl 0343.47031
[11] Fagnola, F.; Rebolledo, R., On the existence of stationary states for quantum dynamical semigroups, J. Math. Phys., 42, 3, 1296-1308 (2001) · Zbl 1013.81031
[12] Ambainis, A., Quantum walks and their algorithmic applications, Int. J. Quantum Inf., 1, 04, 507-518 (2003) · Zbl 1069.81505
[13] Kempe, J., Quantum random walks: an introductory overview, Contemp. Phys., 44, 4, 307-327 (2003)
[14] Yu, N.; Ying, M., Reachability and termination analysis of concurrent quantum programs, (International Conference on Concurrency Theory (2012), Springer), 69-83 · Zbl 1364.68145
[15] Carbone, R.; Pautrat, Y., Irreducible decompositions and stationary states of quantum channels, Rep. Math. Phys., 77, 3, 293-313 (2016) · Zbl 1351.81025
[16] Chiaverini, J.; Leibfried, D.; Schaetz, T.; Barrett, M.; Blakestad, R.; Britton, J.; Itano, W.; Jost, J.; Knill, E.; Langer, C., Realization of quantum error correction, Nature, 432, 7017, 602-605 (2004)
[17] Choi, M.-D.; Kribs, D. W., Method to find quantum noiseless subsystems, Phys. Rev. Lett., 96, 5, Article 050501 pp. (2006)
[18] Kribs, D.; Laflamme, R.; Poulin, D., Unified and generalized approach to quantum error correction, Phys. Rev. Lett., 94, 18, Article 180501 pp. (2005)
[19] Nielsen, M. A.; Chuang, I. L., Quantum Computation and Quantum Information (2010), Cambridge University Press · Zbl 1288.81001
[20] Paulsen, V., Completely Bounded Maps and Operator Algebras, vol. 78 (2002), Cambridge University Press · Zbl 1029.47003
[21] Horn, R. A.; Johnson, C. R., Matrix Analysis (2012), Cambridge University Press
[22] Fagnola, F.; Pellicer, R., Irreducible and periodic positive maps, Commun. Stoch. Anal., 3, 3, 407-418 (2009) · Zbl 1331.46052
[23] Carbone, R.; Pautrat, Y., Open quantum random walks: reducibility, period, ergodic properties, Ann. Henri Poincaré, 17, 99-135 (2016) · Zbl 1333.81205
[24] Levin, D. A.; Peres, Y.; Wilmer, E. L., Markov Chains and Mixing Times (2009), American Mathematical Soc.
[25] Wielandt, H., Unzerlegbare, nicht negative matrizen, Math. Z., 52, 1, 642-648 (1950) · Zbl 0035.29101
[26] Sanz, M.; Pérez-García, D.; Wolf, M. M.; Cirac, J. I., A quantum version of Wielandt’s inequality, IEEE Trans. Inf. Theory, 56, 9, 4668-4673 (2010) · Zbl 1366.81131
[27] Liu, C.; Petulante, N., On limiting distributions of quantum Markov chains, Int. J. Math. Math. Sci., 2011, Article 740816 pp. (2011) · Zbl 1225.81080
[28] Blume-Kohout, R.; Ng, H. K.; Poulin, D.; Viola, L., Information-preserving structures: a general framework for quantum zero-error information, Phys. Rev. A, 82, 6, Article 062306 pp. (2010)
[29] Li, Y.; Ying, M., (Un) decidable problems about reachability of quantum systems, (International Conference on Concurrency Theory (2014), Springer), 482-496 · Zbl 1417.68042
[30] Barry, J.; Barry, D. T.; Aaronson, S., Quantum partially observable Markov decision processes, Phys. Rev. A, 90, 3, Article 032311 pp. (2014)
[31] Ying, S.; Ying, M., Reachability analysis of quantum Markov decision processes, arXiv preprint · Zbl 1407.68341
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.