\documentclass[12pt]{article}
\usepackage{e-jc}
\usepackage{amsmath, amsthm, amssymb, amsfonts, mathrsfs}
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}
\usepackage[dvips]{graphicx}
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{cor}[theorem]{Corollary}
\newtheorem{lem}[theorem]{Lemma}
\newtheorem{prop}[theorem]{Proposition}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\def \Fl {{\mathbb F}}
\def \Zl {{\mathbb Z}}
\def \Nl {{\mathbb N}}
\def \Rl {{\mathbb R}}
\def \Ql {{\mathbb Q}}
\def \Cl {{\mathbb C}}
\def \r {{\mathbf r}}
\def \ul {{\mathbf u}}
\def \vl {{\mathbf v}}
\def \x {{\mathbf x}}
\def \y {{\mathbf y}}
\def \sig {{\mathbf \sigma}}
\def \z {{\mathbf z}}
\def \o {{\mathbf 0}}
\def \s {{\sf s}}
\def \m {{\mathbf m}}
\def \n {{\mathbf n}}
\def \D {{\mathbf D}}
\def \C {{\mathbf C}}
\def \d {{\mathbf d}}
\newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}}
\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}
\title{\bf Pretty Good State Transfer on Circulant Graphs}
\author{ Hiranmoy Pal \qquad Bikash Bhattacharjya\\
\small Department of Mathematics\\[-0.8ex]
\small Indian Institute of Technology Guwahati\\[-0.8ex]
\small Guwahati, India - 781039\\
\small\tt $\{$hiranmoy, b.bikash$\}$@iitg.ernet.in
}
\date{\dateline{Aug 18, 2016}{ XX }\\
\small Mathematics Subject Classifications: 05C12, 05C50}
\begin{document}
\maketitle
\begin{abstract}
Let $G$ be a graph with adjacency matrix $A$. The transition matrix of $G$ relative to $A$ is defined by $H(t):=\exp{\left(-itA\right)}$, where $t\in {\mathbb R}$. The graph $G$ is said to admit pretty good state transfer between a pair of vertices $u$ and $v$ if there exists a sequence of real numbers $\{t_k\}$ and a complex number $\gamma$ of unit modulus such that $\lim\limits_{k\rightarrow\infty} H(t_k) e_u=\gamma e_v.$ We find that the cycle $C_n$ as well as its complement $\overline{C}_n$ admit pretty good state transfer if and only if $n$ is a power of two, and it occurs between every pair of antipodal vertices. In addition, we look for pretty good state transfer in more general circulant graphs. We prove that union (edge disjoint) of an integral circulant graph with a cycle, each on $2^k$ $(k\geq 3)$ vertices, admits pretty good state transfer. The complement of such union also admits pretty good state transfer. Using Cartesian products, we find some non-circulant graphs admitting pretty good state transfer.
\bigskip\noindent \textbf{Keywords:} circulant graph, pretty good state transfer, Kronecker approximation theorem
\end{abstract}
\section{Introduction}
Perfect state transfer (PST) has great significance due to its applications in quantum information processing and cryptography (see \cite{ben,cha,ek}). The phenomenon of PST in quantum communication networks was originally introduced by Bose in \cite{bose}. In mathematical terms, PST is defined as follows. The transition matrix of a graph $G$ with adjacency matrix $A$ is defined by
\[H(t):=\exp{\left(-itA\right)},\;t\in\Rl.\]
The transition matrix $H(t)$ is a unitary matrix and it is also a polynomial in $A$. The graph $G$ is said to exhibit PST from a vertex $u$ to another vertex $v$ if there exists a real number $\tau$ and a complex number $\gamma$ with $|\gamma|=1$ such that $H(\tau)e_u=\gamma e_v.$ In the case where $H(\tau)e_u=\gamma e_u$, $\tau\neq 0$, we say that $G$ is periodic at the vertex $u$. Moreover, $G$ is said to be periodic if there is $\tau\in\Rl$ such that $H(\tau)$ is a scalar multiple of the identity matrix, in which case the graph is periodic at all vertices. Finding whether a given graph has PST is quite difficult especially when the graph is large. Remarkably, in \cite{cou1}, Coutinho \emph{et al.} showed that one can decide whether a graph admits PST in polynomial time with respect to the size of the graph on a classical computer.\par
In initial papers (see \cite{chr2,chr1}), we find that PST occurs on Cartesian powers of a path on two vertices and a path on three vertices. Further the results have been generalized to NEPS of the respective graphs (see\cite{ber,chi,pal}). A graph is called integral if all its eigenvalues are integers. In \cite{god1}, Godsil established the fact that if a vertex transitive graph exhibits PST between two vertices at time $\tau$ then the corresponding transition matrix $H(t)$ evaluated at $\tau$ is a scalar multiple of a permutation matrix of order two. In that case, using $H\left(2\tau\right)=\left(H\left(\tau\right)\right)^2$, one can conclude that the graph is periodic at $2\tau$. A Cayley graph is well known to be vertex-transitive and hence it is also a regular graph. In \cite{god1}, we also find that a regular graph is periodic if and only if the graph is integral. As a result, if PST occurs on a Cayley graph then it must be integral. A characterization of PST in integral circulant graphs appears in \cite{mil4}. Some results on PST in gcd-graph, which is a special class of integral Cayley graph, can be found in \cite{pal2,pal1}. In \cite{god2}, we see that there are only finitely many connected graphs with maximum valency at most $k$ where PST occurs. Since there are few graphs having PST, we consider a relaxation to PST called pretty good state transfer (PGST).\par
The notion of PGST was first introduced by Godsil in \cite{god1}. A graph $G$ with transition matrix $H(t)$ has PGST between a pair of vertices $u$ and $v$ if there is a sequence of real numbers $\{t_k\}$ and a complex number of unit modulus $\gamma$ such that \[\lim_{k\rightarrow\infty} H(t_k) e_u=\gamma e_v.\]
In such a case, we also say that $G$ exhibits PGST from $u$ to $v$ with respect to the sequence $\{t_k\}$. This is equivalent to say that for $\epsilon>0$, there exists $t\in \Rl$ and $\gamma\in\Cl$ with $|\gamma|=1$ such that
\[\left| e_u^T H(t) e_v -\gamma\right|<\epsilon.\]
There are a few published papers which discuss PGST. Godsil \emph{et al.} \cite{god4} showed that the path $P_n$ exhibits PGST if and only if $n+1$ equals to either $2^m$ or $p$ or $2p$, where $p$ is an odd prime. We also see in \cite{fan} that a double star $S_{k,k}$ admits PGST if and only if $4k+1$ is not a perfect square. The double star can be realized as a corona product of the complete graph $K_2$ and an empty graph. PGST in more general corona products has been studied in \cite{ack,ack1}. Moreover, in \cite{pal3}, we find some NEPS of the path on three vertices having PGST. Some other relevant results regarding PST and PGST can be found in \cite{cou,cou2,god3,kirk}.\par
Circulant graphs arises frequently in communication networks. Among the circulant graphs only integral circulant graphs are periodic (see \cite{god1}). It can be proved that if a graph is periodic then the graph has PGST if and only if it has PST. Since a complete characterization of PST in integral circulant graph is known, we consider PGST in circulant graphs which are not integral. In the present article, we completely classify which cycles exhibit PGST. Beside cycles, we also find two classes of non-integral circulant graphs one of which exhibits PGST and the other does not. Apart from circulant graphs, we use Cartesian product to find some non-circulant graphs having PGST.\par
Let $\left(\Gamma,+\right)$ be a finite abelian group and consider $S\subseteq\Gamma\setminus\{0\}$ with $\left\lbrace -s:s\in S\right\rbrace=S$. Such a set $S$ is called a symmetric subset of $\Gamma$. A Cayley graph over $\Gamma$ with a symmetric set $S$ is denoted by $Cay\left(\Gamma,S\right)$. The graph has the vertex set $\Gamma$ where two vertices $a,b\in\Gamma$ are adjacent if and only if $a-b\in S$. The set $S$ is called the connection set of $Cay\left(\Gamma,S\right)$. Let $\Zl_n$ be the cyclic group of order $n$. A circulant graph is a Cayley graph over $\Zl_n$. A cycle $C_n$, in particular, is a circulant graph over $\Zl_n$ with the connection set $\{1,n-1\}$. Eigenvalues and eigenvectors of a cycle are very well known. Suppose $\omega_n=\exp{\left(\frac{2\pi i}{n}\right)}$ is the primitive $n$-th root of unity. Then the eigenvalues of $C_n$ are
\begin{eqnarray}\label{e}
\lambda_l=2\cos{\left(\frac{2l\pi}{n}\right)},\;0\leq l\leq n-1,
\end{eqnarray}
and the corresponding eigenvectors are $\vl_l=\left[1,\omega_n^l,\ldots,\omega_n^{l(n-1)}\right]^T$.\par
The eigenvalues and eigenvectors of a Cayley graph over an abelian group are also known in terms of characters of the abelian group. In \cite{wal1}, it appears that the eigenvectors of a Cayley graph over an abelian group are independent of the connection set. Consider two symmetric subsets $S_1,S_2$ of $\Gamma$. So the set of eigenvectors of both $Cay(\Gamma, S_1 )$ and $Cay(\Gamma, S_2 )$ can be chosen to be equal. Hence we have the following result.
\begin{prop}\label{3ab}
If $S_1$ and $S_2$ are symmetric subsets of an abelian group $\Gamma$ then adjacency matrices of the Cayley graphs $Cay(\Gamma, S_1 )$ and $Cay(\Gamma, S_2 )$ commute.
\end{prop}
If $d$ is a proper divisor of $n$ then we define
\[S_n(d)=\{x\in\Zl_n: gcd(x,n)=d\},\]
and for any set $D$ containing proper divisors of $n$, we define
\[S_n(D)=\bigcup\limits_{d\in D} S_n(d).\]
The set $S_n(D)$ is called a gcd-set of $\Zl_n$. A gcd graph over $\Zl_n$ is a circulant graph whose connection set is a gcd-set. We denote a gcd graph over $\Zl_n$ with the connection set $S_n(D)$ by $G(n,D)$.\par
The following theorem determines circulant graphs which are integral.
\begin{theorem}\cite{so}
A circulant graph is integral if and only if the connection set is a gcd-set.
\end{theorem}
The Cartesian product of two graphs $G_{1}$ and $G_{2}$ with vertex sets $V_{1}$ and $V_{2}$ is the graph $G_{1}\square G_{2}$, with vertex set $V_{1}\times V_{2}$. Two vertices $(u_{1},u_{2})$ and $(v_{1},v_{2})$ are adjacent in $G_{1}\square G_{2}$ if and only if either $u_{1}$ is adjacent to $v_{1}$ in $G_{1}$ and $u_{2}=v_{2}$, or $u_{1}=v_{1}$ and $u_{2}$ is adjacent to $v_{2}$ in $G_{2}$. The transition matrix of a Cartesian product of two graphs is given by the following result.
\begin{lem}\cite{chr2}
Let $G_1$ and $G_2$ be two graphs having transition matrices $H_{G_1}(t)$ and $H_{G_2}(t)$, respectively. Then the transition matrix of the Cartesian product $G_1\square G_2$ is $H_{G_1\square G_2}(t)=H_{G_1}(t)\otimes H_{G_2}(t)$.
\end{lem}
Now we introduce Kronecker approximation theorem on simultaneous approximation of numbers. This will be used later to find graphs allowing PGST.
\begin{theorem}[Kronecker approximation theorem]\cite{apo}
If $\alpha_1,\ldots,\alpha_l$ are arbitrary real numbers and if $1,\theta_1,\ldots, \theta_l$ are real, algebraic numbers linearly independent over $\Ql$ then for $\epsilon>0$ there exist $q\in\Zl$ and $p_1,\ldots,p_l\in\Zl$ such that
\[\left|q\theta_j-p_j-\alpha_j\right|<\epsilon.\]
\end{theorem}
A bound on the integer $q$ relative to the precision $\epsilon$ and some other given constraints is given in \cite{mala}.
\section{Pretty Good State Transfer on Circulant Graphs}
We begin with the discussion that the odd cycles never exhibit PGST. Moreover, if an even cycle admits PGST then it must occur only between the antipodal vertices. Suppose $G$ is a graph with adjacency matrix $A$. If $P$ is the matrix of an automorphism of $G$ then $P$ must commute with $A$ and consequently $P$ commutes with the transition matrix $H(t)$. Suppose $G$ allows PGST between two vertices $u$ and $v$. Then there exists a sequence of real numbers $\{t_k\}$ and a complex number $\gamma$ of unit modulus such that
\[\lim_{k\rightarrow\infty} H(t_k) e_u=\gamma e_v.\]
Further this implies that
\[\lim_{k\rightarrow\infty} H(t_k) \left(Pe_u\right)=\gamma \left(Pe_v\right).\]
Since the sequence $\{H(t_k)e_u\}$ cannot have two different limits, we conclude that if $P$ fixes $e_u$ then $P$ must fix $e_v$ as well. Note that the map that sends $j$ to $-j$ is an automorphism of the circulant graph $Cay\left(\Zl_n,S\right)$. As a consequence, we have the following result.
\begin{lem}\label{l0}
If pretty good state transfer occurs in a circulant graph $Cay\left(\Zl_n,S\right)$ then $n$ is even and it occurs only between the pair of vertices $u$ and $u+\frac{n}{2}$, where $u,u+\frac{n}{2}\in\Zl_n$.
\end{lem}
From now onwards we only consider the even cycles. Notice that it is enough to find PGST in $C_{n}$ between the pair of vertices $0$ and $\frac{n}{2}$. We thus calculate the $(0,\frac{n}{2})$-th entry of the transition matrix of $C_n$. If $\sum\limits_{l=0}^{n-1}\lambda_lE_l$ is the spectral decomposition of the adjacency matrix $A$ of $C_n$ then the transition matrix can be calculated as
\[H(t)=\exp{\left(-itA\right)}=\sum\limits_{l=0}^{n-1}\exp{\left(-i\lambda_l t\right)E_l}.\]
Note that $E_l=\frac{1}{n}\vl_l\vl_l^*$, where $\vl_l=\left[1,\omega_n^l,\ldots,\omega_n^{l(n-1)}\right]^T$ as given in $\left(\ref{e}\right)$. Therefore the $(0,\frac{n}{2})$-th entry of $E_l$ is $\frac{1}{n}\omega_{n}^{-\frac{nl}{2}}$. Hence, we evaluate the $(0,\frac{n}{2})$-th entry of $H(t)$ as
\begin{eqnarray}\label{e0}
H(t)_{0,\frac{n}{2}}=\frac{1}{n}\sum\limits_{l=0}^{n-1}\exp{\left(-i\lambda_l t\right)}\cdot\omega_{n}^{-\frac{nl}{2}}=\frac{1}{n}\sum\limits_{l=0}^{n-1}\exp{\left[-i\left(\lambda_l t+l\pi\right)\right]}.
\end{eqnarray}
It is well known that a cycle on four vertices admits PST at $\frac{\pi}{2}$ between any pair of antipodal vertices. Since PGST is a generalization of PST, the cycle on four vertices also exhibits PGST. In the following result, we distinguish a class of cycles admitting PGST. Later, we will show that these are the only cycles with PGST.
\begin{lem}\label{l1}
If $n=2^k,\;k\geq 3$, then the cycle $C_{n}$ exhibits pretty good state transfer with respect to a sequence in $2\pi\Zl.$
\end{lem}
\begin{proof}
The eigenvalues of $C_n$ can be realized as
\[\lambda_l=2\cos{\left(\frac{2l\pi}{n}\right)}=\omega_n^l+\omega_n^{-l},\;\text{where }l=0,1,\ldots,n-1.\]
The graph $C_{2^k}$ is bipartite and each of its eigenvalue is repeated twice except the eigenvalues $2$ and $-2$. For $ 1\leq l\leq 2^{k-2}-1,$ we see that
\[\lambda_l=2\cos{\left(\frac{2l\pi}{n}\right)}=2\cos{\left(2\pi-\frac{2l\pi}{n}\right)}=\lambda_{n-l}.\] Similarly, for $ 1\leq l\leq 2^{k-2}-1$ we have
\[\lambda_l=-\lambda_{\frac{n}{2}-l}=-\lambda_{\frac{n}{2}+l}.\]
Now we show that the distinct positive eigenvalues of $C_n$ are linearly independent over $\Ql$. It is well known that the minimal polynomial of $\omega_n$ over $\Ql$ has degree $\phi(n)$, where $\phi$ is Euler's phi-function (see \cite{esc}). It is evident that $\cos{\left(\frac{2l\pi}{n}\right)}$ is positive only when $0\leq\frac{2l\pi}{n}<\frac{\pi}{2}$ or $\frac{3\pi}{2}<\frac{2l\pi}{n}<2\pi$. Consequently, the distinct positive eigenvalues are $\lambda_l$ where $0\leq l<\frac{n}{4}.$ If the distinct positive eigenvalues are linearly dependent over $\Ql$ then $\omega_n$ will be a root of a polynomial of degree at most $m=2^{k-1}-1$ as $\omega_n^{-1}=-\omega_n^{m}$. But since $2^{k-1}-1<2^{k-1}= \phi(2^k),$ we conclude that the distinct positive eigenvalues $\lambda_0,\lambda_1,\ldots,\lambda_{2^{k-2}-1}$ are linearly independent over $\Ql$.\par
For $ 1\leq l\leq 2^{k-2}-1$, consider the following real numbers
\begin{eqnarray*}
\alpha_l=\begin{cases} 0, & \text{ if $l$ is even}\\
\frac{1}{2}, & \text{ if $l$ is odd.}
\end{cases}
\end{eqnarray*}
By Kronecker approximation theorem, for $\delta>0$ there exist $q,m_1,\ldots,m_{2^{k-2}-1}\in\Zl$ such that for $l=1,\ldots, 2^{k-2}-1$
\begin{eqnarray}\label{e1}
\left|q\lambda_l-m_l-\alpha_l\right|<\frac{\delta}{2\pi},\; \emph{i.e,}\;\left|2q\pi\lambda_l-2m_l\pi-2\alpha_l\pi\right|<\delta.
\end{eqnarray}
Since $\lambda_0,\lambda_{2^{k-2}},\lambda_{2^{k-1}}$ and $\lambda_{3\cdot2^{k-2}}$ are integers, considering $t=2q\pi$, we observe that for each $l=0,\;2^{k-2},\;2^{k-1},\;3\cdot2^{k-2}$ there exists an integer $l'$ satisfying
\[\left|\left(\lambda_l t+l\pi\right)- 2l'\pi\right|<\delta.\]
Also for each $l=1,\ldots, 2^{k-2}-1$, considering $t=2q\pi$ and using $\left(\ref{e1}\right)$, we find
\begin{eqnarray*}
l'=\begin{cases} \frac{2m_l+l+1}{2}, & \text{ if $l$ is odd}\\
\frac{2m_l+l}{2}, & \text{ if $l$ is even.}
\end{cases}
\end{eqnarray*}
such that
\[\left|\left(\lambda_l t+l\pi\right)- 2l'\pi\right|<\delta.\]
Since the relation $\lambda_l=-\lambda_{\frac{n}{2}-l}=-\lambda_{\frac{n}{2}+l}=\lambda_{n-l}$ on eigenvalues of the cycle $C_{2^k}$ holds for $ 1\leq l\leq 2^{k-2}-1$, considering $t=2q\pi$, we conclude that for each $l=0,\ldots, n-1,$ there is an integer $l'$ such that
\[\left|\left(\lambda_l t+l\pi\right)- 2l'\pi\right|<\delta.\]
Therefore by uniform continuity of the exponential function $\exp{\left(-ix\right)}$, it follows that for $\epsilon>0$ there exists $q\in\Zl$ so that $t=2q\pi$ and $\left|\exp{\left[-i\left(\lambda_l t+l\pi\right)\right]}- 1\right|<\epsilon.$ Finally, from Equation (\ref{e0}), we observe that
\[\left|H(t)_{0,\frac{n}{2}}-1\right|=\frac{1}{n}\left|\sum\limits_{l=0}^{n-1}\left(\exp{\left[-i\left(\lambda_l t+l\pi\right)\right]}-1\right)\right|<\epsilon.\]
This leads to the conclusion that $C_n$ admits PGST whenever $n=2^k,\;k\geq 3$, with respect to a sequence in $2\pi\Zl$.
\end{proof}
Let $G$ and $H$ be two simple graphs on the same vertex set $V$, and respective edge sets $E(G)$ and $E(H)$. The \emph{edge union} of $G$ and $H$, denoted $G\cup H$, is defined on the vertex set $V$ whose edge set is $E(G)\cup E(H)$. Using Lemma \ref{l1}, we find more general circulant graphs allowing PGST. We present this as a theorem.
\begin{theorem}\label{t1}
Let $n=2^k$ with $k\geq 3$. If $D$ is a set of proper divisors of $n$ not containing $1$ then the circulant graph $C_n\cup G(n,D)$ as well as its complement admit pretty good state transfer with respect to the same sequence in $2\pi\Zl$.
\end{theorem}
\begin{proof}
Notice that both graphs $C_n$ and $G(n,D)$ have the same vertex set $\Zl_n$ but the edge sets are disjoint as $1\not\in D$. Suppose $A$ and $B$ are the adjacency matrices of $C_n$ and $G(n,D)$, respectively. The adjacency matrix of $C_n\cup G(n,D)$ is therefore $A+B$. Since the matrices $A$ and $B$ commute, the transition matrix of $C_n\cup G(n,D)$ is
\[H(t)=H_A(t) H_B(t),\]
where $H_A(t)$ and $H_B(t)$ are transition matrices of $C_n$ and $G(n,D)$, respectively. Suppose $B$ has the spectral decomposition $\sum\limits_{j=1}^r \theta_j E_j$. Since the graph $G(n,D)$ is integral, the values $\theta_j$'s are integers. This in turn implies that if $t\in 2\pi\Zl$ then
\[H_B(t)=\exp{\left(-itB\right)}=\sum\limits_{j=1}^r \exp{(-it\theta_j)}E_j=I.\]
Hence $H(t)=H_A(t)$ whenever $t\in 2\pi\Zl$. Finally, by Lemma \ref{l1}, we see that $C_n\cup G(n,D)$ exhibits PGST.\par
It remains to show that complement of $C_n\cup G(n,D)$ also admits PGST. The adjacency matrix of the complement is $J-I-(A+B).$ Since all circulant graphs are regular, the matrix $A+B$ commutes with $J-I$. If $H'(t)$ is the transition matrix of the complement of $C_n\cup G(n,D)$ then
\[H'(t)=\exp{\left(-it\left(J-I\right)\right)}H(-t).\]
Clearly the eigenvalues of $J-I$ are integers. Hence following the same argument as given in the previous part, we have the desired result.
\end{proof}
In Theorem \ref{t1}, the graph $C_n\cup G(n,D)$ can never be a gcd graph and so it cannot be integral. The reason is that if $C_n\cup G(n,D)=G(n,D')$ for some divisor set $D'$ then $1\in D'$. Therefore $\{1,n-1\}\cup S_n(D)$ contains all odd numbers in $\Zl_n$ as $\{1,n-1\}\cup S_n\left(D\right)=S_n\left(D'\right).$ As $n=2^k\;(k\geq 3)$, we see, for example, that $\{1,n-1\}\cup S_n(D)$ can never contain $3$.\par
Notice that if $D$ is an empty set then Theorem \ref{t1} implies that complement of a cycle $C_{2^k},~(k\geq 3)$ also allows PGST. Observe that the complement of $C_4$ is the disjoint union of two paths of length two. Since a path of length two admits PST and PGST is a generalization of PST, we conclude that the complement of $C_4$ also admits PGST. Another point to observe in the proof of Theorem \ref{t1} is that for a fixed $n$, there exists a fixed sequence with respect to which all graphs of the form $C_n\cup G(n,D)$ as well as their complement exhibit PGST. \par
It turns out that there are some more graphs allowing PGST apart from the circulant graphs we already mentioned. Before finding those graphs we introduce the following notations. For $k\geq 3$, we denote
\[\mathcal{G}_k = \left\lbrace C_{2^k}\cup G\left(2^k,D\right)\;:\; D \text{ is a set of proper divisors of } 2^k \text{ and } 1\not\in D \right\rbrace.\]
Also the set of the complements of graphs in $\mathcal{G}_k$ is denoted by $\bar{\mathcal{G}_k}$. Further we set
\[\mathcal{G}=\bigcup\limits_{k\geq 3}\left(\mathcal{G}_k\cup\bar{\mathcal{G}_k}\right).\]
Now we find the following corollaries regarding PGST in Cartesian products.
\begin{cor}\label{c0}
Let $G_1, G_2\in\mathcal{G}_k\cup\bar{\mathcal{G}_k}$. Then the Cartesian product $G_1\square G_2$ as well as its complement admit pretty good state transfer.
\end{cor}
\begin{proof}
In the proof of Theorem \ref{t1} we see that if $G_1, G_2\in\mathcal{G}_k\cup\bar{\mathcal{G}_k}$ then both $G_1$ and $G_2$ have PGST with respect to the same sequence $\{t_m\}$ in $2\pi\Zl$. Suppose $G_1$ admits PGST between the vertices $u_1$ and $v_1$ and $G_2$ admits PGST between the vertices $u_2$ and $v_2$. Also assume that $H_{G_1}(t)$ and $H_{G_2}(t)$ are the transition matrices of $G_1$ and $G_2$, respectively. Therefore there exist $\gamma_1,\gamma_2\in\Cl$ with $|\gamma_1|=|\gamma_2|=1$ such that
\[\lim_{m\rightarrow\infty} e_{u_1}^T H_{G_1}(t_m) e_{v_1}=\gamma_1 \text{ and } \lim_{m\rightarrow\infty} e_{u_2}^T H_{G_2}(t_m) e_{v_2}=\gamma_2.\]
Using the property of transition matrix of a Cartesian product, we have
\begin{eqnarray*}
\left(e_{u_1}\otimes e_{u_2}\right)^T\left(H_{G_1\square G_2}\left(t_m\right)\right)\left(e_{v_1}\otimes e_{v_2}\right)
& = & \left(e_{u_1}\otimes e_{u_2}\right)^T\left(H_{G_1}\left(t_m\right)\otimes H_{G_2}\left(t_m\right)\right)\left(e_{v_1}\otimes e_{v_2}\right)\\
& = & \left(e_{u_1}^T H_{G_1}\left(t_m\right)e_{v_1}\right)\cdot\left(e_{u_2}^T H_{G_2}\left(t_m\right)e_{v_2}\right).
\end{eqnarray*}
Now taking limits on both sides we find that $G_1\square G_2$ admits PGST.\par
It remains to show that the complement of $G_1\square G_2$ exhibits PGST. Notice that both $G_1$ and $G_2$ are regular graphs and therefore $G_1\square G_2$ is also a regular graph. Now as in the proof of second part of Theorem \ref{t1}, we have the desired conclusion.
\end{proof}
More generally, following the proof of Corollary \ref{c0}, we can deduce that if two graphs have PGST with respect to the same sequence then their Cartesian product also admits PGST with respect to that sequence. In the next result, we find another class of graphs exhibiting PGST.
\begin{cor}
Let a graph $G_1$ be periodic at a vertex at time $2\pi$. If $G_2\in\mathcal{G}$ then the Cartesian product $G_1\square G_2$ admits pretty good state transfer. If $G_1$ is regular then the complement of $G_1\square G_2$ also exhibits pretty good state transfer.
\end{cor}
\begin{proof}
Suppose $G_1$ is periodic at a vertex $u$ at time $2\pi$. If $H_{G_1}(t)$ is the transition matrix of $G_1$ then there exists $\gamma_1\in\Cl$ with $|\gamma|=1$ such that $e_u^T H_{G_1}(2\pi)e_u=\gamma_1$. Hence for $q\in\Zl$, we have $e_u^T H_{G_1}(2q\pi)e_u=\gamma_1^q$. Since $G_2\in\mathcal{G}$ there is a sequence $\{t_m\}$ in $2\pi\Zl$ with respect to which $G_2$ exhibits PGST between two vertices $v$ and $w$, say. Since the unit circle is compact there is a subsequence $\{t'_m\}$ of $\{t_m\}$ such that $\left\lbrace e_u^T H_{G_1}(t'_m)e_u\right\rbrace$ is convergent. If $H_{G_2}(t)$ is the transition matrix of $G_2$ then
\begin{eqnarray*}
\left(e_{u}\otimes e_{v}\right)^T\left(H_{G_1\square G_2}\left(t'_m\right)\right)\left(e_{u}\otimes e_{w}\right)
= \left(e_{u}^T H_{G_1}\left(t'_m\right)e_{u}\right)\cdot\left(e_{v}^T H_{G_2}\left(t'_m\right)e_{w}\right).
\end{eqnarray*}
Now taking limits on both sides, we find that $G_1\square G_2$ admits PGST.\par
In case $G_1$ is regular then $G_1\square G_2$ is also regular. Therefore the complement of $G_1\square G_2$ also exhibits PGST.
\end{proof}
\begin{remark} If a graph is integral then it is periodic at $2\pi$. So Cartesian product of an integral graph and a graph in $\mathcal{G}$ allows PGST. This gives a large number of graphs having PGST.
\end{remark}
In Lemma \ref{l1}, we found a class of cycles with PGST. Next we investigate PGST in the remaining class of cycles. The only possibility we need to consider is the case when $n$ has an odd prime factor. We have used some of the techniques from \cite{god4} to prove the following result.
\begin{lem}\label{l2}
Let $m\in\Nl$ and $p$ be an odd prime such that $n=mp$. Then the cycle $C_{n}$ does not exhibit pretty good state transfer.
\end{lem}
\begin{proof}
Notice that if $m$ is an odd number then, by Lemma \ref{l0}, we have the desired result. Hereafter we assume that $m$ is even. For an odd prime $p$ we have the following identity involving the primitive $p$-th root $\omega_p$ of unity:
\[1+\omega_p+\omega_p^2+\ldots+\omega_p^{p-1}=0.\]
This further yields
\begin{eqnarray}\label{e2}
1+2\sum\limits_{r=1}^{\frac{p-1}{2}}\cos{\left(\frac{2r\pi}{p}\right)}=0.
\end{eqnarray}
Multiplying both sides of $\left(\ref{e2}\right)$ by $2\cos{\left(\frac{2\pi}{n}\right)}$ we obtain the following relation of eigenvalues of $C_n$ (as given in $\left(\ref{e}\right)$).
\begin{eqnarray}\label{e3}
\lambda_1 + \sum\limits_{r=1}^{\frac{p-1}{2}}\lambda_{mr+1} + \sum\limits_{r=1}^{\frac{p-1}{2}} \lambda_{mr-1}=0.
\end{eqnarray}
Similarly multiplying $\left(\ref{e2}\right)$ by $2\cos{\left(\frac{4\pi}{n}\right)}$ gives
\begin{eqnarray}\label{e4}
\lambda_2 + \sum\limits_{r=1}^{\frac{p-1}{2}}\lambda_{mr+2} + \sum\limits_{r=1}^{\frac{p-1}{2}} \lambda_{mr-2}=0.
\end{eqnarray}
Now from Equation $\left(\ref{e3}\right)$ and $\left(\ref{e4}\right)$ we get
\begin{eqnarray}\label{e5}
\left(\lambda_2 - \lambda_1\right) + \sum\limits_{r=1}^{\frac{p-1}{2}}\left(\lambda_{mr+2} - \lambda_{mr+1}\right) + \sum\limits_{r=1}^{\frac{p-1}{2}}\left(\lambda_{mr-2}-\lambda_{mr-1}\right)=0.
\end{eqnarray}
If $C_n$ admits PGST then, by Equation $\left(\ref{e0}\right)$, we have a sequence of real numbers $\{t_k\}$ and a complex number $\gamma$ with $|\gamma|=1$ such that
\[\lim_{k\rightarrow\infty}\sum\limits_{l=0}^{n-1}\exp{\left[-i\left(\lambda_l t_k+l\pi\right)\right]}=n\gamma.\]
Since the unit circle is compact, we have a subsequence $\{t'_k\}$ of $\{t_k\}$ such that
\[\lim_{k\rightarrow\infty}\exp{[-i\left(\lambda_l t'_k+l\pi\right)]}=\gamma,\text{ for }0\leq l\leq n-1.\]
This further implies that
\[\lim_{k\rightarrow\infty}\exp{[-i\left(\lambda_{l+1}-\lambda_l\right)t'_k]}=-1.\]
Denoting the term in left hand side of Equation $\left(\ref{e5}\right)$ as $L$, we find that
\[\lim_{k\rightarrow\infty}\exp{\left(-iLt'_k\right)}=-1.\]
But this is not possible as $L=0$. Hence there is no pretty good state transfer in $C_n$ whenever $n$ has an odd prime factor.
\end{proof}
In the next result we see that if $p$ is an odd prime and $m\in \Nl$, then the complement of the cycle $C_{mp}$ does not admit PGST. This gives an another class of circulant graphs not allowing PGST. We provide this result as a corollary.
\begin{cor}\label{c2}
Let $m\in\Nl$ such that $n=mp$ for some odd prime $p$. Then the complement of the cycle $C_{n}$ does not exhibit pretty good state transfer.
\end{cor}
\begin{proof}
For $m=1$, by Lemma \ref{l0}, we conclude that complement of $C_{n}$ does not admit PGST.
So we only consider the case $m\geq 2$.\par
The cycles are regular graphs. Therefore the eigenvalues of the complement of $C_{n}$ are $\lambda'_0=n-\lambda_0-1$ and $\lambda'_l=-\lambda_l-1,$ whenever $1\leq l\leq n-1,$ corresponding to the same set of eigenvectors as that of $C_{n}$. This means that $\left(0,\frac{n}{2}\right)$-th entry of the transition matrix of the complement $\overline{C}_{n}$ can be obtained from Equation $\left(\ref{e0}\right)$ by replacing the eigenvalues $\lambda_l$ with $\lambda'_l$. If $C_{mp}$ exhibits PGST then by the same argument as given in Lemma \ref{l2}, we have a sequence $\{t'_k\}$ of real numbers satisfying
\begin{eqnarray}\label{e9}
\lim_{k\rightarrow\infty}\exp{[-i\left(\lambda'_l t'_k+l\pi\right)]}=\gamma,\;|\gamma|=1,\text{ for }0\leq l\leq mp-1.
\end{eqnarray}
Let $L'=\left(\lambda'_2 - \lambda'_1\right) + \sum\limits_{r=1}^{\frac{p-1}{2}}\left(\lambda'_{mr+2} - \lambda'_{mr+1}\right) + \sum\limits_{r=1}^{\frac{p-1}{2}}\left(\lambda'_{mr-2}-\lambda'_{mr-1}\right).$ Using Equation $\left(\ref{e9}\right)$ and proceeding as in the proof of Lemma \ref{l2}, we find that
\begin{eqnarray}\label{e10}
\lim_{k\rightarrow\infty}\exp{\left(-iL't'_k\right)}=-1.
\end{eqnarray}
Now using $\lambda'_0=n-\lambda_0-1$ and $\lambda'_l=-\lambda_l-1$ for $1\leq l\leq n-1,$ in Equation $\left(\ref{e3}\right)$ and Equation $\left(\ref{e4}\right),$ we obtain
\begin{eqnarray*}
L'=\begin{cases}
2p,\;\text{if }m=2;\\
0,\;\;\;\text{if }m\geq 3.
\end{cases}
\end{eqnarray*}
Since $L'=0$ for $m\geq 3$, Equation $\left(\ref{e10}\right)$ gives a contradiction.\\
Now consider the case $m=2.$ Putting $l=p$ in Equation $\left(\ref{e9}\right),$ we get $\lim\limits_{k\rightarrow\infty}\exp{\left(-it'_k\right)}=-\gamma,$ as $\lambda'_p=1.$ Since $L'=2p$ for $m=2$, Equation $\left(\ref{e10}\right)$ gives $\left(-\gamma\right)^{2p}=-1,$ i.e, $\gamma^{2p}=-1.$ Again from Equation $\left(\ref{e9}\right),$ we get
\begin{eqnarray*}
&&\lim_{k\rightarrow\infty}\exp{[-i\left(\lambda'_1+\lambda'_{p-1}\right)t'_k]}=-\gamma^2\\
\text{or,}&&\lim_{k\rightarrow\infty}\exp{[-i(-2)t'_k]}=-\gamma^2,\text{ as }\lambda'_1+\lambda'_{p-1}=-2\\
\text{or,}&&\left(-\gamma\right)^{-2}=-\gamma^2,\text{ as }\lim_{k\rightarrow\infty}\exp{\left(-it'_k\right)}=-\gamma\\
\text{or,}&&\gamma^4=-1,
\end{eqnarray*}
which contradicts the fact that $\gamma^{2p}=-1$ as $p$ is odd. Hence we conclude that the complement of $C_{mp}$ does not exhibit PGST.
\end{proof}
Combining Lemma \ref{l1} and Lemma \ref{l2}, we get a complete characterization for PGST on cycles. Similarly, combining Theorem \ref{t1} and Corollary \ref{c2}, we obtain a complete characterization for PGST on complement of cycles as well. These two characterizations, along with Lemma \ref{l0}, are combined as the following theorem.
\begin{theorem}
A cycle $C_n$ as well as its complement $\overline{C}_n$ admit pretty good state transfer if and only if $n=2^k$ for $k\geq 2$, and it occurs between
every pair of antipodal vertices.
\end{theorem}
\section{Conclusions}
In the past decade the study of PST in graphs has received considerable attention. Now we know a handful of graphs exhibiting PST. It is always preferable to find graphs having PST between vertices at a long distance. So far the best known graphs in this regard are the hypercubes. In a hypercube with $n$ vertices, we have PST between vertices at a distance $\log_2(n)$. It is thus desirable to have graphs allowing PST between vertices at a distance of $O(n).$ Most lucrative classes of graphs in this regard are the paths $P_n$ and the cycles $C_n$ as both of them have large diameter. But it is well known that $P_n$ does not exhibit PST whenever $n\geq 4$ and $C_n$ admits PST only when $n=4$.\par
Meanwhile the study of PGST got some interest. In \cite{god4}, the authors presented a remarkable result which classifies the paths $P_n$ admitting PGST between the end vertices. This serves as an example where PGST takes place between vertices at a distance $n$. In this article, we found that $C_{n}$ exhibits PGST if and only if $n$ is a power of two and PGST occurs between any pair of antipodal vertices. This gives an another class of graphs having PGST between vertices at a distance of $O(n).$ We also found a good number of circulant graphs allowing or not allowing PGST. Apart from the circulant graphs, we found some other graphs allowing PGST.\par
We found that the circulant graph $C_{2^k}\cup G\left(2^k,D\right)$ for $k\geq3,1\not\in D,$ admits PGST. However, it is not known if there are any other circulant graphs allowing PGST. It is thus desirable to classify which circulant graphs exhibit PGST. More generally, it is preferable to have a characterization of PGST in Cayley graphs.
\section*{Acknowledgments}
We would like to thank Professor Chris Godsil, University of Waterloo, for his valuable suggestions regarding the work presented in this paper. Also we are very grateful to the anonymous referee for the critical review and invaluable comments to improve the manuscript.
\begin{thebibliography}{10}
\bibitem{ack} E.~Ackelsberg, Z.~Brehm, A.~Chan, J.~Mundinger, and C.~Tamon. \newblock Laplacian State Transfer in Coronas. \newblock \emph{Linear Algebra and its Applications}, \textbf{506}:154--167, 2016.
\bibitem{ack1} E. Ackelsberg, Z. Brehm, A. Chan, J. Mundinger, and C. Tamon. \newblock Quantum State Transfer in Coronas. \newblock \arxiv{1605.05260}.
\bibitem{apo} T. M. Apostol. \newblock Modular Functions and Dirichlet Series in Number Theory. \newblock \emph{2nd ed. New York: Springer-Verlag}, 1997.
\bibitem{mil4} M. Ba\v si\'c. \newblock Characterization of Circulant Networks having Perfect State Transfer. \newblock \emph{Quantum Information Processing}, \textbf{12}(1):345--364, 2013.
\bibitem{ben} C. H. Bennett and G. Brassard. \newblock Quantum Cryptography: Public Key Distribution and Coin Tossing. \newblock \emph{Proc. IEEE Int. Conf. Computers Systems and Signal Processing, Bangalore, India}, 175--179, 1984.
\bibitem{ber} A. Bernasconi, C. Godsil, and S. Severini. \newblock Quantum Networks on Cubelike Graphs. \newblock \emph{Physical Review A}, \textbf{78}(5):052320, 2008.
\bibitem{bose} S. Bose. \newblock Quantum Communication through an Unmodulated Spin Chain. \newblock \emph{Physical Review Letters}, \textbf{91}(20):207901, 2003.
\bibitem{cha} R. J. Chapman, M. Santandrea, Z. Huang, G. Corrielli, A. Crespi, M. H. Yung, R. Osellame, and A. Peruzzo. \newblock Experimental Perfect State Transfer of an Entangled Photonic Qubit. \newblock \emph{Nature Communications}, \textbf{7}:11339, 2016.
\bibitem{chi} W. Cheung and C. Godsil. \newblock Perfect State Transfer in Cubelike Graphs. \newblock \emph{Linear Algebra and its Applications}, \textbf{435}(10):2468--2474, 2011.
\bibitem{chr2} M. Christandl, N. Datta, T. Dorlas, A Ekert, A. Kay, and A. J. Landahl. \newblock Perfect Transfer of Arbitrary States in Quantum Spin Networks. \newblock \emph{Physical Review A}, \textbf{71}(3):032312, 2005.
\bibitem{chr1} M. Christandl, N. Datta, A. Ekert, and A. J. Landahl. \newblock Perfect State Transfer in Quantum Spin Networks. \newblock \emph{Physical Review Letters}, \textbf{92}(18):187902, 2004.
\bibitem{cou} G. Coutinho and C. Godsil. \newblock Perfect State Transfer in Products and Covers of Graphs. \newblock \emph{Linear and Multilinear Algebra}, \textbf{64} (2):235--246, 2016.
\bibitem{cou1} G. Coutinho and C. Godsil. \newblock Perfect State Transfer is Poly-time. \newblock \arxiv{1606.02264}.
\bibitem{cou2} G. Coutinho, C. Godsil, K. Guo, and F. Vanhove. \newblock Perfect State Transfer on Distance-regular Graphs and Association Schemes. \newblock \emph{Linear Algebra and its Applications}, \textbf{478}:108--130, 2015.
\bibitem{ek} A. K. Ekert. \newblock Quantum Cryptography based on Bell's Theorem. \newblock \emph{Physical Review Letters}, \textbf{67}(6):661, 1991.
\bibitem{esc} J. P. Escofier. \newblock Galois Theory. \newblock \emph{1st ed. New York: Springer-Verlag}, 2001.
\bibitem{fan} X. Fan and C. Godsil. \newblock Pretty Good State Transfer on Double Stars. \newblock \emph{Linear Algebra and its Applications}, \textbf{438}(5):2346--2358, 2013.
\bibitem{god3} C. Godsil. \newblock Periodic Graphs. \newblock \emph{The Electronic Journal of Combinatorics}, \textbf{18}(1): P23, 2011.
\bibitem{god1} C. Godsil. \newblock State Transfer on Graphs. \newblock \emph{Discrete Mathematics}, \textbf{312}(1):129--147, 2012.
\bibitem{god2} C. Godsil. \newblock When can Perfect State Transfer occur? \newblock \emph{Electronic Journal of Linear Algebra}, \textbf{23}:877--890, 2012.
\bibitem{god4} C. Godsil, S. Kirkland, S. Severini, and J. Smith. \newblock Number-theoretic Nature of Communication in Quantum Spin Systems. \newblock \emph{Physical Review Letters}, \textbf{109}(5): 050502, 2012.
\bibitem{kirk} S. Kirkland. \newblock Sensitivity Analysis of Perfect State Transfer in Quantum Spin Networks. \newblock \emph{Linear Algebra and its Applications}, \textbf{472}:1--30, 2015.
\bibitem{wal1} W. Klotz and T. Sander. \newblock Integral Cayley Graphs over Abelian Groups. \newblock \emph{The Electronic Journal of Combinatorics}, \textbf{17}: R81, 2010.
\bibitem{mala} G. Malajovich. \newblock An Effective Version of Kronecker's Theorem on Simultaneous Diophantine Approximation. \newblock \emph{Instituto de Matem\'atica da Universidade Federal do Rio de Janeiro}, Brasil, 2001.
\bibitem{pal2} H. Pal and B. Bhattacharjya. \newblock A class of gcd-graphs having Perfect State Transfer. \newblock \emph{Electronic Notes in Discrete Mathematics}, \textbf{53}:319--329, 2016.
\bibitem{pal1} H. Pal and B. Bhattacharjya. \newblock Perfect State Transfer on gcd-graphs. \newblock \emph{Linear and Multilinear Algebra}, \doi{10.1080/03081087.2016.1267105}.
\bibitem{pal} H. Pal and B. Bhattacharjya. \newblock Perfect State Transfer on NEPS of the Path on Three Vertices. \newblock \emph{Discrete Mathematics}, \textbf{339}(2):831--838, 2016.
\bibitem{pal3} H. Pal and B. Bhattacharjya. \newblock Pretty Good State Transfer on some NEPS. \newblock \emph{Discrete Mathematics}, \textbf{340}(4):746--752, 2017.
\bibitem{so} W. So. \newblock Integral Circulant Graphs. \newblock \emph{Discrete Mathematics}, \textbf{306}(1):153--158, 2006.
\end{thebibliography}
\end{document}