Clustering quantum Markov chains on trees associated with open quantum random walks

1.   Introduction

Markov chains and random walks find widespread applications in several areas. Markov chains-based algorithms play crucial in unsupervised Machine learning and networks, such as the Markov clustering algorithm ^[41,42], which is proven to be one of the most powerful approaches for detecting clustered structures. Quantum Markov Chains (QMCs) ^[1] have been introduced long ago ^[2,6] and found important applications in physics ^{[7,14,15,16,40]}. QMCs on trees ^{[4,5,22,23,30,36,38]} have been studied in connection with statistical mechanical models ^[3,24,27,36]. In particular, quantum phase transitions were investigated for Pauli type models ^[19,20,21]. A variety of aspects of quantum Markov states on trees have been investigated ^{[26,27,28,29]}.

Over the last few decades, quantum random walks ^[8] have been the subject of a significant amount of research due to their utility in a variety of domains, such as quantum information and networks ^[33,34]. In ^[8], OQRWs have been introduced in the unitary case. In ^[9], Attal et al. extended this approach and also considered OQRWs on graphs. The inclusion of OQRWs in the general frame of QMCs has been established in ^[12,18] and then extended to QMCs on trees ^[31,32]. Stopping rules and recurrence for QMCs were introduced in ^[37]. In addition, in recent works ^[31,32], QMCs on trees have been associated with OQRWs. This led to further applications, such as quantum phase transitions and recurrence of QMCs on trees ^[11,37].

In quantum statistical mechanics, the clustering property for a state indicates the absence of long-range order ^[17,35]. In ^[30], we investigate the clustering property for a class of QMCs on the Comb graph. In ^[20,39], it was shown that a QMC associated with an XY-Ising model on the Cayley tree satisfy the clustering property. In the present paper, we show that the QMC associated with the disordered phase of a quantum system based on OQRW does not satisfy the clustering property. To the best of our knowledge, non-clustering QMCs on tree have not been addressed previously in the literature. Further relevant problems can be investigated, such as the types of von Neumann algebras associated with the QMCs under consideration, such as ^[25]. The obtained results can have important and promising implications in Markov models in data science.

The paper is organized as follows: Section 2 is devoted to some preliminaries on trees. In Section 3, we introduce QMCs associated with OQRW on trees. Section 4 is dedicated to the main result of the paper.

2.   Preliminaries

Let $\Gamma^{k}_{+} = (V, E)$ be semi-infinite Cayley tree of order $k$. Denote $o\in V$ the root of the tree. Two vertices $x$ and $y$ are called nearest-neighbors if there exists an edge joining them, we denote $x\sim y$. Let $u$ and $v$ be two different vertices, we call edge-path with length $n\in\mathbb{N}$ joining $u$ to $v$ a finite list of vertices $u_1, u_2, \cdots, u_n$ such that $u \sim u_1\sim u_2\sim\cdots\sim u_n = v$. It is well known that, a tree can be characterized through the property that any two distinct vertices are joined by means of a unique edge-path. The distance on the tree $d(u, v)$ between $u$ and $v$ is the length of the unique edge-path joining them. The hierarchical structure of $\Gamma^{k}_{+}$ allows to define the levels

On the levels, a coordinate structure is assigned as follows. For $m\in \mathbb{N}$ and $x\in W_m$ is identified to a n-uplet $x\equiv (\ell_1, \dots, \ell_m)$, where $\ell_j\in\{1, \dots, k\}$, $1\leq j\leq m \,$. The coordinate structure is illustrated in Figure 1 in the case of the Cayley tree of order two. In the above notations, we write

Define

For $\ell_1, \ell_2.\dots, \ell_n\in\{1, 2, \dots, k\}$ and $u = (\ell_1, \ell_2, \dots, \ell_n)\in W_n$ there exists a unique path joining it to the root $o$ given as follows:

