TY - GEN
T1 - Reachability probabilities of quantum Markov chains
AU - Ying, Shenggang
AU - Feng, Yuan
AU - Yu, Nengkun
AU - Ying, Mingsheng
PY - 2013
Y1 - 2013
N2 - 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.
AB - 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.
KW - persistence
KW - quantum Markov chains
KW - reachability
UR - https://www.scopus.com/pages/publications/84882789057
U2 - 10.1007/978-3-642-40184-8_24
DO - 10.1007/978-3-642-40184-8_24
M3 - Conference contribution
AN - SCOPUS:84882789057
SN - 9783642401831
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 334
EP - 348
BT - Concurrency Theory - 24th International Conference, CONCUR 2013, Proceedings
T2 - 24th International Conference on Concurrency Theory, CONCUR 2013
Y2 - 27 August 2013 through 30 August 2013
ER -