\section{Introduction}
There are two types of quantum walks: continuous-time and discrete-time. In a continuous quantum walk, the evolution is usually determined by the adjacency matrix or the Laplacian matrix of the graph. Hence, certain properties of the walk, such as perfect state transfer, uniform mixing and fractional revival, translate into properties of the graph (see, for example, \cite{Godsil2012,Chan2013,Chan2018}). On the other hand, the transition matrix of a discrete quantum walk is a product of two non-commuting sparse unitary matrices, whose sizes usually equal the number of arcs of the graph. Moreover, the choice of these sparse matrices is not unique. Such freedom leads to various models of discrete quantum walks (see, for example, \cite{Aharonov2000,Szegedy2004,Kendon2003,Portugal2015}); however, the relation between graph properties and walk properties is less clear.

In this paper, we study a discrete quantum walk formalized by Kendon \cite{Kendon2003}. The transition matrix is a product of two matrices: the arc-reversal matrix, which maps an arc $(a, b)$ to the arc $(b, a)$, and a Grover coin matrix, which sends an arc $(a, b)$ to certain linear combination of the outgoing arcs of vertex $a$. Over the past few years, investigation of this model on specific families of graphs has received an increased attention. For example, Konno et al \cite{Konno2019} characterized the positive support of the $m$-th power of the transition matrix for regular graphs with girth greater than $2m-1$, and Yoshie \cite{Yoshie2019} characterized certain distance regular graphs on which this walk is periodic. Following their notion, we will refer to this walk as the \textsl{Grover walk}. 

The graphs we consider in this paper are distance regular. Let $U$ be the transition matrix of a Grover walk. Then $U^2$ is the transition matrix of another discrete quantum walk defined by Szegedy \cite{Szegedy2004}. We show that if our graph $X$ is distance regular of diameter $d$ with invertible adjacency matrix, then
\[U^2 = \exp(t_1 S_1) \exp(t_2 S_2) \cdots (\exp(t_d S_d)),\]
where $S_i$ is the skew-adjacency matrix of the $i$-th distance digraph of the line digraph of $X$. Moreover, $S_i$ and $S_j$ commute. This reveals an interesting connection between discrete quantum walks on graphs and continuous quantum walks on oriented graphs.


\section{Grover Walks}
To gather more combinatorial insights into the Grover walk, we start this section with an alternative definition given by Godsil and Guo \cite{Godsil2010Guo}.


Throughout, let $X$ be a $k$-regular graph. We will replace each edge $\{a,b\}$ of $X$ by two arcs $(a,b)$ and $(b,a)$. The \textsl{line digraph} of $X$, denoted $\LD(X)$, is the digraph whose vertices are the arcs of $X$, and $(a,b)$ is adjacent to $(c,d)$ in $\LD(X)$ if $b=c$. Note that the adjacency in $\LD(X)$ is not a symmetric relation. In Figure \ref{fig_LDK3}, we illustrate $K_3$ and its the line digraph. 
\begin{figure}[h]
	\centering
\begin{minipage}{0.5\textwidth}
\includegraphics[width=6cm]{K3}
\end{minipage}%
\begin{minipage}{0.5\textwidth}
\includegraphics[width=6cm]{LD}
\end{minipage}
\caption{A Planar Embedding of $K_4$}
\label{fig_LDK3}
\end{figure}

Let $A(\LD(X))$ denote the $01$-adjacency matrix of $\LD(X)$. Let $R$ denote the \textsl{arc-reversal matrix}, that is, the permutation matrix on the arcs that maps $(a,b)$ to $(b,a)$. We define the \textsl{transition matrix} of the Grover walk on $X$ to be
\[U:= \frac{2}{k} A(\LD(X)) -R.\]

For those who are familiar with the original description of the Grover walk, we show the equivalence between these two definition. To this end, we introduce two more matrices, $D_t$ and $D_h$, whose rows are indexed by the vertices of $X$, and columns by the arcs of $X$:
\[(D_t)_{u, ab} = \begin{cases}
1,\quad u=a\\
0,\quad \text{otherwise}
\end{cases}\]
and
\[(D_h)_{u, ab} = \begin{cases}
1,\quad u=b\\
0,\quad \text{otherwise}
\end{cases}\]
We sometimes refer to $D_t$ as the \textsl{tail-arc} incidence matrix, and $D_h$ the \textsl{head-arc} incidence matrix. It is not hard to verity the following.

