{'fraction_non_alphanumeric': 0.054994695595633275, 'fraction_numerical': 0.009547927860100612, 'mean_word_length': 3.726949207376254, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 9, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Reachability Probabilities of Quantum Markov Chains

This paper studies three kinds of long-term behaviours, 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.

and it was used in termination checking of concurrent quantum programs. However, reachability studied in [24] can be properly described as qualitative reachability because only algorithms for computing reachable subspaces but not reachability probabilities were developed. This paper is a continuation of [24] and aims at quantitative reachability analysis for qMCs. More precisely, the main purpose of this paper is to develop (classical) algorithms for computing the reachability, repeated reachability and persistence probabilities of qMCs.
Reachability analysis techniques for classical MCs heavily depends on algorithms for graph-reachability problems, in particular for finding bottom strongly connected components (BSCCs) of the underlying graph of a MC (see [2,Section 10.1.2]). Such algorithms have been intensively studied by the graph algorithms community since early 1970's (see [5, Part VI]; [22]), and are ready to be directly adopted in reachability analysis of MCs. However, we don't have the corresponding algorithms for qMCs in hands and have to start from scratch. So, in order to conduct reachability analysis for qMCs we introduce the notion of BSCC and develop an algorithm for finding BSCC decomposition for qMCs in this paper. Interestingly, there are some essential differences between BSCCs in the classical and quantum cases. For example, BSCC decomposition of a qMC is unnecessary to be unique. Also, classical algorithms for finding BSCCs like depth-first search cannot be directly generalised to qMCs. Instead, it requires very different ideas to develop algorithms for finding BSCCs of qMCs, appealing to matrix operation algorithms [5, Chapter 28] through matrix representation of super-operators. The major challenge in dealing with quantum BSCCs, which would not arise in classical BSCCs at all, is to maintain the linear algebraic structure underpinning quantum systems. We believe that these results for quantum BSCCs obtained in this paper are also of independent significance. This paper is organised as follows. The preliminaries are presented in Sec. 2; in particular we recall the notion of qMC and define the graph structure of a qMC. The notion of BSCC of a qMC is introduced in Sec. 3, where a characterisation of quantum BSCC is given in terms of the fixed points of super-operators, and an algorithm for checking whether a subspace of the state Hilbert space of a qMC is a BSCC is given. In Sec. 4, we define the notion of transient subspace of a qMC and show that the state space of a qMC can be decomposed into the direct sum of a transient subspace and a family of BSCCs. Furthermore, it is proved that although such a decomposition is not unique, the dimensions of its components are fixed. In particular, an algorithm for constructing BSCC decomposition of qMCs is found. With the preparation in Secs. 3 and 4, we examine reachability of a qMC in Sec. 5, where an algorithm for computing reachability probability is presented. An algorithm for computing repeated reachability and persistence probabilities is finally developed in Sec. 6. Sec. 7 is a brief conclusion.

Basics of Quantum Theory
For convenience of the reader, we recall some basic notions from quantum theory; for details we refer to [17]. The state space of a quantum system is a Hilbert space. In this paper, we only consider a finite-dimensional Hilbert space H, which is just a finitedimensional complex vector space with inner product. The inner product of two vectors |φ , |ψ ∈ H is denoted by φ|ψ . A pure quantum state is a normalised vector |φ in H with φ|φ = 1. We say that two vectors |φ and |ψ are orthogonal, written |φ ⊥|ψ , if φ|ψ = 0. A mixed state is represented by a density operator, i.e. a positive operator ρ on H with tr(ρ) = 1, or equivalently a positive semi-definite and trace-one n × n matrix if dim H = n. In particular, for each pure state |ψ , there is a corresponding density operator ψ = |ψ ψ|. For simplicity, we often use pure state |ψ and density operator ψ interchangeably. A positive operator ρ is called a partial density operator if trace tr(ρ) ≤ 1. The set of partial density operators on H is denoted by D(H). The support supp(ρ) of a partial density operator ρ ∈ D(H) is defined to be the space spanned by the eigenvectors of ρ with non-zero eigenvalues. The set of all (bounded) operators on H, i.e. d × d complex matrices with d = dim H, is denoted by B(H).
For any set V of vectors in H, we write spanV for the subspace of H spanned by V ; that is, it consists of all finite linear combinations of vectors in V . Two subspaces X and Y of H are said to be orthogonal, written X⊥Y , if |φ ⊥|ψ for any |φ ∈ X and |ψ ∈ Y . The ortho-complement X ⊥ of a subspace X of H is the subspace of vectors orthogonal to all vectors in X. An operator P is called the projection onto a subspace X if P |ψ = |ψ for all |ψ ∈ X and P |ψ = 0 for all |ψ ∈ X ⊥ . We write P X for the projection onto X. According to the theory of quantum measurements, for any density operator ρ, trace tr(P X ρ) is the probability that the mixed state ρ lies in subspace X. Let {X k } be a family of subspaces of H. Then the join of {X k } is defined by In particular, we write X ∨ Y for the join of two subspaces X and Y . It is easy to see that k X k is the smallest subspace of H that contains all X k .
Composed quantum systems are modeled by tensor products. If a quantum system consists of two subsystems with state spaces H 1 and H 2 , then its state space is H = H 1 ⊗ H 2 , which is the Hilbert space spanned by vectors |ψ 1 |ψ 2 = |ψ 1 ⊗ |ψ 2 with |ψ 1 ∈ H 1 and |ψ 2 ∈ H 2 . For any operators A 1 on H 1 and A 2 on H 2 , their tensor product A 1 ⊗ A 2 is defined by for all |ψ 1 ∈ H 1 and |ψ 2 ∈ H 2 together with linearity.
The evolution of a closed quantum system is described as a unitary operator, i.e. an operator U on H with U † U = U U † = I, where I is the identity on H. A pure state |φ becomes U |φ after this unitary evolution U , while a mixed state ρ becomes U ρU † . The dynamics of an open quantum system is described by a super-operator, i.e. a linear map E from the space of linear operators on H into itself, satisfying the following conditions: In this paper, we only consider trace-preserving super-operators. Each super-operator has a Kraus operator-sum representation:

Quantum Markov Chains
Now we are ready to introduce the notion of quantum Markov chain. Recall that a Markov chain is a pair S, P , where S is a finite set of states, and P is a matrix of transition probabilities, i.e. a mapping P : for every s ∈ S, where P (s, t) is the probability of going from s to t. A quantum Markov chain is a quantum generalisation of a Markov chain where the state space of a Markov chain is replaced by a Hilbert space and its transition matrix is replaced by a super-operator.

Definition 1. A quantum Markov chain is a pair G = H, E , where H is a finitedimensional Hilbert space, and E is a super-operator on H.
The behaviour of a quantum Markov chain can be described as follows: if currently the process is in a mixed state ρ, then it will be in state E(ρ) in the next step. Both ρ and E(ρ) can be written as statistical ensembles: where p i , q j ≥ 0 for all i, j, and i p i = j q j = 1. So, super-operator E can be understood as an operation that transfers statistical ensemble {(p i , |φ i )} to {(q j , |ψ j )}.
In this way, a quantum Markov chain can be seen as a generalisation of a Markov chain.

Graphs in Quantum Markov Chains
There is a natural graph structure underlying a quantum Markov chain. This can be seen clearly by introducing adjacency relation in it. To this end, we first introduce an auxiliary notion. The image of a subspace X of H under a super-operator E is defined to be Definition 3. 1. A sequence π = ρ 0 → ρ 1 → · · · → ρ n of adjacent density operators in a quantum Markov chain G is called a path from ρ 0 to ρ n in G, and its length is |π| = n. 2. For any density operators ρ and σ, if there is a path from ρ to σ then we say that σ is reachable from ρ in G.
The following lemma is very useful for our later discussion.

Basic Definitions
The notion of bottom strongly connected component plays an important role in model checking Markov chains. In this section, we extend this notion to the quantum case. We first introduce an auxiliary notation. Let X be a subspace of a Hilbert space, and let E be a super-operator on H. Then the restriction of E on X is defined to be super-operator E| X with E| X (ρ) = P X E(ρ)P X for all ρ ∈ D(X), where P X is the projection onto X.

Definition 5.
Let G = H, E be a quantum Markov chain. A subspace X of H is called strongly connected in G if for any |ϕ , |ψ ∈ X, we have |ϕ ∈ R GX (ψ) and |ψ ∈ R GX (ϕ), where quantum Markov chain G X = X, E X is the restriction of G on X.
We write SC(G) for the set of strongly connected subspaces of H in G. It is easy to see that (SC(G), ⊆) is an inductive set; that is, for any subset {X i } of SC(G) that is linearly ordered by ⊆, we have i X i ∈ SC(G). Thus, by Zorn lemma we assert that there exists a maximal element in SC(G).

Definition 6. A maximal element of (SC(G), ⊆) is called a strongly connected component (SCC) of G.
To define bottom strongly connected component, we need an auxiliary notion of invariant subspace.
It is easy to see that if super-operator E has the Kraus representation Recall that in a classical Markov chain, the probability of staying in an invariant subset is non-decreasing. A quantum generalisation of this fact is presented in the following: Now we are ready to introduce the key notion of this section.

Definition 8. Let G = H, E be a quantum Markov chain. Then a subspace X of H is called a bottom strongly connected component (BSCC) of G if it is a SCC of G and invariant in G.
Example 1. Consider quantum Markov chain G = H, E with state space H = span{|0 , · · · , |4 } and super-operator where the operators E i (i=1,...,5) are given as follows: and the states used above are defined by It is easy to see that B = span{|0 , |1 } is a BSCC of quantum Markov chain G, as for The following lemma clarifies the relationship between different BSCCs.

Characterisations of BSCCs
This subsection purports to give two characterisations of BSCCs. The first is presented in terms of reachable spaces.
To present the second characterisation, we need the notion of fixed point of superoperator.
The second characterisation of BSCCs establishes a connection between BSCCs and minimal fixed point states.

Theorem 2. A subspace X is a BSCC of quantum Markov chain G = H, E if and only
if there exists a minimal fixed point state ρ of E such that supp(ρ) = X. Furthermore, ρ is actually the unique fixed point state, up to normalisation, with the support included in X.

Checking BSCCs
We now present an algorithm that decides whether or not a given subspace is a BSCC of a quantum Markov chain (see Algorithm 1). The correctness and complexity of this algorithm are given in the following theorem.

Decompositions of the State Space
A state in a classical Markov chain is transient if there is a non-zero probability that the process will never return to it, and a state is recurrent if from it the returning probability is 1. It is well-known that a state is recurrent if and only if it belongs to some BSCC in a finite-state Markov chain, and thus the state space of a classical Markov chain can be decomposed into the union of some BSCCs and a transient subspace [2], [16]. The aim of this section is to prove a quantum generalisation of this result.
for any ρ ∈ D(H), where P X is the projection onto X.

Algorithm 1: CheckBSCC(X)
input : A quantum Markov chain G = H, E and a subspace X ⊆ H output: The above definition is stated in a "double negation" way. Intuitively, it means that the probability in a transient subspace will be eventually zero. To understand this definition better, let us recall that in a classical Markov chain, a state s is said to be transient if the system starting from s will eventually return to s with probability less than 1. It is well-known that in a finite-state Markov chain, this is equivalent to that the probability at this state will eventually become 0. In the quantum case, the property "eventually return" can be hardly described without measurements, and measurements will disturb the behaviour of the systems. So, we choose to adopt the above definition.
To give a characterisation of transient subspaces, we need the notion of the asymptotic average of a super-operator E, which is defined to be It is easy to see from [21, Proposition 6.3, Proposition 6.9] that E ∞ is a super-operator as well.
We now turn to examine the structure of the image of the state space H under superoperator E. Combining Theorems 4 and 5, we see that the state space of a quantum Markov chain G = H, E can be decomposed into the direct sum of a transient subspace of a family of BSCCs: where B i 's are orthogonal BSCCs of G. A similar decomposition was recently obtained in [18] for a special case of E 2 = E. The above decomposition holds for any superoperator E and thus considerably generalises the corresponding result in [18]. The BSCC and transient subspace decomposition of a classical Markov chain is unique. However, it is not the case for quantum Markov chains; a trivial example is that E is the identity operator, for which any 1-dimensional subspace of H is a BSCC, and thus for each orthonormal basis {|i } of H, i span{|i } is an orthogonal decomposition of H. The following is a more interesting example.
Example 2. Let quantum Markov chain G = E, H be given as in Example 1. Then The relation between different decompositions of a quantum Markov chain is clarified by the following theorem.

Theorem 6. Let G = H, E be a quantum Markov chain, and let
To conclude this section, we present an algorithm for finding a BSCC and transient subspace decomposition of a quantum Markov chain (see Algorithm 2).

Reachability Probabilities
The traditional way to define reachability probabilities in classical Markov chains is first introducing a probability measure based on cylinder sets of finite paths of states. The probability of reaching a set T is then the probability measure of the set of paths which include a state from T . Typically, reachability probabilities can be obtained by solving a system of linear equations, which is easy and numerically efficient. In quantum Markov chains, however, it is even not clear how to define such a probability measure. Thus it seems hopeless to extend reachability analysis to the quantum case in this way.
Fortunately, there is another way to compute the reachability probability in a classical Markov chain S, P . Given a set of states T ⊆ S, we first change the original Markov chain into a new one S, P ′ by making states in T absorbing. Then the reachability probability of T is simply the limit of the probability accumulated in T , when the time goes to infinity. It turns out that this equivalent definition can be extended into the quantum case as follows. where E = P G + E • (I − P G ) is the super-operator which first performs the projective measurement {P G , I − P G } and then applies the identity operator I or E depending on the measurement outcome.
Obviously the limit in the above definition exists, as the probabilities tr(P G E i (ρ)) are nondecreasing in i.
To compute the reachability probability, we first note the subspace G is invariant under E. Thus G, E is again a quantum Markov chain. Since E(I G ) = I G and E ∞ (G) = G, we can decompose G into a set of orthogonal BSCCs according to E by Theorem 5. The following lemma shows a connection between the limit probability of hitting a BSCC and the probability that the asymptotic average of the initial state lies in the same BSCC. Our next results assert that if a quantum Markov chain starts from a pure state in a BSCC then its evolution sequence ψ, E(ψ), E 2 (ψ), · · · will hit a subspace with non-zero probability infinitely often provided X is not orthogonal to that BSCC. They establishes indeed a certain fairness and thus can be seen as quantum generalisations of Theorems 10.25 and 10.27 in [2]. It is well-known that in the quantum world a measurement will change the state of the measured system. Consequently, fairness naturally splits into two different versions in quantum Markov chains.

Lemma 5. (Measure-once fairness) Let B be a BSCC of quantum Markov chain G =
H, E , and X a subspace which is not orthogonal to B. Then for any |ψ ∈ B, it holds that tr(P X E i (ψ)) > 0 for infinitely many i. where E = P X ⊥ • E, and X ⊥ is the ortho-complement of X in H.
Lemma 6 is stated also in a "double negation" way. To best understand it, let us assume that at each step after E is applied, we perform a projective measurement {P X , P X ⊥ }. If the outcome corresponding to P X is observed, the process terminates immediately; otherwise, it continues with another round of applying E. Lemma 6 asserts that the probability of nontermination is asymptotically 0; in other words, if we set X as an absorbing boundary, which is included in BSCC B, the reachability probability will be absorbed eventually. This lemma is indeed a strong version of fairness. Furthermore, we have: It is worth noting that in Theorem 9, X is not required to be a subspace of a BSCC B. The following two examples give some simple applications of Theorem 9.
Example 3. Consider a quantum walk on an n-size cycle [1]. The state space of the whole system is H = H p ⊗ H c , where H p = span{|0 , · · · , |n − 1 } is the position space, and H c = span{|0 , |1 } is the coin space. The evolution of the systems is described by a unitary transformation U = S(I ⊗ H), where the coin operator H is the Hadamard operator, and the shift operator where the arithmetic operations over the index set are understood as modulo n. If we set absorbing boundaries at position 0, then from any initial state |ψ , we know from Theorem 9 that the probability of nontermination is asymptotically 0 because there is no BSCC which is orthogonal to the absorbing boundaries.
Example 4. Consider the quantum Markov chain in Example 1. Let ρ 0 be the initial state, and assume that projective measurement {P 0 = |0 0|, P 1 = I − P 0 } will be performed at the end of each step and P 0 is set as the absorbing boundary. We writẽ ρ k =Ẽ k (ρ 0 ) for the partial density operator after k steps, whereẼ = P 1 • E.
Let D 1 and D 2 be as in Example 2. Then the probabilities in D 1 and D 2 are both 0.5. This means that if supp(P 0 ) is not totally in a BSCC D, then the probability in D may not be absorbed.

Repeated Reachability and Persistence Probabilities
In this section, we consider how to compute two kinds of reachability probabilities, namely "repeated reachability" and "persistence property", in a quantum Markov chain.
Note that E ∞ (H) ⊥ is a transient subspace. We can focus our attention on E ∞ (H).

Definition 12. Let G = H, E be a quantum Markov chain and G a subspace of E ∞ (H).
1. The set of states in E ∞ (H) satisfying the repeated reachability "infinitely often reaching G" is 2. The set of states in E ∞ (H) satisfying the persistence property "eventually always in X" is The set X (G) is defined again in a "double negation" way. Its intuitive meaning can be understood as follows: if the process starts in a state in X (G) and we make G absorbing, then the probability will be eventually absorbed by G.
The following theorem gives a characterisation of X (G) and Y(G) and also clarifies the relationship between them.

Theorem 10. For any subspace
where B ranges over all BSCCs, and the orthogonal complements are taken in E ∞ (H). Now we can define probabilistic persistence and probabilistic repeated reachability.
Definition 13. 1. The probability that a state ρ satisfies the repeated reachability rep(G) is the eventual probability in X (G), starting from ρ:

The probability that a state ρ satisfies the persistence property pers(G) is the eventual probability in Y(G), starting from ρ:
Pr(ρ pers(G)) = lim k→∞ tr(P Y(G) E k (ρ)).
The well-definedness of the above definition comes from the fact that X (G) and Y(G) are invariant. By Theorem 1 we know that the two sequences {tr(P X (G) E k (ρ))} and {tr(P Y(G) E k (ρ))} are non-decreasing, and thus their limits exist. Combining Theorems 4 and 10, we have: Theorem 11. 1. The repeated reachability probability is Pr(ρ pers(G ⊥ )).

The persistence probability is
Finally, we are able to give an algorithm for computing reachability and persistence probabilities (see Algorithm 3). With Theorem 11, Algorithm 3 can also be used to compute repeated reachability probability Pr(ρ rep(G)).

Conclusions
We introduced the notion of bottom strongly connected component (BSCC) of a quantum Markov chain (qMC) and studied the BSCC decompositions of qMCs. This enables us to develop an efficient algorithm for computing repeated reachability and persistence probabilities of qMCs. Such an algorithm may be used to verify safety and liveness properties of physical systems produced in quantum engineering and quantum programs for future quantum computers. Then E ∞ (ρ) can be easily derived from the correspondence |i |i is the (unnormalised) maximally entangled state in H⊗H. 2. We compute the density operator basis by the following three steps: (iii) For each basis matrix A in B, compute positive matrices Then by [21,Proposition 6.8], every element of Q is a fixed point state of E. Replace A by elements of Q after normalisation. Then the resultant B is the required density operator basis. At last, we make the elements in B linearly independent. This can be done by removing elements in B using Guassian elimination. The computational complexity of this step is O(n 6 ). With these steps, we know the total complexity is O(n 6 ).
⊓ ⊔ Proof of Lemma 1. We only prove part 1; for the proof of part 2, see [24]. It follows from

⊓ ⊔
Proof of Lemma 3. We only prove the necessity part; the sufficiency part is obvious. Suppose X is a BSCC. By the strong connectivity of X, we have R G (ψ) ⊇ X for all |ψ ∈ X. On the other hand, we have from the invariance of X that E(X) ⊆ X. Thus R G (φ) = X for any non-zero vector |φ in X. Before proving Theorem 2, we recall some basic properties of fixed point states. For more details, we refer to [3,21].

([3, Lemma 2]) If ρ is a fixed point state for E, then supp(ρ) is an invariant sub-
space. Conversely, if X is an invariant subspace of E, then there exists a fixed point state ρ X such that supp(ρ X ) ⊆ X.
Proof of Theorem 2. We first prove the sufficiency part. Let ρ be a minimal fixed point state such that supp(ρ) = X. Then by Lemma 9.2, X is an invariant subspace. To show that X is a BSCC, by Lemma 3 it suffices to prove for any |φ ∈ X, R G (φ) = X. Suppose conversely there exists |ψ ∈ X such that R G (ψ) X. Then by Lemma 1 R G (ψ) is an invariant subspace of E as well. By Lemma 9.2, we can find a fixed point state ρ ψ with supp(ρ ψ ) ⊆ R G (ψ) X, contradicting the assumption that ρ is minimal.
For the necessity part, let X be a BSCC. Then X is invariant, and by Lemma 9.2, we can find a minimal fixed point state ρ X with supp(ρ X ) ⊆ X. Take |φ ∈ supp(ρ X ). By Lemma 2 we have R G (φ) = X. But on the other hand, by Lemma 9.2 again we have supp(ρ X ) is invariant, so R G (φ) ⊆ supp(ρ X ). Thus supp(ρ X ) = X indeed.
Finally, the uniqueness of ρ comes from the observation that whenever ρ and σ are both fixed point states of E, then so is λρ + γσ, provided that it is nonzero, for any real numbers λ and γ.
⊓ ⊔ Proof of Theorem 3. By Theorem 2, to check whether a subspace X is a BSCC, it is sufficient to check the following two properties: 1. X is invariant; 2. Every fixed point state of E| X has X as its support.
That justifies the correctness of Algorithm 1. The complexity of this algorithm mainly comes from the statement ( * ) which, according to Lemma 7.2, can be computed in time O(n 6 ).

⊓ ⊔
Proof of Theorem 4. Let P be the projection onto T E , ρ ∈ D(H), and p k = tr(P E k (ρ)).
Since E ∞ (H) is an invariant subspace, by Theorem 1 we have p k is non-increasing.
Thus the limit p ∞ = lim k→∞ p k does exist. Furthermore, noting that supp(E ∞ (ρ)) ⊆ E ∞ (H), we have Thus p ∞ = 0, and T E is transient by the arbitrariness of ρ.
To show that T E is the largest transient subspace of G, note that supp(E ∞ (I)) = E ∞ (H). Let σ = E ∞ (I/d). Then by Lemma 8, σ is a fixed point state with supp(σ) =

⊓ ⊔
The following corollary is immediately from Lemma 10. Proof. If ρ is minimal, then by Theorem 2, supp(ρ) is itself a BSCC and we are done. Otherwise, we apply Lemma 10 to obtain two fixed point states of E with smaller orthogonal supports. Repeating this procedure, we will get a set of minimal fixed point states ρ 1 , · · · , ρ k with mutually orthogonal supports, and But we also have B 1 ⊥T E , a contradiction as v j=1 D j T E = H.
Suppose we have b i = d i for any i < n. We claim b n = d n as well. Otherwise let, say, b n < d n . Then from Lemma 2.2, we have On the other hand, we have does exist, and tr(P Bi E ∞ (ρ)) ≤ q i . Moreover This implies q i = tr(P Bi E ∞ (ρ)).

⊓ ⊔
Proof of Theorem 8. The claim that is directly from Lemma 4 and Theorem 5, and the time complexity of computing this quantity follows from Lemma 7.1.

⊓ ⊔
Proof of Lemma 5. As X is not orthogonal to B, we can always find a pure state |φ ∈ B such that P X |φ = 0. Now for any |ψ ∈ B, if there exists N such that tr(P X E k (ψ)) = 0 for any k > N . Then |φ ∈ R G (E N +1 (ψ)), which means that R G (E N +1 (ψ)) is a proper invariant subspace of B. This contradicts the assumption that B is a BSCC. Thus we have tr(P X E i (ψ)) > 0 for infinitely many i.

⊓ ⊔
Proof of Lemma 6. Similar to Proposition 6.2 in [21] and Lemma 4.1 in [25], we can show that the limit exists as well. For any |ψ ∈ B, we claim that ρ ψ := E ∞ (ψ) is a zero operator. Otherwise, it is easy to check that ρ ψ is a fixed point of E. Furthermore, from the fact that we have tr(P X E(ρ ψ )) = 0 as E is trace-preserving. Thus P X E(ρ ψ )P X = 0, and ρ ψ is also a fixed point of E. Note that supp(ρ ψ ) ⊆ X ⊥ ∩ B. This contradicts with the assumption that B is a BSCC, by Theorem 2.
With the claim, and the fact that tr( E i (ψ)) is non-increasing in i, we immediately have lim i→∞ tr( E i (ψ)) = 0.
⊓ ⊔ Proof of Theorem 9. Similar to the proof of Lemma 6.

⊓ ⊔
To prove Theorem 10, we need the following lemma.
Lemma 11. Suppose E ∞ (H) has a proper invariant subspace S. Then for any density operator ρ with supp(ρ) ⊆ E ∞ (H) and any integer k, we have tr(P S E k (ρ)) = tr(P S ρ) where P S is the projection onto S.
For any BSCC B ⊆ G, from Lemmas 8.2 and 9.2 we have B ⊆ E ∞ (H). Furthermore, as B is a BSCC, for any |ψ ∈ B and any i, supp(E i (ψ)) ⊆ B ⊆ G. Thus B ⊆ Y(G), and the result follows from the fact that Y(G) is a subspace.
For any |ψ ∈ Y(G), note that ρ ψ := E ∞ (ψ) is a fixed point state. Let X = supp(ρ ψ ). We claim |ψ ∈ X. This is obvious if X = E ∞ (H). Otherwise, as E ∞ (I H ) is a fixed point state and E ∞ (H) = supp(E ∞ (I H )), by Lemma 10 we have E ∞ (H) = X ⊕ X ⊥ , where X ⊥ , the ortho-complement of X in E ∞ (H), is also invariant. As X is again a direct sum of some orthogonal BSCCs, by Lemma 4 we have lim i→∞ tr(P X E i (ψ)) = tr(P X E ∞ (ψ)) = 1; that is, lim i→∞ tr(P X ⊥ E i (ψ)) = 0.
By the definition of Y(G), there exists M ≥ 0, such that supp(E i (ψ)) ⊆ G for all i ≥ M . Thus Furthermore, since X can be decomposed into the direct sum of some BSCCs, we have X ⊆ B⊆G B. Then the result follows by noting |ψ ∈ X.
First, from Claims 1 and 2 above we have Y(G ⊥ ) ⊆ G ⊥ and G ′ := Y(G ⊥ ) ⊥ is invariant. Thus G ⊆ Y(G ⊥ ) ⊥ , and E is a also super-operator on G ′ ; that is, the pair G ′ , E is again a quantum Markov chain. Furthermore, Claim 1 implies that any BSCC in G ⊥ is also contained in Y(G ⊥ ). Thus there is no BSCC in G ′ ∩ G ⊥ . By Theorem 9, for any |ψ ∈ G ′ , lim i→∞ tr[(P G ⊥ • E) i (ψ)] = 0. Thus |ψ ∈ X (G) by definition.
Suppose a BSCC B ⊆ G. Then we have tr(P B I G ⊥ ) = 0, and so tr(P B E i (I G ⊥ )) = 0 for any i ≥ 0 by Lemma 11. Thus tr(P B E ∞ (I G ⊥ )) = 0, leading to B ⊥ E ∞ (G ⊥ ). Therefore B ⊆ E ∞ (G ⊥ ) ⊥ . Then the result follows from the fact that E ∞ (G ⊥ ) ⊥ is a subspace.
By Corollary 1, E ∞ (G ⊥ ) ⊥ can be decomposed into direct sum of BSCCs B 1 , B 2 , · · · . For any B i , we have tr(P Bi E ∞ (I G ⊥ )) = 0. Thus tr(P Bi I G ⊥ ) = 0, meaning that B i ⊥ G ⊥ . Therefore B i ⊆ G, and the result holds.
The invariance of X (G) and Y(G) is already included in Claims 1 and 2. This complete the proof. ⊓ ⊔