Let $u' = (\ell'_1, \ell'_2, \dots, \ell'_m)\in W_m$, the shift $\alpha_u$ on the tree is defined as

In particular, $\alpha_u(o) = u$. For each $u\in W_n$, we define its set of direct successors by

Put

Recall that a graph isomorphism ^[13] is an edge-preserving bijection from a graph $G_1 = (V_1, E_1)$ onto a graph $G_2 = (V_2, E_2)$ such that:

- $\alpha$ is a bijective map from $V_1$ onto $V_2$;

- for every $x, y\in V_1$ one has $x\sim y$ if and only if $\alpha(x)\sim \alpha(y)$.

The sub-tree $\Gamma_{+, u}^{k} = (V_u, E_u)$, whose vertex set is $V_u$, is isomorphic to $\Gamma_{+}^{k}$. For each $n\in \mathbb{N},$ we define

The map $\alpha_u$ is a graph isomorphism from $\Gamma_+^{k} = (V, E)$ onto $\Gamma_{+, u}^{k} = (V_u, E_u)$, we denote its inverse isomorphism by $\alpha_u^{-1}.$

To each vertex $x\in V$, we assign the C$^*$–algebra of observables $\mathcal{A}_x = \mathcal{A}$ with unit ${{\bf 1}\!\!{{\rm{I}}}}_x$. For any finite region $V'\subset V$, we consider the local algebra $\mathcal{A}_{V'} = \bigotimes_{x\in V'}\mathcal{A}_x$. In particular, for each $n$, one defines $\mathcal{A}_{\Lambda_n} = \bigotimes_{u\in\Lambda_n}\mathcal{A}_u$. One has the embedding

where for each finite region $V'\subset V$, one has ${{\bf 1}\!\!{{\rm{I}}}}_{V'} = \bigotimes_{u\in V'}{{\bf 1}\!\!{{\rm{I}}}}_u$. We obtain the following local algebra associated with the increasing set $\{\mathcal{A}_{\Lambda_n}\}_{n\ge 0}$

and its C$^*$-closure ^[10] is the following quasi-local algebra

For $a\in \mathcal{A}$ and $x\in V$, we denote $a^{(x)} = a\otimes {{\bf 1}\!\!{{\rm{I}}}}_{V\setminus\{x\}}$, where $a$ appears at the component $\mathcal{A}_u$ of the infinite tensor product $\mathcal{A}_V$. Notice that, the graph isomorphism $\alpha_u$ defines a $*-$isomorphism $\widetilde{\alpha}_u$ from $\mathcal{A}_V$ into $\mathcal{A}_{V_u}$ satisfying

where for each $y\in \Lambda_{u; \, n}$ by $\alpha^{-1}_u(y)$ we mean the element $x\in \Lambda_n$ satisfying $\alpha_u(x) = y$.

Let $\mathcal{C}\subset\mathcal{B}$ be two C$^*$-algebras. We call transition expectation (TE), any completely positive identity preserving (CP$1$) from $\mathcal{B}$ into $\mathcal{C}$. Let $\mathcal C\subseteq\mathcal B\subseteq \mathcal A$ be unitary C$^\ast$–algebras. Recall that:

● A quasi-conditional expectation (QCE) is a CP$1$ linear map $E :\mathcal A \to \mathcal B$ such that

● A TE is any CP$1$ linear map between two unitary $C^*$-algebras.

The set of states on a C$^*$–algebra $\mathcal{A}$ will be denoted by $\mathcal{S}(\mathcal{A})$.

For a given TE $\mathcal{E}_{W_n}$ from $\mathcal{A}_{\Lambda_{[n, n+1]}}$ into $\mathcal{A}_{W_n}$, the map

is a TE w.r.t. the triplet $\mathcal{A}_{\Lambda_{n-1}}\subset\mathcal{A}_{\Lambda_n}\subset\mathcal{A}_{\Lambda_{n+1}}$. The hierarchical structure of the Cayley tree manifests in the fact that

This allows to consider local TE $\mathcal{E}_u$ from $\mathcal{A}_{\{u\}\cup S(u)}$ into $\mathcal{A}_{u}$. Then the map

defines a TE from $\mathcal{A}_{\Lambda_{[n, n+1]}}$ into $\mathcal{A}_{W_n}$.

Definition 2.1. ^[6] A (backward) QMC on $\mathcal{A}_V$ is defined to be a triplet $(\phi_o, (\mathcal{E}_{n})_{n\ge 0}, (h_{n})_n)$, where

● $\phi_o\in \mathcal{S}(\mathcal{A}_o)$ is an initial state,

● for each $n$, $\mathcal{E}_{n}$ is a TE from $\mathcal{A}_{\Lambda_{[n, n+1]}}$ into $\mathcal{A}_{W_n}$,

● for each $n$, $h_n\in\mathcal{A}_{W_n, +}$ is a positive boundary condition,

such that for each $a\in \mathcal{A}_V$ the limit

exists in the weak-*-topology and defines a state $\varphi$ on $\mathcal{A}_V$, which will be also referred as QMC.

Definition 2.2. ^[38] The triplet $\varphi\equiv \left(\phi_o, (E_{\Lambda_{n}})_{n\ge 0}, (h_{n})_n\right)$ is called a tree-homogeneous QMC (THQMC) if there exists a TE $\mathcal{E}:\mathcal{A}_{\{o\}\cup S(o)} \to \mathcal{A}_{o}$ such that for each $n$

where $id_{\mathcal{A}_{ \Lambda_{n-1}}}$ is the identity map on ${\mathcal{A}_{ \Lambda_{n-1}}}$ and

for some boundary condition $h\in\mathcal{A}_{o; +}$.

In the sequel, for the sake of simplicity we denote $a^{(u)}: = \alpha_u(a)$ for each $a\in \mathcal{A}$ and $u\in V$.

Theorem 2.1. Let $\phi_o$ be a state on $\mathcal{A}_o$ and $\mathcal{E}\colon \mathcal{A}_{\Lambda_1} \to \mathcal{A}_o$ a TE. For $h\in \mathcal{A}_+$, if

then $(\phi_o, \mathcal{E}, h)$ is a THQMC on the algebra $\mathcal{A}_V$.

3.   QMCS on trees associated with OQRW

Let $\mathcal{H}$ and $\mathcal{K}$ be two separable Hilbert spaces. Let $\mathcal{B}(\mathcal{H})$ (respectively $\mathcal{B}(\mathcal{K})$) be the algebra of all bounded operators over $\mathcal{H}$ (respectively $\mathcal{K}$) with identity ${{\bf 1}\!\!{{\rm{I}}}}_{\mathcal{H}}$ (respectively ${{\bf 1}\!\!{{\rm{I}}}}_\mathcal{K}$). Let $\{ |i\rangle \, :\, i\in \Lambda\}$ be an orthonormal basis of $\mathcal{K}$, where $\Lambda$ is a connected graph. The algebra of observables at a given site $u\in V$ is $\mathcal{A}_u = \mathcal{B}({\mathcal{H}})\otimes\mathcal{B}(\mathcal{K}) \equiv \mathcal{B}({\mathcal{H}}\otimes \mathcal{K})$ with identity ${{\bf 1}\!\!{{\rm{I}}}}_u = {{\bf 1}\!\!{{\rm{I}}}}_{\mathcal{H}}\otimes {{\bf 1}\!\!{{\rm{I}}}}_{\mathcal{K}}$. In the notations of the previous section, for each$a\in \mathcal{B}({\mathcal{H}}) \otimes\mathcal{B}(\mathcal{K})$ we denote $\alpha_u(a) = a^{(u)}\in \mathcal{A}_u$. For each $(i, j)\in\Lambda^2$, the quantum transition from the state $|j\rangle$ into the state $|i\rangle$ is implemented by an operator $B_{j}^{i}\in \mathcal{B}(\mathcal{H})$ such that

Consider a density operator $\rho\in \mathcal{B}(\mathcal{H}\otimes\mathcal{K})$, of the form

where $\mathcal{B}(\mathcal{H})_{+}$ is the cone of positive operators over $\mathcal{H}$.

For each $u\in V$, we set

Put

where $b^{(x)} = \alpha_x(b)$ for every $b\in \mathcal{B}(\mathcal{H}\otimes\mathcal{K})$ and $x\in V$.

Let

where ${\mathrm{Tr}}_{u]}$ is the partial trace defined by linear extension of