\begin{lemma}\label{lem_props}
Let $X$ be a $k$-regular graph. The incidence matrices $D_t$ and $D_h$ satisfy the following identities.
\begin{enumerate}[(i)]
\item $D_t R = D_h$
\item $D_tD_t^T = D_hD_h^T=kI$
\item $D_tD_h^T = D_hD_t^T = A(X)$
\item $D_h^TD_t = A(\LD(X))$
\qed
\end{enumerate}
\end{lemma}

Hence, 
\begin{align*}
U &= \frac{2}{k}A(\LD(X)) - R\\
&= \frac{2}{k} D_h^TD_t - R\\
&=R\left(\frac{2}{k}D_t^TD_t-I\right),
\end{align*}
where $\frac{2}{k}D_t^TD_t-I$ is precisely the coin matrix.




\section{Distances in digraphs}
Given a digraph $Y$, let $\dist_Y(a,b)$ denote the distance in $Y$ from $a$ to $b$. Note that in general $\dist_Y(a,b)\ne \dist_Y(b,a)$. 

There is a simple relation between the distances in a graph and the distances in its line digraph.

\begin{lemma}\label{lem_dist}
Let $(a,b)$ and $(c,d)$ be two arcs of $X$. Then
\[\dist_{\LD(X)}((a,b),(c,d)) =\begin{cases}
\dist_X(b,c)-1,\quad \text{if }(a,b)=(c,d)\\
\dist_X(b,c)+1,\quad \text{otherwise}.
\end{cases}\]
\end{lemma}
\proof
The case where $(a,b)$ coincides with $(c,d)$ is trivial. Suppose $(a,b)$ is different from $(c,d)$. If there is a dipath $u_0=b, u_1, u_2, \cdots, u_m=c$ in $X$ from $b$ to $c$, then $(a, u_0), (u_0, u_1), (u_1,u_2),\cdots, (u_m, d)$ is a dipath in $\LD(X)$ from $(a,b)$ to $(c,d)$. This shows
\[\dist_{\LD(X)}((a, b), (c, d)) \le \dist_X(b,c)+1\]
Now, suppose  $(a, u_0), (u_0, u_1), (u_1,u_2),\cdots, (u_m, d)$ is a shortest dipath in $\LD(X)$ from $(a,b)$ to $(c,d)$. Then for any $i\ne j$, we have $u_i\ne u_j$, as otherwise we could have removed the portion from $(u_i, u_{i+1})$ to $(u_{j-1}, u_j)$ to get a shorter dipath. Hence, $u_0,u_1,u_2,\cdots,u_m$ is a dipath in $X$ from $b$ to $c$, and so
\[\dist_X(b,c)\ge \dist_{LD(X)}((a,b),(c,d))-1.\tag*{\sqr53}\]

\section{Distance regular graphs and their line digraphs}
A graph is \textsl{distance regular} if for any two vertices $u$ and $v$ at distance $\ell$, the number of vertices at distance $i$ from $u$ and distance $j$ from $v$ is a constant $p_{ij}^{\ell}$, which depends only on the distances $i$, $j$ and $\ell$. The parameters $p_{ij}^{\ell}$ are called the \textsl{intersection numbers}.

Suppose our graph $X$ is distance regular of diameter $d$. Let $A_i=A(X_i)$ denote the adjacency matrix of its $i$-th distance graph. It is well-known that
\[\{\seq{A}{0}{1}{d}\}\]
forms an association scheme (see, for example, \cite[Ch 12]{Godsil1993}). In particular, each eigenprojection $E_r$ of $A(X)$ is a linear combination of $\seq{A}{0}{1}{d}$:
\[E_r = \frac{1}{|V(X)|} \left(q_r(0) A_0 + q_r(1) A_1 +\cdots + q_r(d)A_d \right);\]
the parameters $q_r(i)$ are constants called the \textsl{dual eigenvalues}. Moreover, for any $i$ and $j$,
\[A_i A_j = \sum_{\ell=0}^d p_{ij}^{\ell} A_{\ell}.\]



We can generalize distance regularity to digraphs. A digraph $Y$ is \textsl{distance regular} if for any two vertices $u$ and $v$ with
$\dist_Y(u,v)=\ell$, the number of vertices $w$ such that $\dist_Y(u,w)=i$ and $\dist_Y(w,v)=j$ depends only on the distances $i$,$j$ and $\ell$; we denote this number by $m_{ij}^{\ell}$.

Now, we are ready to show that the line digraph of a distance regular graph is distance regular.

