Quantum Pair State Transfer on Isomorphic Branches

The continuous-time quantum walk [24] on a quantum spin network, modeled by a graph $G$ with the Heisenberg $XY$ Hamiltonian as described in [3, 9, 20], is governed by the transition matrix $U_{G}(t)=\exp{\left(itA\right)},$ where $t\in{\mathbbm{R}}$ and $A$ is the adjacency matrix of $G.$ The Laplacian matrix $L$ can be used instead of the adjacency matrix when defining the transition matrix $U_{G}(t)$ whenever $XYZ$ interaction model [10] is adopted. However, for a regular graph, analyzing state transfer using either the adjacency or Laplacian model is equivalent, as both considerations yield the same information. The state associated with a vertex $a$ in $G$ is considered to be the characteristic vector ${\mathbf{e}}_{a}.$ Perfect state transfer (PST) [9, 20] occurs at time $\tau$ between two distinct vertices $a$ and $b$ in $G$ whenever the fidelity of transfer $\left|{\mathbf{e}}_{a}^{T}U_{G}(\tau){\mathbf{e}}_{b}\right|^{2}$ attains its maximum value $1.$ Since PST is a rare phenomenon [28], a relaxation known as pretty good state transfer (PGST) was introduced in [27, 45]. A graph $G$ is said to have PGST between the vertices $a$ and $b$ whenever the fidelity $\left|{\mathbf{e}}_{a}^{T}U_{G}(t){\mathbf{e}}_{b}\right|^{2}$ comes arbitrarily close to $1$ for appropriate choices of $t.$ The pair state associated with a pair of vertices $(a,b)$ is considered to be $\frac{1}{\sqrt{2}}\left({\mathbf{e}}_{a}-{\mathbf{e}}_{b}\right)$. In the case of perfect pair state transfer (PPST), the fidelity of transfer between two linearly independent pair states assumes the maximum value $1.$ As like PGST, one may consider pretty good pair state transfer (pair-PGST) where pair states are considered instead of the vertex states. In the past two decades, several network topologies having high fidelity vertex state transfer has been observed, such as the Cartesian powers of the path on two or three vertices [20], the path $P_{n}$ on $n$ vertices [20, 30, 27, 43], circulant graphs [2, 5, 41, 38, 39], cubelike graphs [7, 19], Cayley graphs [14, 16, 40, 42], distance regular graphs [22], Hadamard diagonalizable graphs [32], signed graphs [12], corona products [1], blow-up graphs [8], etc. We find that these graphs can be considered as isomorphic branches to a larger network to enable various properties associated to pair state transfer. Using the Laplacian model, pair state transfer was first introduced by Chen et al. [18], where it is shown that among paths and cycles, only the paths on three or four vertices and the cycle on four vertices admit Laplacian PPST, provided at least one of the pairs is an edge. Further investigation on pair state transfer can be found in cubelike graphs [13], Cayley graphs [15, 35], paths [46], vertex coronas [47]. Kim et al. [33] later generalized the notion of pair state transfer using $s$-pair states of the form ${\mathbf{e}}_{a}+s{\mathbf{e}}_{b},$ where $s$ is a non-zero complex number. They analyzed the existence of perfect state transfer between $s$-states in complete graphs, cycles, and antipodal distance regular graphs having perfect vertex state transfer.

In this article, we study continuous-time quantum walks on graphs relative to the adjacency matrix. The subsequent sections are organized as follows. In Section 2, we present several results on the existence of PPST and pair-PGST in graphs, and briefly introduce equitable partition for weighted graphs. A non-trivial relationship between the transfer of vertex states and pair states is established in Section 3, which provides a framework for constructing infinite families of graphs, such as trees, unicyclic graphs, and others, that exhibit PPST. Section 4 includes the characterization of pair state transfer on paths and cycles. Although not all paths or cycles admit PPST, we show that addition of a few edges to it enable PPST in the resulting graph. In Section 5, we introduce perfect $(m,L)$-state transfer in graphs, and uncover a few related observations.

Let $G$ be an undirected and weighted graph having a vertex set $V(G)$ and a weight function $w\mathrel{\mathop{\mathchar 58\relax}}V(G)\times V(G)\to\mathbb{R}$ which is symmetric. If $G$ is a simple graph then $w(a,b)=1,$ whenever $a$ and $b$ are adjacent in $G$, otherwise $w(a,b)=0.$ The adjacency matrix $A$ of a graph $G$ is a square matrix whose rows and columns are indexed by the vertices of $G$ and $A_{a,b}=w(a,b).$ A graph $G$ is said to have perfect pair state transfer (PPST) between two linearly independent pair states $\frac{1}{\sqrt{2}}\left({\mathbf{e}}_{a}-{\mathbf{e}}_{b}\right)$ and $\frac{1}{\sqrt{2}}\left({\mathbf{e}}_{c}-{\mathbf{e}}_{d}\right)$ associated to $(a,b)$ and $(c,d),$ respectively, if there exists $\tau\in\mathbb{R}$ such that

