Model Checking Quantum Systems --- A Survey <s> Definition 4.1 (Quantum Markov chains [47]): <s> An inexpensive faucet aerator is provided by three molded parts and a thin metal cup that holds two of the molded parts in assembled relationship. The first molded part is an elongated annulus provided with upstream and downstream recesses separated by an inner ring that helps to break up the liquid flow and serves as an abutment to support a second molded, jet-forming, part in the upstream recess and is arranged to be engaged by the third, molded, part located in the downstream recess and aiding in defining air intake means to the aerator. <s> BIB001 </s> Model Checking Quantum Systems --- A Survey <s> Definition 4.1 (Quantum Markov chains [47]): <s> 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. <s> BIB002 </s> Model Checking Quantum Systems --- A Survey <s> Definition 4.1 (Quantum Markov chains [47]): <s> We present quantum observable Markov decision processes (QOMDPs), the quantum analogs of partially observable Markov decision processes (POMDPs). In a QOMDP, an agent is acting in a world where the state is represented as a quantum state and the agent can choose a superoperator to apply. This is similar to the POMDP belief state, which is a probability distribution over world states and evolves via a stochastic matrix. We show that the existence of a policy of at least a certain value has the same complexity for QOMDPs and POMDPs in the polynomial and infinite horizon cases. However, we also prove that the existence of a policy that can reach a goal state is decidable for goal POMDPs and undecidable for goal QOMDPs. <s> BIB003 </s> Model Checking Quantum Systems --- A Survey <s> Definition 4.1 (Quantum Markov chains [47]): <s> 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 [1] and also a semantic model of quantum programs [2]. The BSCC (Bottom Strongly Connected Component) and stationary coherence decompositions of quantum Markov chains were introduced in [3, 4, 5]. 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. <s> BIB004
A quantum Markov chain is a triple (H, E, H 0 ), where H and H 0 are the same as in Definition 3.1, and E is a super-operator on H. A quantum Markov chain starts in an initial state in H 0 , and at each step it performs (the same) quantum operation modelled by the super-operator E. Note that the (discrete-time) dynamics of closed quantum systems are usually depicted by unitary operators, and the behaviours of open quantum systems are described by super-operators (see BIB001 , Section 8.2). Obviously, the notion of quantum automata can be generalised by replacing unitary operators U α (α ∈ Act) in Definition 3.1 by super-operators E α (α ∈ Act). Furthermore, quantum Markov decision processes can be defined by introducing decision strategies into such generalised quantum automata BIB003 ,  . Several algorithms for checking reachability of quantum Markov chains and quantum Markov decision processes were developed in BIB002 ,  . As in checking classical Markov chains and Markov decision processes, graph reachability is a key to these algorithms. However, classical graph theory is not suited to our purpose; instead a new theory of quantum graphs (i.e. graphs in a Hilbert space with adjacency relation induced by a super-operator) was developed, and in particular, an algorithm for the BSCC (bottom strongly connected components) decomposition of the state Hilbert spaces was found in BIB002 . Another decomposition technique, namely periodic decomposition, for quantum Markov chains was recently proposed in BIB004 .