\begin{lemma}\label{lem_drdg}
Let $X$ be a distance regular graph. Let $Y=\LD(X)$ be its line digraph. Then $Y$ is a distance regular digraph. Moreover, for any $i$ and $j$, we have $m_{ij}^{\ell} = m_{ji}^{\ell}$. 
\end{lemma}
\proof
Let $(a,b)$ and $(c,d)$ be two arcs of $X$. We count arcs $(x,y)$ that are at distance $i$ from $(a,b)$ and from which $(c,d)$ is at distance $j$.  

We will prove the case where $i,j\ge 1$; the other cases follow from a similar argument. By Lemma \ref{lem_dist}, we are counting elements in the set
\[\Phi:=\{(x,y): \dist_X(b,x)=i-1, \dist_X(y, c)=j-1, \dist_X(x,y)=1\}.\]
On the other hand,
\[(A_{i-1} A_1 A_{j-1})_{bc} = \sum_x \sum_y (A_{i-1})_{bx} (A_1)_{xy} (A_{j-1})_{yc}=\@ifstar{\oldabs}{\oldabs*}{\Phi}.\]
Since $X$ is distance regular, there are intersection numbers $p_{1,j-1}^{m}$ and $p_{i-1,m-1}^{\ell}$ such that
\begin{align*}
A_{i-1} A_1 A_{j-1} &= A_{i-1} \sum_{m} p_{1,j-1}^{m} A_{m}\\
&=\sum_{\ell} \sum_{m} p_{i-1,m-1}^{\ell} p_{1,j-1}^{m} A_{\ell}.
\end{align*}
Therefore, the size of $\Phi$ is a constant $m_{ij}^{\ell}$ that depends only on $i$, $j$ and $\ell$. By Lemma \ref{lem_dist}, $\ell$ is determined by the distance from $(a,b)$ to $(c,d)$. Finally, since $A_{i-1}$ commutes with $A_{j-1}$, we have $m_{ij}^{\ell} = m_{ji}^{\ell}$. 
\qed

Let $Y$ be a digraph. The $i$-th \textsl{distance digraph} of $Y$, denoted $Y_i$, has the same vertex set as $Y$, and vertex $a$ is adjacent to vertex $b$ in $Y_i$ if $\dist_Y(a,b)=i$.  One consequence of Lemma \ref{lem_drdg} is that the $01$-adjacency matrices of the distance digraphs of $\LD(X)$ commute, if $X$ is distance regular. Moreover, we have a formula for these adjacency matrices.


\begin{lemma}\label{lem_form}
Let $X$ be a distance regular graph. Let $A_i$ be the adjacency matrix of its $i$-th distance graph. Let $Y=\LD(X)$. Let $Y_i$ be the $i$-th distance digraph of $Y$. Then $A(Y_0)=I$, $A(Y_2) = D_h^T A_1 D_t-I$, and for $i= 1,3,\cdots,d+1$, $A(Y_i) = D_h^T A_{i-1} D_t $. 
\qed
\end{lemma}

Using Lemma \ref{lem_form}, we can verify two properties of $A(Y_i)$, one of which we have already seen.
\begin{corollary}\label{cor_props}
Let $X$ be a distance regular graph. Let $Y=\LD(X)$. Let $Y_i$ be the $i$-th distance digraph of $Y$. Then the following statements hold.
\begin{enumerate}[(i)]
\item $A(Y_0), A(Y_1), \cdots,A(Y_{d+1})$ sum to $J$.
\item $Y$ is distance regular.
\end{enumerate}
\end{corollary}
\proof
We prove (i); the other statement follows similarly. By Lemma \ref{lem_form}, 
\[\sum_{i=0}^{d+1}A(Y_i) = I + (D_h^TA_0D_t) + (D_h^TA_1D_t-I) + \sum_{i=2}^dD_h^TA_{i-1}D_t\]
which reduces to $D_h^TJ D_t$. Since each column of $D_h$ or $D_t$ has exactly one non-zero entry, we have $D_h^TJD_t=J$.
\qed

Given a digraph $Y$, let $S(Y)$ denote its \textsl{skew-adjacency matrix}, that is,
\[S(Y) = A(Y) - A(Y)^T.\]
Note that $A(Y)$ and $A(Y)^T$ may not have disjoint supports, so the underlying oriented graph of $S(Y)$ may differ from $Y$. We illustrate this situation in Figure \ref{fig_supp}.

\begin{figure}[h]
	\centering