$$U_{G}(\tau)\left({\mathbf{e}}_{a}-{\mathbf{e}}_{b}\right)=\gamma\left({\mathbf{e}}_{c}-{\mathbf{e}}_{d}\right)\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ \text{for some}\leavevmode\nobreak\ \gamma\in\mathbb{C}.$$

(1)

In which case, we simply say that PPST occurs between pairs $(a,b)$ and $(c,d).$ If PPST occurs from $(a,b)$ to itself at time $\tau\leavevmode\nobreak\ (\neq 0),$ then $G$ is said to be periodic at $(a,b).$ The spectrum $\sigma(G)$ is the set of all eigenvalues of the adjacency matrix of $G.$ Suppose $E_{\lambda}$ is the orthogonal projection onto the eigenspace corresponding to eigenvalue $\lambda.$ If $\lambda_{1},\lambda_{2},\ldots,\lambda_{d}$ are the distinct eigenvalues of $A,$ then the spectral decomposition of $A$ is given by

$$A=\sum\limits_{j=1}^{d}\lambda_{j}E_{\lambda_{j}}.$$

The idempotents satisfy $E_{\lambda_{j}}E_{\lambda_{k}}=0,$ whenever $j\neq k,$ and $E_{\lambda_{1}}+E_{\lambda_{2}}+\cdots+E_{\lambda_{d}}=I,$ where $I$ is the identity matrix. The eigenvalue support of the pair state $\frac{1}{\sqrt{2}}\left({\mathbf{e}}_{a}-{\mathbf{e}}_{b}\right)$ associated to $(a,b)$ is defined by $\sigma_{ab}=\{\lambda\in\sigma(G)\mathrel{\mathop{\mathchar 58\relax}}E_{\lambda}({\mathbf{e}}_{a}-{\mathbf{e}}_{b})\neq 0\}.$ If PPST occurs between $(a,b)$ and $(c,d),$ then (1) implies that the support of $(a,b)$ and $(c,d)$ are identical. The states associated to $(a,b)$ and $(c,d)$ are called strongly cospectral if and only if

$$E_{\lambda}({\mathbf{e}}_{a}-{\mathbf{e}}_{b})=\pm E_{\lambda}({\mathbf{e}}_{c}-{\mathbf{e}}_{d})$$

holds for all $\lambda\in\sigma(G)$. It is well known that if PPST occurs between $(a,b)$ and $(c,d)$ in $G$ then the associated states are strongly cospectral [33, Theorem 2.3]. The strong cospectrality condition together with the spectral decomposition of $A$ yields

$\displaystyle\left({\mathbf{e}}_{a}-{\mathbf{e}}_{b}\right)^{T}A^{k}\left({\mathbf{e}}_{a}-{\mathbf{e}}_{b}\right)=\left({\mathbf{e}}_{c}-{\mathbf{e}}_{d}\right)^{T}A^{k}\left({\mathbf{e}}_{c}-{\mathbf{e}}_{d}\right),$

for all non-negative integers $k$. If $G$ is simple then $(a,b)$-th entry of $A^{k}$ represents the number of walks of length $k$ from $a$ to $b$. Let $N(a)$ denote the set of all neighbours of vertex $a.$ Considering $k=2,$ we arrive at the following conclusion.

It is worth mentioning that periodicity is necessary for a pair state to exhibit PPST [33, Theorem 2.5]. The following result provides necessary and sufficient conditions for a pair state to be periodic.

Since there are only a few paths and cycles exhibiting PPST (see Section 4), we consider a generalization to it as follows. A graph $G$ is said to exhibit pair-PGST between two linearly independent pair sates $\frac{1}{\sqrt{2}}\left({\mathbf{e}}_{a}-{\mathbf{e}}_{b}\right)$ and $\frac{1}{\sqrt{2}}\left({\mathbf{e}}_{c}-{\mathbf{e}}_{d}\right)$ associated to $(a,b)$ and $(c,d),$ respectively, if there exists a sequence $t_{k}\in{\mathbbm{R}}$ such that

$\displaystyle\lim_{k\to\infty}U_{G}\left(t_{k}\right)\left({\mathbf{e}}_{a}-{\mathbf{e}}_{b}\right)=\gamma\left({\mathbf{e}}_{c}-{\mathbf{e}}_{d}\right)\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ \text{for some}\leavevmode\nobreak\ \gamma\in\mathbb{C}.$

(2)

In [44, Lemma 3.3], van Bommel showed that if a graph has pretty good state transfer between a pair of arbitrary states, then they are strongly cospectral. In particular, if a graph $G$ has pretty good pair state transfer between $(a,b)$ and $(c,d)$, then the associated pair states are strongly cospectral.