For $a = a_u\otimes a_{u, 1}\otimes \cdots \otimes a_{u, k}$ one shows that

where

Theorem 3.1. With the above notations, if $\omega_o\in \mathcal{A}_{o; +}$ is an initial state and $h\in \mathcal{A}_{o; +}$ is a boundary condition such that

Then the triplet $(\omega_o, (\mathcal{E}_{u})_{u\in V}, (h_u)_{u\in V})$ defines a quantum Markov chain $\varphi$ on the algebra $\mathcal{A}_V$. Moreover, for each $a = \bigotimes_{u\in \Lambda_n}a_u\in\mathcal{A}_{\Lambda_n}$ one has

where $\mathcal{E}_u$ is given by (3.5), the functional $\varphi_{jj}$ is given by (3.6), and

Proof. See ^[31]. □

The forward Markov operator associated with the TE (3.5) is defined from $\mathcal{A}_u$ into itself as follows

and for each $\ell\in \{1, 2, \cdots, k\}$, the $\ell^{th}$ backward Markov operator is defined on $\mathcal{A}_{x, \ell}$ into $\mathcal{A}_x$ by

In previous works ^[31,38], it was shown that the boundary condition $h = {{\bf 1}\!\!{{\rm{I}}}}$ corresponds to the QMC associated with the disordered phase of the system. One finds