\begin{minipage}{0.5\textwidth}
\includegraphics[width=6cm]{LD}
\end{minipage}%
\begin{minipage}{0.5\textwidth}
\includegraphics[width=8cm]{LDnorev}
\end{minipage}
\caption{$\LD(K_3)$ and the underlying oriented graph of $S(\LD(K_3))$}
\label{fig_supp}
\end{figure}



Two properties of $S(Y_i)$ follow from Lemma \ref{lem_form} and Corollary \ref{cor_props}.
\begin{corollary}\label{cor_SY}
Let $X$ be a $k$-regular distance regular graph. Let $Y_i$ be the $i$-th distance digraph of $\LD(X)$. The following statements hold.
\begin{enumerate}[(i)]
\item $S(Y_0),S(Y_1),\cdots,S(Y_{d+1})$ are linearly dependent.
\item For $i,j=0,1,\cdots,d+1$,
\[S(Y_i) S(Y_j) = S(Y_j) S(Y_i).\tag*{\sqr53}\]
\end{enumerate}
\end{corollary}

\section{Spectral decomposition}
Let $X$ be a distance regular graph of diameter $d$. Let $U$ be the transition matrix of the Grover walk on $X$. In this section, we derive some properties of the eigenprojections of $U$. 

We first cite a result from \cite{Zhan2019}.

\begin{theorem}\label{thm_spd}
Every non-real eigenvalue of $U$ comes from an eigenvalue of $A(X)$. More specifically, let $\lambda$ be an eigenvalue of $A(X)$ that is neither $k$ nor $-k$. Let $E_{\lambda}$ be the orthogonal projection onto the $\lambda$-eigenspace of $X$. Suppose $\lambda=k\cos(\theta)$ for some real number $\theta$. Then $e^{i\theta}$ is an eigenvalue of $U$ with eigenprojection
\[F_{\theta_+} = \frac{1}{2k \sin^2(\theta)} (D_t - e^{i\theta} D_h)^T E_{\lambda} (D_t - e^{-i\theta} D_h),\]
and $e^{-i\theta}$ is an eigenvalue of $U$ with eigenprojection
\[F_{\theta_-}=\frac{1}{2k\sin^2(\theta)} (D_t - e^{-i\theta} D_h)^T E_{\lambda} (D_t - e^{i\theta} D_h).\tag*{\sqr53}\]
\end{theorem}

As a consequence, for any non-real eigenvalue $e^{i\theta}$ of $U$, the difference $F_{\theta_+} - F_{\theta_-}$ is an imaginary scalar multiple of some real skew-symmetric matrix. 

\begin{corollary}\label{cor_Fdiff}
Let $\lambda$ be an eigenvalue of $A(X)$ that is neither $k$ nor $-k$. Let $E_{\lambda}$ be the orthogonal projection onto the $\lambda$-eigenspace of $X$. Suppose $\lambda = k\cos(\theta)$ for some real number $\theta$. Let $F_{\theta_+}$ and $F_{\theta_-}$ be the $e^{i\theta}$-eigenprojection and the $e^{-i\theta}$-eigenprojection, respectively. Then $F_{\theta_+} - F_{\theta_-}$ is an imaginary scalar multiple of 
\[D_t^TE_{\lambda} D_h - D_h^T E_{\lambda} D_t. \tag*{\sqr53}\]
\end{corollary}

We now fix a $\lambda$ that satisfies the condition in Corollary \ref{cor_Fdiff}, and set
\[S_{\lambda} := D_t^TE_{\lambda} D_h - D_h^T E_{\lambda} D_t.\]
We show that if $X$ is distance regular, then $S_{\lambda}$ is a linear combination of the skew adjacency matrices of the distance digraphs of $\LD(X)$.

\begin{lemma}\label{lem_span}
Let $X$ be a distance regular graph of diameter $d$. Let $Y = \LD(X)$. Let $Y_i$ be the $i$-th distance digraph of $Y$. Then
\[S_{\lambda} \in \mathrm{span} \{S(Y_1),S(Y_2),\cdots,S(Y_d)\}\]
\end{lemma}
\proof
Recall that $E_{\lambda}$ lies in the span of $\{A_i:i=0,1,\cdots,d\}$. By the formula 
\[S_{\lambda} = D_t^TE_{\lambda} D_h - D_h^T E_{\lambda} D_t,\]
we see $S_{\lambda}$ lies in the span of $\{S(Y_i):i=0,1,\cdots,d+1\}$. Moreover, Corollary \ref{cor_SY} shows that $S(Y_0), S(Y_1),\cdots,S(Y_{d+1})$ are linearly dependent. Hence
\[S_{\lambda} \in \mathrm{span} \{S(Y_1),S(Y_2),\cdots,S(Y_d)\}.\tag*{\sqr53}\]