In this section, we present a result that establishes a non-trivial relationship between vertex state and pair state transfer. Suppose a weighted graph $X_{1}$ is isomorphic to $X_{2}$ where $f\mathrel{\mathop{\mathchar 58\relax}}X_{1}\to X_{2}$ is an isomorphism satisfying $w(a,b)=w\left(f(a),f(b)\right),$ for all pair of vertices $a$ and $b$ in $X_{1}.$ Consider a connected graph $G$ where $X_{1}\cup X_{2},$ the disjoint union of $X_{1}$ and $X_{2},$ appears as an induced subgraph in such a way that $w(a,y)=w\left(f(a),y\right),$ for all $a\in V\left(X_{1}\right)$ and $y\in V(G)\setminus V\left(X_{1}\cup X_{2}\right).$ In which case, we say that $X_{1}$ and $X_{2}$ are isomorphic branches of the graph $G.$ The following result describes the evolution of certain pair states in a graph with isomorphic branches.

In Lemma 4, the orbits of $\hat{f}$ forms an equitable partition of $G,$ where $\left\{a,\hat{f}(a)\right\}$ forms a cell for every $a\in X_{1}$ and the remaining vertices are in singleton cells. Graphs with high fidelity pair sate transfer are obtained using the following result.

In Theorem 2, we observe that the evolution of certain pair states in a graph $G$ having isomorphic branches depends only on the local structure of $G.$ It is evident that all properties related to vertex state transfer in $X_{1}$ have natural consequences in terms of the pair states in $G.$ Consider the path $P_{5}$ as given in Figure 1, where $X_{1}$ and $X_{2}$ appear as isomorphic branches. It is well known that the path $X_{1}$ on two vertices admits PST at time $\frac{\pi}{2}$ between the end vertices $a$ and $b.$ Consequently, PPST occurs in $P_{5}$ between $(a,c)$ and $(b,d)$ at the same time. In fact, if the middle vertex of $P_{5}$ is identified with any vertex of a graph $H$ then PPST between $(a,c)$ and $(b,d)$ remains unaffected. In particular, considering $H$ a tree or an unicyclic graph, we have the following.

It is worth mentioning that among all trees only the path on two or three vertices exhibits PST [23]. In [21], the author finds that a graph with $m$ edges never have PST from vertex $a$ whenever the eccentricity $\epsilon_{a}$ of $a$ satisfies $(\epsilon_{a})^{3}\geq 54m.$ However, in the case of PPST, there is no such bound on eccentricity of the vertices or the graph diameter. One may wonder whether there is a simple graph $G$ exhibiting PST between a pair of vertices $a$ and $b,$ and PGST between another pair $c$ and $d$ where there is no PST. The answer is positive when considering pair states instead of the vertex states. Consider the graph $G$ given in Figure 2. One may apply Theorem 2 and observe that PPST occurs in $G$ between $(1,3)$ and $(5,6)$. Here $G$ exhibits pair-PGST between $(2,4)$ and $(9,12)$ as well. Since there is no PST in $P_{4},$ we have no PPST between $(2,4)$ and $(9,12).$

Suppose $K_{n}$ is a complete graph on $n$ vertices. All permutations of the $n$ vertices of $K_{n}$ forms an automorphism. One can deduce using Lemma 2 that there is no pair-PGST in $K_{n}.$ Let $a,$ $b,$ $c,$ $d$ be distinct vertices in $K_{n},$ where $n\geq 5,$ which form a cycle $C_{4}$ with $a$ and $c$ as antipodal vertices. Observe that the edges $(a,c)$ and $(b,d)$ are appearing as isomorphic branches of $K_{n}\backslash C_{4}.$ Theorem 2 applies here to find that PPST occurs between $(a,b)$ and $(c,d).$ In fact, we have the following conclusion.