and

4.   Main result

In this section, we restrict ourselves to the case $h = {{\bf 1}\!\!{{\rm{I}}}}$. Indeed, thanks to (3.1) the boundary condition $h = {{\bf 1}\!\!{{\rm{I}}}}$ is solution of (3.8). The corresponding QMC evaluated on localized elements $a = \bigotimes_{x\in\Lambda_m}a_x$ is given by

Definition 4.1. A state $\psi$ on $\mathcal{A}_V$ is said to be clustering (mixing) if

where $|u| = d(u, o)$.

Theorem 4.1. Let $\varphi \equiv (\phi_o, \mathcal{E}, h = {{\bf 1}\!\!{{\rm{I}}}})$ then

(i) Let $m\ge 0$ be an integer, for every $a, b\in\mathcal{A}_{\Lambda_m}$,

where

(ii) The QMC $\varphi$ given by (3.9) is clustering if and only if $|\Lambda| = 1$.

Proof. (i) Let $u = (\ell_1, \ell_2, \cdots, \ell_n)$. Let $a, b\in \mathcal{A}_{V; loc}$. Without lose of generality, we can assume that $a = \bigotimes_{x\in \Lambda_m}a_x, b = \bigotimes_{x\in \Lambda_m}b_x \in \mathcal{A}_{\Lambda_m}.$ For $F\subset \Lambda_m$, we denote $b_{F} = \bigotimes_{x\in F}b_x$, one can see that

We find

On the other hand, we have

Then

iterating the above procedure, we get

Denote $u_j = (\ell_1, \ell_2, \dots, \ell_j)$ for each $j\in\{1, 2, \cdots, n\}$. For $c_j\in \mathcal{A}_{u_j}$, we have

It follows that

where

For $c\in\mathcal{A}_{u_i}$, we have