\section{Factoring $U^2$}
Let $X$ be a $k$-regular distance regular graph. Let $U$ be the transition matrix of the Grover walk on $X$. We can write the spectral decomposition of $U$ as
\[U = \sum_r e^{i\theta_r} F_r,\]
for some real numbers $\theta_r \in(-\pi, \pi]$. Thus
\[U^2 = \sum_r e^{2i\theta_r} F_r.\]
From Theorem \ref{thm_spd}, we see that if $\theta_r\in(0,\pi)$, then $k\cos (\theta)$ is an eigenvalue of $A(X)$. 


Now, we assume in addition that $A(X)$ is invertible. It follows that $\pm i$ are not eigenvalues of $U$, that is, $-1$ is not an eigenvalue of $U^2$. Hence, we have
\[U^2=  \exp(iH),\]
where 
\[H = 2 \sum_{r: 0<\theta_r<\pi} (F_r- \comp{F_r}).\]
Our discussion in the last section shows that $H$ is a linear combination of the skew-adjacency matrices of the distance digraphs of $\LD(X)$.

\begin{theorem}
Let $X$ be a distance regular graph with diameter $d$. Let $U$ be the transition matrix of the Grover walk on $X$. Let $Y_i$ be the $i$-th distance digraph of $\LD(X)$. If $A(X)$ is invertible, then there are real scalars $\seq{t}{1}{2}{d}$ such that
\[U^2 = \exp(t_1S(Y_1)) \exp(t_1 S(Y_2))\cdots \exp(t_d S(Y_d)).\]
\end{theorem}
\proof
We have
\[U^2 = \exp(iH)\]
where 
\[H = 2 \sum_{r: 0<\theta_r<\pi} (F_r- \comp{F_r}).\]
By Lemma \ref{lem_span}, $H$ is a linear combination of $S(Y_1), S(Y_2),\cdots,S(Y_d)$. By Corollary \ref{cor_SY}, these skew-adjacency matrices commute, so we can factor $U^2$ into the desired form.
\qed

If we rewrite $\exp(t_iS(Y))$ in the above theorem as $\exp(i t_i (iS(Y_i)))$, then we have the transition matrix of a continuous quantum walk on an oriented graph, evaluated at time $t_i$. Thus, for a distance regular graph with diameter $d$ and invertible adjacency matrix, the Grover walk on it factors into at most $d$ continuous quantum walks on the distance digraphs of $\LD(X)$. In particular, a discrete quantum walk on $K_n$ is equivalent to a continuous quantum walk on its line digraph.

\begin{corollary}
Let $U$ be the Grover walk on $K_n$. Then there is a real scalar $t$ such that
\[U^2 = \exp(t S(\LD(K_n))).\tag*{\sqr53}\]
\end{corollary}

The Grover walk on an invertible strongly regular graph factors into at most two continuous quantum walks. For the Petersen graph $P$, the factors of $U^2$ are continuous quantum walks on the oriented graphs shown in Figure \ref{fig_LDPet}.


\begin{figure}[h]
	\centering
\begin{minipage}{0.5\textwidth}
\includegraphics[width=6cm]{LDPet}
\end{minipage}%
\begin{minipage}{0.5\textwidth}
\includegraphics[width=6cm]{LDPet2}
\end{minipage}
\caption{Underlying oriented graphs of $S(\LD(P))$ and $S(\LD(P)_2)$}
\label{fig_LDPet}
\end{figure}


Finally, we remark here that not all $d$ distance digraphs may show up in the factorization. For example, if $U$ is the Grover walk of the $3$-cube $Q_3$, and $Y_2$ is the second distance digraph of $\LD(Q_3)$, then there is a scalar $t$ such that $U^2 = \exp(t S(Y_2))$.


\section{Future work}
In this paper, we showed a connection between a discrete quantum walk on an invertible distance regular graph and some continuous quantum walks on the distance digraphs of its line digraph. It will be interesting to translate properties on the discrete side, such as perfect state transfer, into properties on the continuous side, and vice versa.

Our factorization relies on the ``lift" from the eigenspaces of the graph to the eigenspaces of the transition matrix, as stated in Theorem \ref{thm_spd}. With a similar argument, we can factor discrete quantum walks on other graphs with nice eigenspaces. We plan to work on this problem for Cayley graphs.

\section{Acknowledgment}
The author would like to thank Ada Chan for her inspiring discussion.

\bibliographystyle{amsplain}