It is well known that $C_{4},$ the cycle of length $4,$ admits PST at $\frac{\pi}{2}$ between antipodal vertices. We find a family of Cayley graphs exhibiting PPST, where multiple copies of $C_{4}$ appear as isomorphic branches. Let ${\mathbbm{Z}}_{m}$ denote the group of integers modulo $m.$ Consider $S=\left\{(0,\pm 1),(\pm 1,0),(\pm 1,2),(\pm m,0)\right\}\subset\mathbb{Z}_{4m}\times\mathbb{Z}_{4}$ with $m>1.$ The Cayley graph $\text{Cay}\left(\mathbb{Z}_{4m}\times\mathbb{Z}_{4},S\right)$ has the vertex set $\mathbb{Z}_{4m}\times\mathbb{Z}_{4},$ where two vertices $a$ and $b$ are adjacent whenever $a-b\in S.$ The edges of $\text{Cay}\left(\mathbb{Z}_{4m}\times\mathbb{Z}_{4},S\right)$ associated to $(\pm m,0)\in S$ forms $4m$ disjoint cycles of length $4,$ where the vertices $(j,k)$ and $(2m+j,k),$ for all $(j,k)\in\mathbb{Z}_{4m}\times\mathbb{Z}_{4},$ appear as antipodal vertices in each copy of $C_{4}.$ The vertices $(j,k)$ and $(j,k+2)$ are appearing in two distinct copies of $C_{4}$, say $X_{1}$ and $X_{2}.$ Both $(j,k)$ and $(j,k+2)$ are adjacent to $(j,k\pm 1),\leavevmode\nobreak\ (j\pm 1,k),\leavevmode\nobreak\ (j\pm 1,k+2)$ in $V(G)\setminus V\left(X_{1}\cup X_{2}\right).$ Now, Theorem 2 applies to find a family of Cayley graphs having PPST (or Laplacian PPST) from a pair of non-adjacent vertices.

A vertex $a$ in a graph $G$ is said to be $C$-sedentary if for some constant $0<C\leq 1,$

$$\inf_{t>0}\leavevmode\nobreak\ \left|{\mathbf{e}}_{a}^{T}U_{G}(t){\mathbf{e}}_{a}\right|\geq C.$$

The notion of sedentary family of graphs was first introduced by Godsil [29]. It is observed in [37, Proposition 2] that a $C$-sedentary vertex in a graph does not have PGST. Theorem 2 applies to identify graphs having $C$-sedentary pair states where there is no pair-PGST.

In a complete graph $K_{n}$ on $n$ vertices where $n\geq 3,$ one observes $\left|{\mathbf{e}}_{a}^{T}U_{K_{n}}(t){\mathbf{e}}_{a}\right|\geq 1-\frac{2}{n},$ for all vertices $a.$ Hence, each vertex in $K_{n}$ is $\left(1-\frac{2}{n}\right)$-sedentary. Now, consider the graph $G=K_{n}+K_{1}+K_{n},$ for $n\geq 3,$ where all vertices of two disjoint copies of $K_{n}$ are joined with an isolated vertex by edges. Since the pair state associated to $(a,b)$ becomes an eigenvector of $G$ whenever $a$ and $b$ lies in the same copy of $K_{n},$ there is no PPST from $(a,b)$ (see [33]). In the remaining cases, where both $a$ and $b$ have degree $n,$ Corollary 4 applies to conclude that $G$ does not exhibit PPST. Finally, if the vertex $x$ of degree $2n$ is paired with another vertex $b$ in $G,$ then the eigenvalue support of $(x,b)$ contains the eigenvalues $n-1$ and $\frac{(n-1)\pm\sqrt{(n+1)^{2}+4n}}{2}.$ Since periodicity is necessary for the existence of PPST, we find using Theorem 1 that there is no PPST in $G.$

A graph $G$ is said to have fractional revival from a vertex $a$ whenever the transition matrix of $G$ maps the state associated with $a$ to a linear combination of the states of a collection of vertices containing the initial one [6, 17, 26, 36]. One may consider fractional revival on $G$ from a pair state as well. A graph $G$ admits fractional revival at time $\tau$ between pair states $\frac{1}{\sqrt{2}}\left({\mathbf{e}}_{a}-{\mathbf{e}}_{b}\right)$ and $\frac{1}{\sqrt{2}}\left({\mathbf{e}}_{c}-{\mathbf{e}}_{d}\right)$ associated to $(a,b)$ and $(c,d),$ respectively, if for some $\alpha,\beta\in\mathbb{C}$ with $\beta\neq 0$, we have

$$U_{G}(\tau)\left({\mathbf{e}}_{a}-{\mathbf{e}}_{b}\right)=\alpha\left({\mathbf{e}}_{a}-{\mathbf{e}}_{b}\right)+\beta\left({\mathbf{e}}_{c}-{\mathbf{e}}_{d}\right).$$

It is well known that $P_{4}$ exhibits $\left(-\cos{\frac{\pi}{\sqrt{5}}},-i\sin{\frac{\pi}{\sqrt{5}}}\right)$-revival at $\frac{2\pi}{\sqrt{5}}$ between the end vertices. Then Theorem 2 applies to conclude that $P_{9}$ exhibits fractional revival between $(1,9)$ and $(4,6)$ at the same time. Using Theorem 2, one may construct families of graphs having fractional revival from a pair state to another as below.

The results uncovered in Section 3 play a significant role in characterizing pair state transfer on special classes of graphs, including paths, cycles, and others. First we present a complete characterization of PPST in paths. Then, we unfold a sufficient condition for pair-PGST in paths, which leads to a complete characterization of pair-PGST in cycles. These insights guide us to discover new families of graphs exhibiting pair state transfer.