zbMATH — the first resource for mathematics

Reachability probabilities of quantum Markov chains. (English) Zbl 1390.68444
D’Argenio, Pedro R. (ed.) et al., CONCUR 2013 – concurrency theory. 24th international conference, CONCUR 2013, Buenos Aires, Argentina, August 27–30, 2013. Proceedings. Berlin: Springer (ISBN 978-3-642-40183-1/pbk). Lecture Notes in Computer Science 8052, 334-348 (2013).
Summary: This paper studies three kinds of long-term behaviour, namely reachability, repeated reachability and persistence, of quantum Markov chains (qMCs). As a stepping-stone, we introduce the notion of bottom strongly connected component (BSCC) of a qMC and develop an algorithm for finding BSCC decompositions of the state space of a qMC. As the major contribution, several (classical) algorithms for computing the reachability, repeated reachability and persistence probabilities of a qMC are presented, and their complexities are analysed.
For the entire collection see [Zbl 1269.68020].

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
Full Text: DOI