This means that elements of the form $c' = \sum_{j}{{\bf 1}\!\!{{\rm{I}}}}_{\mathcal{H}}\otimes |j\rangle\langle j|\varphi_{jj}(c_i)$ are invariant for the all the backward Markov operators $P_{u_i; \ell; b}$. Then

Therefore, using (3.9) we find (4.3).

(ii) On the other hand, we have

Fix $j\in\Lambda$. For $a = ({{\bf 1}\!\!{{\rm{I}}}}_{\mathcal{H}}\otimes |j\rangle\langle j|)^{(1)}$, we get

Therefore, the QMC $\varphi$ satisfies (4.2) if and only if $\varphi_{jj} = \phi_o$, $\forall j\in \Lambda$. If $|\Lambda| > 1$, then for $j\ne j'$ we have $\varphi_{jj}({{\bf 1}\!\!{{\rm{I}}}}_{\mathcal{H}}\otimes |j\rangle\langle j|) = 1 \ne 0 = \varphi_{j'j'}({{\bf 1}\!\!{{\rm{I}}}}_{\mathcal{H}}\otimes |j\rangle\langle j|)$. If $\Lambda$ is reduced to a singleton $\{j_0\}$, the state $\varphi$ is a product state. It is enough to take $\phi_0 = \varphi_{j_0j_0}$ to get the clustering property. This finishes the proof. □

Remark 4.1. In (4.3), if $a = {{\bf 1}\!\!{{\rm{I}}}}$ we get

the limiting state $\varphi_{\infty}$ on $\mathcal{A}$ is equitably distributed between the state $\varphi_{jj}$ with respect to the initial state $\phi_o$.

From Theorem 4.1 the state $\varphi$ is clustering if and only the OQRW is trivial and the walker occupies a single site $\Lambda = \{i_0\}$. In this case the QMC $\varphi$ is a product state.

Example 4.1. Let $\mathcal{H} = \mathcal{K} = \mathbb{C}^2$ with canonical basis $(|1\rangle, |2\rangle)$ and $\Lambda = \{1, 2\}$. The algebra of observable is $\mathcal{A} = {\mathbb{M}}_2(\mathbb{C})\otimes \mathbb{M}_2(\mathbb{C})\equiv\mathbb{M}_4(\mathbb{C})$. The transitions of the OQRW are given by

where $\alpha, \beta, \gamma, \delta\in\mathbb{C}$ such that

Put

The initial state is the normalized trace given by $\phi_o = \frac{1}{4}{\mathrm{Tr}}$. One has $\varphi_{jj}(b) = {\mathrm{Tr}}\left(\rho_j\otimes|j\rangle\langle j|b\right)$ for each $j\in\Lambda$.

Let $a = b = \sigma\otimes|2\rangle\langle 2|$, from (3.5) we find

Therefore

Since $b\in \mathcal{A}_o$ then from (4.4) we have $\hat{b} = \mathcal{E}_o(b\otimes {{\bf 1}\!\!{{\rm{I}}}})$. It follows that

In addition

Then (4.3) implies that

Thus

Therefore, the state $\varphi$ does not satisfy the clustering property. Moreover, from (4.5) limiting state is given by

If in addition $|\beta|\ne |\gamma|$, then for $u\in V\setminus \Lambda_1$, we have

then the QMC $\varphi$ is not invariant under the translation $\tau_u$.

5.   Conclusions

In prior studies, significant characteristics of QMCs on trees, such as phase transition and recurrence, have been investigated. In the present paper, we examine the clustering property of a QMC approach on the Cayley tree associated OQRWs. This analysis reveals an additional ergodic property within the disordered phase of the quantum system under examination. Notably, our research shows promise in relation to the development of data clustering algorithms.

Use of AI tools declaration

The authors declare they have not used Artificial Intelligence (AI) tools in the creation of this article.

Acknowledgments

This research is funded by the "Researchers Supporting Project number (RSPD2023R683), King Saud University, Riyadh, Saudi Arabia".

Conflict of interest

The authors have no conflicts of interest to declare.