\documentclass[ALCO,ThmDefs,Unicode,epreuves]{cedram}

\def\ints{\mathbb{Z}}
\def\reals{\mathbb{R}}
\def\cx{\mathbb{C}}
\def\cA{\mathcal{A}}
\def\cB{\mathcal{B}}
\def\cE{\mathcal{E}}
\def\cH{\mathcal{H}}
\def\cP{\mathcal{P}}
\def\th{\theta}
\def\a{\alpha}
\def\b{\beta}
\def\g{\gamma}
\def\G{\Gamma}
\def\e{\epsilon}
\def\mod#1{{\ \left(\modrm #1\right)}}

\DeclareMathOperator{\spn}{span}
\DeclareMathOperator{\modrm}{mod}
\DeclareMathOperator{\expe}{e}
\DeclareMathOperator{\irm}{i}
\DeclareMathOperator{\irmbis}{i}

\def\hp{\widehat{p}}
\def\hX{\widehat{X}}
\def\hA{\widehat{A}}
\def\fp{\widetilde{p}}
\def\fa{\widetilde{a}}
\def\fb{\widetilde{b}}
\def\fc{\widetilde{c}}
\def\fX{\widetilde{X}}
\def\fA{\widetilde{A}}
\def\fG{\widetilde{\Gamma}}
\def\fhp{\mathcal{P}}
\def\fhX{\mathcal{X}}
\def\fhA{\mathcal{A}}



\def\one{\mathbf{1}}

\newcommand{\Dita}{{Di{\c{t}}{\u{a}}}}
\newcommand{\ium}{{instantaneous uniform mixing }}
\newcommand{\BM}{{Bose--Mesner }}





%%%%%%%%% a placer avant \begin{document}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand*{\mk}{\mkern -1mu}
\newcommand*{\Mk}{\mkern -2mu}
\newcommand*{\mK}{\mkern 1mu}
\newcommand*{\MK}{\mkern 2mu}

\hypersetup{urlcolor=purple, linkcolor=blue, citecolor=red}


\newcommand*{\romanenumi}{\renewcommand*{\theenumi}{\roman{enumi}}}
\newcommand*{\Romanenumi}{\renewcommand*{\theenumi}{\Roman{enumi}}}
\newcommand*{\alphenumi}{\renewcommand*{\theenumi}{\alph{enumi}}}
\newcommand*{\Alphenumi}{\renewcommand*{\theenumi}{\Alph{enumi}}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%% Auteur

\author{\firstname{Ada} \lastname{Chan}}

\address{York University\\ 
Dept. of Mathematics and Statistics\\
4700 Keele Street\\
Toronto\\ 
Ontario\\
M3J 1P3, Canada}

\email{ssachan@yorku.ca}


%%%%% Sujet

\keywords{Association schemes, Hamming schemes, complex Hadamard matrix, continuous-time quantum walks, instantaneous uniform mixing, perfect state transfer.}
 
\subjclass{05E03}


%%%%% Gestion

\DOI{10.5802/alco.112}
\datereceived{2019-06-22}
\daterevised{2020-02-09}
\dateaccepted{2020-02-09}


%%%%% Titre et résumé

\title
{Complex Hadamard matrices, instantaneous uniform mixing and cubes}

\begin{abstract}
We study the continuous-time quantum walks on graphs in the adjacency algebra of
the $n$-cube and its related distance regular graphs. 

For $k\geq 2$, we find graphs in the adjacency algebra of $(2^{k+2}-8)$-cube
that admit instantaneous uniform mixing at time $\pi/2^k$ and graphs that have perfect state transfer at time $\pi/2^k$.

We characterize the folded $n$-cubes, the halved $n$-cubes and the folded halved $n$-cubes
whose adjacency algebra contains a complex Hadamard matrix. We obtain the same conditions
for the characterization of these graphs admitting instantaneous uniform mixing.
\end{abstract}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



\begin{document}

\maketitle

\section{Introduction}

The continuous-time quantum walk on a graph $X$ is given by the transition operator
\begin{equation*}
\expe^{-\irm tA} = \sum_{k\geq 0} \frac{(-\irm t)^k}{k!}A^k,
\end{equation*}
where $A$ is the adjacency matrix of $X$.
For example, if $X$ is the complete graph on two vertices, $K_2$, then 
\begin{align*}
\expe^{-\irm tA} &= \left(1-\frac{t^2}{2!}+\frac{t^4}{4!}-\cdots \right) I - \irm \left(t-\frac{t^3}{3!} + \frac{t^5}{5!}-\cdots\right) A\\
&= \begin{pmatrix} \cos t & -\irm \sin t \\-\irm \sin t & \cos t\end{pmatrix}.
\end{align*}

Being the quantum analogue of the random walks on graphs, there is a lot of research interest on quantum walks
for the development of quantum algorithms. Moreover, quantum walks are proved to be universal for quantum computations
\cite{MR2507892}. In this paper, we focus on the continuous-time quantum walks introduced by Farhi and Gutmann in~\cite{MR1638221}.
Please see~\cite{MR2852516} and~\cite{quant-ph0303081} for surveys on quantum walks.


Since $A$ is real and symmetric, the operator $\expe^{-\irm tA}$ is unitary.
We say the continuous-time quantum walk on $X$ is {\sl \ium at time $\tau$} if
\begin{equation*}
|(\expe^{-\irm \tau A})_{a,b}| = \frac{1}{\sqrt{|V(X)|}},
\qquad \text{for all vertices $a$ and $b$.}
\end{equation*}
This condition is equivalent to $\sqrt{|V(X)|} \expe^{-\irm \tau A}$ being a complex
Hadamard matrix. Thus if $X$ admits \ium then its adjacency algebra
contains a complex Hadamard matrix.
In $K_2$, the continuous-time quantum walk is \ium at time $\pi/4$.

In~\cite{MR2047028}, Moore and Russell discovered that the continuous-time quantum walk on the $n$-cube
is \ium at time $\pi/4$ which is faster than its classical analogue. 
Ahmadi et al.~\cite{MR2023606} showed that the complete graph $K_q$ admits \ium if and only if $q\in \{2,3,4\}$.
Best et al.~\cite{arXiv:0808.2382} proved that
\ium occurs in graphs $X$ and $Y$ at time $\tau$ if and only if \ium occurs in 
their Cartesian product at the same time.
They concluded that the Hamming graph $H(n,q)$, which is the Cartesian product of $n$ copies of $K_q$,
has \ium if and only if $q\in \{2,3,4\}$.
In the same paper, they also proved that a folded $n$-cube admits \ium if and only if $n$ is odd.


In this paper, we give a necessary condition for the \BM algebra of a symmetric association scheme to
contain a complex Hadamard matrix. 
Applying this condition, we generalize the result of Best et al. to show that the adjacency algebra of $H(n,q)$
contains the adjacency matrix of a graph that admits \ium if and only if $q\in \{2,3,4\}$.
We characterize the halved $n$-cubes and the folded halved $n$-cubes that have instantaneous uniform mixing.
We obtain the same characterization for the folded $n$-cubes, the halved $n$-cubes and the folded halved $n$-cubes to have a complex
Hadamard matrix in their adjacency algebras.

A {\sl cubelike graph} is a Cayley graph of the elementary abelian group $\ints_2^d$.
The graphs appear in this paper are distance regular cubelike graphs.
For $k\geq 2$, we find graphs in the adjacency algebra of $H(2^{k+2}-8,2)$ that admit
\ium at time $\pi/2^k$.
Hence, for all $\tau >0$, there exists graphs that admit \ium at time less than $\tau$.

In a graph $X$, perfect state transfer occurs from vertex $u$ to vertex $w$ at time $\tau$ if 
\begin{equation*}
|(\expe^{-\irm \tau A(X)})_{u,w}|=1.
\end{equation*}
In the $n$-cube, perfect state transfer occurs between antipodal vertices at time $\pi/4$~\cite{quant-ph/0411020}.

Given a graph $X$, we use $A(X)$ to denote its adjacency matrix,
and $X_r$ to denote the graph on the vertex set $V(X)$ in which two vertices are adjacent if
they are at distance $r$ in $X$.
We use $I_v$ and $J_v$ to denote the $v\times v$ identity matrix and the $v\times v$
matrix of all ones, respectively.
We drop the subscript if the order of the matrices is clear.


\section{A Necessary Condition}
\label{Section_NecCond}

The graphs we study in this paper are distance regular. 
The adjacency algebra of a distance regular graph is the \BM algebra of a symmetric association scheme.
In this section, we give a necessary condition for a \BM algebra to contain a complex
Hadamard matrix. This condition is also necessary for a \BM algebra to contain the adjacency matrix
of a graph that admits instantaneous uniform mixing.


A {\sl symmetric association scheme} of order $v$ with $d$ classes is a set 
\begin{equation*}
\cA =\{A_0, A_1, \ldots, A_d\}
\end{equation*}
of $v\times v$ symmetric $01$-matrices satisfying
\begin{enumerate}
\item
$A_0=I$.
\item
$\sum_{j=0}^d A_j = J$.
\item
$A_j A_k = A_kA_j$, for $j,k=0,\ldots,d$.
\item
$A_j A_k \in \spn \cA$, for $j,k=0,\ldots,d$.
\end{enumerate}
For example, if $X$ is a distance regular graph with diameter $d$ and $X_j$ is the $j$-th distance graph of $X$, for $j=1,\ldots, d$, then
the set
$\{I, A(X_1), A(X_2),\ldots, A(X_d)\}$ is a symmetric association scheme.

The {\sl \BM algebra} of an association scheme $\cA$ is the span of $\cA$ over $\cx$.
It is known~\cite{MR1002568} that the \BM algebra contains another basis $\{E_0, E_1, \ldots, E_d\}$
 satisfying
\begin{enumerate}[(a)]
\item
\label{Eqn_Ej1}
$E_j E_k = \delta_{j,k}E_j$, for $j,k=0,\ldots,d$, and
\item
\label{Eqn_Ej2}
$\sum_{j=0}^d E_j = I$.
\end{enumerate}
Now there exist complex numbers $p_r(s)$'s such that
\begin{equation}
\label{Eqn_Ej4}
A_r = \sum_{s=0}^d p_r(s) E_s,
\qquad \text{for}\ r=0,\ldots,d.
\end{equation}
It follows from Condition~\ref{Eqn_Ej1} that
\begin{equation*}
A_r E_s = p_r(s) E_s,
\qquad \text{for $r,s =0,\ldots,d$}.
\end{equation*}
We call the $p_r(s)$'s {\sl the eigenvalues of the association schemes}.
Since the matrices in $\cA$ are symmetric, the $p_r(s)$'s are real.

A $v\times v$ matrix $W$ is {\sl type II} if, for $a,b=1,\ldots,v$,
\begin{equation}
\label{Eqn_TypeII}
\sum_{c=1}^v \frac{W_{ac}}{W_{bc}} = 
\begin{cases}
v & \text{if $a=b$,}\\
0 & \text{otherwise.}
\end{cases}
\end{equation}
A {\sl complex Hadamard matrix} is a type II matrix whose entries have absolute value one.

\begin{prop}\label{Prop_TypeII}
Let $\cA=\{A_0,A_1,\ldots,A_d\}$ be a symmetric association scheme.
Let $t_0,\ldots,t_d \in \cx\backslash\{0\}$.
The matrix $W=\sum_{j=0}^d t_j A_j$ is type II if and only if
\begin{equation*}
\left[\sum_{h=0}^d p_h(s) t_h \right]\left[\sum_{j=0}^d p_j(s) \frac{1}{t_j}\right] = v,
\qquad \qquad \text{for $s=0,1,\ldots,d$}.
\end{equation*}
\end{prop}
\begin{proof}
The matrix $W$ is type II if and only if
\begin{equation*}
\left[ \sum_{h=0}^d t_h A_h \right]
\left[ \sum_{j=0}^d \frac{1}{t_j} A_j \right] = vI.
\end{equation*}
It follows from Equation~\eqref{Eqn_Ej4} and Condition~\ref{Eqn_Ej2} that
\begin{equation*}
\left[\sum_{h=0}^d \sum_{l=0}^d t_h p_h(l) E_l \right]
\left[ \sum_{j=0}^d \sum_{k=0}^d \frac{1}{t_j} p_j(k) E_k \right] 
= v \sum_{r=0}^d E_r.
\end{equation*}
By Condition~\ref{Eqn_Ej1}, the left-hand side becomes
\begin{equation*}
\sum_{r=0}^d \left[\sum_{h=0}^d t_h p_h(r)\right] \left[\sum_{j=0}^d \frac{1}{t_j} p_j(r) \right] E_r,
\end{equation*}
multiplying $E_s$ to both sides yields the equations of this proposition.
\end{proof}

Finding type II matrices in the \BM algebra of a symmetric association scheme amounts to solving
the system of equations in Proposition~\ref{Prop_TypeII}, which is not easy as $d$ gets large.
When we limit the scope of the search to complex Hadamard matrices, we get the following
necessary condition which can be checked efficiently.

\begin{prop}\label{Prop_NecComHad}
If the \BM algebra of $\cA$ contains a complex Hadamard matrix, then
\begin{equation*}
v \leq \left[\sum_{r=0}^d |p_r(s)| \right]^2,
\qquad \text{for $s=0,1,\ldots,d$}.
\end{equation*}
\end{prop}
\begin{proof}
Suppose $W = \sum_{j=0}^d t_j A_j$ is a complex Hadamard matrix.
By Proposition~\ref{Prop_TypeII}, for $s=0,\ldots,d$,
\begin{equation*}
v = \sum_{r=0}^d p_r(s)^2 + \sum_{0\leq h < j \leq d} \left(\frac{t_h}{t_j}+\frac{t_j}{t_h}\right)p_h(s)p_j(s).
\end{equation*}
Since $|\frac{t_h}{t_j}|=1$, we have $| \frac{t_h}{t_j}+\frac{t_j}{t_h}|\leq 2$ and 
\begin{equation*}
v \leq \sum_{r=0}^d |p_r(s)|^2 + \sum_{0\leq h < j \leq d} 2 |p_h(s)p_j(s)|
= \left[\sum_{r=0}^d |p_r(s)| \right]^2.\qedhere
\end{equation*}
\end{proof}

Suppose $A(X)$ belongs to the \BM algebra of $\cA$.
If \ium occurs in $X$ at time $\tau$ then $\sqrt{v} \expe^{-\irm \tau A(X)}$
is a complex Hadamard matrix and the eigenvalues of $\cA$ satisfy the inequalities in 
Proposition~\ref{Prop_NecComHad}.
For example, the association scheme $\{I_q, J_q-I_q\}$ has eigenvalues $p_0(1)=1$ and $p_1(1)=-1$.
By Proposition~\ref{Prop_NecComHad}, if the
adjacency algebra of $K_q$ contains a complex Hadamard matrix then $q \leq 4$.
Hence \ium does not occur in $K_q$, for $q\geq 5$.

\begin{prop}\label{Prop_IUMeqn}
Let $X$ be a graph whose adjacency matrix belongs to the \BM algebra of $\cA$.
Let $\th_0,\ldots,\th_d$ be the eigenvalues of $A(X)$ satisfying
\begin{equation*}
A(X) = \sum_{s=0}^d \th_s E_s.
\end{equation*}
The continuous-time quantum walk of $X$ is \ium at time $\tau$ if and only if
there exist scalars $t_0,\ldots,t_d$ such that 
\begin{equation*}
|t_0|=\ldots =|t_d|=1
\end{equation*}
and
\begin{equation*}
\sqrt{v} \expe^{-\irm \tau \th_s} = \sum_{j=0}^d p_j(s)t_j,
\qquad \text{for}\ s=0,\ldots,d.
\end{equation*}
\end{prop}
\begin{proof}
It follows from Condition~\ref{Eqn_Ej1} that
$A(X)^k = \sum_{s=0}^d \theta_s^k E_s$, for $k\geq 0$.
Therefore,
\begin{equation}
\label{Eqn_PropIUMeqn}
\sqrt{v} \expe^{-\irm \tau A(X)} = \sqrt{v} \sum_{s=0}^d \expe^{-\irm \tau \th_s}E_s
\end{equation}
belongs to $\spn \cA$,
and there exists $t_0, \ldots, t_d$ such that
\begin{equation*}
\sqrt{v} \expe^{-\irm \tau A(X)} = \sum_{j=0}^d t_j A_j.
\end{equation*}
By Equation~\eqref{Eqn_Ej4}, we get
\begin{equation*}
\sqrt{v} \expe^{-\irm \tau \th_s} = \sum_{j=0}^d p_j(s)t_j,
\qquad \text{for}\ s=0,\ldots,d.
\end{equation*}
Lastly, $\sqrt{v} \expe^{-\irm \tau A(X)}$ is a complex Hadamard matrix
exactly when 
\begin{equation*}
|t_0|=\cdots=|t_d|=1.\qedhere
\end{equation*}
\end{proof}



For $n,q \geq 2$, 
the {\sl Hamming graph} $H(n,q)$ is the Cartesian product of $n$ copies of $K_q$.
Equivalently, the vertex set $V$ of the Hamming graph $H(n,q)$ is the set of words of length $n$
over an alphabet of size $q$, and two words are adjacent
if they differ in exactly one coordinate.
The Hamming graph is a distance regular graph on $q^n$ vertices with diameter $n$.
For $j=1,\ldots, n$, $X_j$ is the graph with vertex set $V$ where two
vertices are adjacent when they differ in exactly $j$ coordinates.
Let $A_0=I$ and $A_j=A(X_j)$, for $j=1,\ldots,n$.
Then $\cH(n,q)= \{A_0, A_1,\ldots, A_n\}$ is a symmetric association scheme, 
called the {\sl Hamming scheme}.
For more information on Hamming scheme, please see~\cite{MR1002568} and~\cite{arXiv:1011.1044}.

It follows from Equation~(4.1) of~\cite{arXiv:1011.1044} that
\begin{equation*}
\sum_{j=0}^n x^jA_j = [I_q+x(J_q-I_q)]^{\otimes n},
\end{equation*}
and the eigenvalues of $\cH(n,q)$ satisfy
\begin{equation}
\label{Eqn_KrawSum}
\sum_{j=0}^n p_j(s) x^j = \left(1+(q-1)x\right)^{n-s}(1-x)^s,
\quad \text{for $s=0,\ldots,n$.}
\end{equation}
Using $[x^k] g(x)$ to denote the coefficient of $x^k$ in a polynomial $g(x)$,
we have
for $r,s = 0,\ldots,n$,
\begin{equation}
\begin{aligned}[b]
p_r(s) &= [x^r] \left(1+(q-1)x\right)^{n-s}(1-x)^s\\
&=[x^r] \left(1+(q-1)x\right)^{n-s}\left((1+(q-1)x) -qx\right)^s\\
&=[x^r] \sum_{h} \binom{s}{h} \left(1+(q-1)x\right)^{n-h}(-qx)^h\\
&= \sum_{h}(-q)^h(q-1)^{r-h}\binom{n-h}{r-h}\binom{s}{h}.
\label{Eqn_Kraw2}
\end{aligned}
\end{equation}
We now quote the following characterization from~\cite{MR2047028} and~\cite{arXiv:0808.2382}.
\begin{theorem}
\label{Thm_Hamming}
The Hamming graph $H(n,q)$ admits \ium if and only if $q\in \{2,3,4\}$.
\end{theorem}

We see from Proposition~\ref{Prop_IUMeqn} that 
whether a graph $X$ admits \ium depends on only the spectrum of $X$ and the eigenvalues of the \BM algebra containing $A(X)$.
A {\sl Doob graph} $D(m_1,m_2)$ is a Cartesian product of $m_1$ copies
of the Shrikhande graph and $m_2$ copies of $K_4$. 
It is a distance regular graph with the same parameters as the Hamming graph $H(2m_1+m_2,4)$, see Section~9.2B of~\cite{MR1002568}.
Since \ium occurs in $H(n,4)$ for all $n\geq 1$, we see that the Doob graph $D(m_1,m_2)$ admits
\ium for all $m_1, m_2 \geq 1$.

\begin{coro}
The \BM algebra of $\cH(n,q)$ contains a complex Hadamard matrix if and only if $q\in \{2,3,4\}$.
\end{coro}
\begin{proof}
It follows from Equation~\eqref{Eqn_KrawSum} that
\begin{equation*}
p_r(n)= (-1)^r\binom{n}{r}.
\end{equation*}
By Proposition~\ref{Prop_NecComHad}, if the \BM algebra of $\cH(n,q)$ contains a complex Hadamard matrix, then 
\begin{equation*}
q^n \leq \left[\sum_{r=0}^n |p_r(n)| \right]^2= 4^n.
\end{equation*}
Hence $q \in \{2,3,4\}$.

The converse follows directly from Theorem~\ref{Thm_Hamming}.
\end{proof}

We conclude that 
if $A(X)$ belongs to the \BM algebra of $\cH(n,q)$, for $q\geq 5$, then
\ium does not occur in $X$.



\section{The Cubes}
\label{Section_Cubes}

The Hamming graph $H(n,2)$ is also called the {\sl $n$-cube}.
It is a distance regular graph on $2^n$ vertices
with intersection numbers 
\begin{equation*}
a_j=0, \quad b_j = (n-j) \quad \text{and}\quad c_j=j, \qquad\text{for $j=0,\ldots,n$}.
\end{equation*} 
It is both bipartite and antipodal, see Section~9.2 of~\cite{MR1002568} for details.

It follows from Equation~\eqref{Eqn_KrawSum} that the eigenvalues of $\cH(n,2)$ satisfy
\begin{equation}
\label{Eqn_pij}
p_r(n-s) = (-1)^rp_r(s) 
\qquad \text{and} \qquad
p_{n-r}(s) = (-1)^sp_r(s),
\end{equation}
for $r,s=0,\ldots,n$.

The proof of Lemma~\ref{Lem_Cube2} uses the following equations, which are Propositions~2.1(3) and~2.3 of~\cite{MR1028893}.
\begin{prop}\label{Prop_CS}
The eigenvalues of $\cH(n,2)$ satisfy
\begin{enumerate}[(a)]
\item
\label{Eqn_CS1}
$p_r(s+1)-p_r(s)=-p_{r-1}(s+1)-p_{r-1}(s)$, for $s= 0, \ldots, n-1$, $r = 1,\ldots, n$
and
\item
\label{Eqn_CS2}
$p_{r-1}(s)-p_{r-1}(s+2) = 4\sum_h (-2)^h\binom{n-2-h}{r-2-h}\binom{s}{h}$, for $s= 0, \ldots, n-2$ and $r = 1,\ldots, n$.
%\qed
\end{enumerate}

\end{prop}

Note that the Kronecker product of two complex Hadamard matrices is a complex Hadamard matrix.
Hence for $\e\in\{-1,1\}$, 
\begin{equation*}
\left[ I_2 + \e \irmbis(J_2-I_2) \right]^{\otimes n}
=\sum_{j=0}^n (\e \irmbis)^jA_j 
\end{equation*}
is a complex Hadamard matrix in the \BM algebra of $\cH(n,2)$.

Suppose $A(X)$ belongs to the \BM algebra of $\cH(n,2)$ and 
\begin{equation*}
A(X) E_s = \th_s E_s, \quad \text{for $s=0,\ldots,n$}.
\end{equation*}
It follows from Equations~\eqref{Eqn_PropIUMeqn} and~\eqref{Eqn_KrawSum} that
\begin{equation*}
\sqrt{2^n} \expe^{-\irm \tau A(X)} = \expe^{\irm \b} \left[ I_2 + \e \irmbis(J_2-I_2) \right]^{\otimes n}
\end{equation*}
if and only if
\begin{align*}
\sqrt{2^n}\expe^{-\irm \tau \th_s} &= \expe^{\irm \b} (1+\e \irmbis)^{n-s}(1-\e \irmbis)^s \\
&= \sqrt{2^n}\expe^{\irm \b}\expe^{\e \irm\pi(n-2s)/4},
\qquad\text{for $s=0,\ldots,n$}.
\end{align*}
This system of equations holds exactly when
\begin{equation*}
\expe^{\irm \b} = \expe^{-\irm \tau\th_0-\e \irm \pi n/4}
\end{equation*}
and
\begin{equation*}
\expe^{-\irm \tau(\th_s-\th_0)} = \expe^{-\e \irm \pi s/2},
\qquad
\text{for}\ s=0,\ldots,n.
\end{equation*}

\begin{lemma}
\label{Lem_Cube1}
Suppose $A(X)$ belongs to the \BM algebra of $\cH(n,2)$
and $A(X) E_s = \th_s E_s$, for $s=0,\ldots,n$.
If there exist $k$ and $\e \in \{-1,1\}$ satisfying
\begin{equation*}
\th_s -\th_0 \equiv \e s 2^{k-1} \mod{2^{k+1}},
\qquad \text{for}\ s=0,\ldots,n,
\end{equation*}
then 
there exists $\b \in \reals$ such that
\begin{equation*}
\sqrt{2^n}\expe^{-\irm \frac{\pi}{2^k} A(X)} = \expe^{\irm \b} [I_2+\e \irmbis (J_2-I_2)]^{\otimes n}.
\end{equation*}
That is,
$X$ admits \ium at time $\pi/2^{k}$.
%\qed
\end{lemma}


\begin{lemma}\label{Lem_Cube2}
Let $r\geq 1$.
Let $\alpha$ be the largest integer such that $\binom{n-1}{r-1}$ is divisible by $2^{\alpha}$.
Suppose 
\begin{equation*}
\binom{n-2-h}{r-2-h}\equiv0\pmod{2^{\alpha+1-h}}, 
\quad \text{for $h=0,\ldots, \alpha$.}
\end{equation*}
Then there exists $\b \in \reals$ such that
\begin{equation*}
\sqrt{2^n}\expe^{-\irm \frac{\pi}{2^{\a+2}} A_r} = \expe^{\irm \b} [I_2+\e \irmbis (J_2-I_2)]^{\otimes n},
\end{equation*}
where $\e \in \{-1, 1\}$ satisfies 
\begin{equation*}
\binom{n-1}{r-1} \equiv -\e 2^{\a} \pmod{2^{\a+2}}.
\end{equation*}
In particular, $X_r$ admits \ium at time $\pi/2^{\a+2}$.

Further, if $n$ is even and $r$ is odd, then there exists $\b' \in \reals$ such that
\begin{equation*}
\sqrt{2^n}\expe^{-\irm \frac{\pi}{2^{\a+2}} A_{n-r}} = \expe^{\irm \b'} [I_2+(-1)^{\frac{n+2}{2}} \e \irmbis (J_2-I_2)]^{\otimes n}.
\end{equation*}
In particular, $X_{n-r}$ admits \ium at time $\pi/2^{\a+2}$.
\end{lemma}
\begin{proof}
Since $2^{\a+3}$ divides the right-hand side of Proposition~\ref{Prop_CS}~\ref{Eqn_CS2}, we have
\begin{equation*}
p_{r-1}(s+2)\equiv p_{r-1}(s) \mod{2^{\a+3}},
\qquad \text{for}\ s=0,\ldots, n-2.
\end{equation*}
Applying this congruence repeatedly gives, for $s=0,\ldots,n-1$,
\begin{equation*}
-p_{r-1}(s+1)-p_{r-1}(s)\equiv -p_{r-1}(1)-p_{r-1}(0) \mod{2^{\a+3}}.
\end{equation*}
It follows from Equation~\eqref{Eqn_Kraw2} that $-p_{r-1}(1)-p_{r-1}(0) = -2\binom{n-1}{r-1}$, which is divisible by $2^{\a+1}$ but not by $2^{\a+2}$. 
Let $\e \in \{-1, 1\}$ satisfy
\begin{equation*}
\binom{n-1}{r-1} \equiv -\e 2^{\a} \pmod{2^{\a+2}}.
\end{equation*}
Then
\begin{equation*}
-p_{r-1}(1)-p_{r-1}(0)\equiv \e 2^{\a+1} \mod{2^{\a+3}}
\end{equation*}
and
\begin{equation*}
-p_{r-1}(s+1)-p_{r-1}(s)\equiv \e 2^{\a+1} \mod{2^{\a+3}},
\quad \text{for $s=0,\ldots,n-1$.}
\end{equation*}
By Proposition~\ref{Prop_CS}~\ref{Eqn_CS1}, we have
\begin{equation*}
p_r(s+1)-p_r(s) \equiv \e 2^{\a+1} \mod{2^{\a+3}}
\end{equation*}
and therefore 
\begin{equation}
\label{Eqn_Cube2a}
p_r(s)-p_r(0) \equiv \e s 2^{\a +1} \pmod{2^{\a+3}}, \quad \text{for $s=0,\ldots,n$.}
\end{equation}
By Lemma~\ref{Lem_Cube1}, 
\begin{equation*}
\sqrt{2^n}\expe^{-\irm \frac{\pi}{2^{\a+2}} A_r} = \expe^{\irm \b} [I_2+\e \irmbis (J_2-I_2)]^{\otimes n},
\end{equation*}
for some $\b \in \reals$, and $X_r$ admits \ium at time $\pi/2^{\a+2}$.

Suppose $n$ is even and $r$ is odd.
By Lemma~\ref{Lem_Cube1}, it suffices to show 
\begin{equation*}
p_{n-r}(s)-p_{n-r}(0) \equiv (-1)^{\frac{n+2}{2}}\e s2^{\a+1} \mod{2^{\a+3}},
\qquad \text{for}\ s=0,\ldots, n.
\end{equation*}

When $s$ is even, $2^{\a+2}$ divides $s2^{\a+1}$ and 
$(-1)^{(n+2)/2}\e s 2^{\a+1} \equiv \e s 2^{\a+1} \mod{2^{\a+3}}$.
Applying Equations~\eqref{Eqn_pij} and~\eqref{Eqn_Cube2a}, we have
\begin{align*}
p_{n-r}(s)-p_{n-r}(0) &= p_r(s)-p_r(0)\\
& \equiv (-1)^{\frac{n+2}{2}}\e s 2^{\a+1} \mod{2^{\a+3}}.
\end{align*}

When $s$ is odd, Equation~\eqref{Eqn_pij} gives
$p_{n-r}(s)-p_{n-r}(0) = -p_r(s)-p_r(0)$.
Applying Equations~\eqref{Eqn_Kraw2} and~\eqref{Eqn_Cube2a}, we get
\begin{equation}
p_r(1)-p_r(0) = \frac{-2r}{n}\binom{n}{r} 
\equiv \e 2^{\a+1} \mod{2^{\a+3}},
\label{Eqn_Lem_Cube2B}
\end{equation}
so $2^{\a+1}$ is the largest power of $2$ that divides $\frac{2r}{n}\binom{n}{r}$.

If $n\equiv 0 \mod{4}$, then $2^{\a+3}$ divides $2\binom{n}{r}=2p_r(0)$ and
\begin{align*}
p_{n-r}(s)-p_{n-r}(0) &= -[p_r(s)-p_r(0)]-2p_r(0)\\
&\equiv -[p_r(s)-p_r(0)] \mod{2^{\a+3}}\\
&\equiv (-1)^{\frac{n+2}{2}}\e s 2^{\a+1} \mod{2^{\a+3}}.
\end{align*}

Suppose $n \equiv 2 \mod{4}$. By Equation~\eqref{Eqn_Kraw2}, 
\begin{equation*}
2p_r(s) = \sum_j (-1)^j 2^{j+1} \binom{n-j}{r-j}\binom{s}{j}.
\end{equation*}
The hypothesis of this lemma ensures that $2^{\a+3}$ divides $2^{j+1} \binom{n-j}{r-j}\binom{s}{j}$ for $j\geq 2$.
Thus
\begin{equation*}
2p_r(s) \equiv 2\binom{n}{r}-2^2\binom{n-1}{r-1}s \mod{2^{\a+3}}.
\end{equation*}
We see from Equation~\eqref{Eqn_Lem_Cube2B} that
$2^{\a+1}$ is the highest power of $2$ that divides $\frac{2r}{n}\binom{n}{r}$.
Since $r$ is odd and $n \equiv 2 \mod{4}$, 
$2^{\a+1}$ is the largest power of $2$ that divides $\binom{n}{r}$.
Using our assumption on $\binom{n-1}{r-1}$, 
\begin{equation*}
2p_r(s) \equiv 2^{\a+2}(\g_1-\g_2) \mod{2^{\a+3}},
\end{equation*}
for some odd integers $\g_1$ and $\g_2$.
Therefore, $2p_r(s)$ is divisible by $2^{\a+3}$ and 
\begin{align*}
p_{n-r}(s) -p_{n-r}(0) 
&= [p_r(s) - p_r(0)] - 2p_r(s)\\
& \equiv (-1)^{\frac{n+2}{2}}\e s 2^{\a+1} \mod{2^{\a+3}}.
\end{align*}
By Lemma~\ref{Lem_Cube1}, there exists $\b' \in \reals$ such that
\begin{equation*}
\sqrt{2^n}\expe^{-\irm\frac{\pi}{2^{\a+2}} A_{n-r}} = \expe^{\irm \b'} [I_2+(-1)^{\frac{n+2}{2}} \e \irmbis (J_2-I_2)]^{\otimes n},
\end{equation*}
and \ium occurs in $X_{n-r}$ at time $2^{\a+2}$.
\end{proof}

To find the $n$'s and $r$'s that satisfy the condition in Lemma~\ref{Lem_Cube2},
we need the following results from number theory, due to Lucas and Kummer, respectively (see Chapter~IX of~\cite{MR0245499}).
\begin{theorem}
\label{Thm_Lucas}
Let $p$ be a prime.
Suppose the representation of $N$ and $M$ in base $p$ are $n_k\ldots n_1 n_0$ and $m_k\ldots m_1m_0$,
respectively.

Then
\begin{equation*}
\binom{N}{M} \equiv \binom{n_k}{m_k}\ldots\binom{n_0}{m_0} \mod{p}.
\end{equation*} 
%\qed
\end{theorem}
\begin{theorem}
\label{Thm_Kummer}
Let $p$ be a prime.
The largest integer $k$ such that $p^k$ divides $\binom{N}{M}$ is 
the number of carries in the addition of $N-M$ and $M$ in base $p$ representation.
%\qed
\end{theorem}


Let $2^{\a}$ be the highest power of $2$ that divides $\binom{n-1}{r-1}$.
That is, there are exactly $\a$ carries in the addition of $n-r$ and $r-1$ in base $2$ representation.
If both $n$ and $r$ are even, then no carry takes place in the right-most digit.
Therefore, there are exactly $\a$ carries in the addition of $n-r$ and $r-2$ in base $2$ representation.
Similarly, when $n$ is odd and $r$ is even, there
are exactly $\a-1$ carries in the addition of $n-r$ and $r-2$ in base $2$ representation.
In both cases, $2^{\a+1}$ does not divide $\binom{n-2}{r-2}$, 
so the hypothesis of Lemma~\ref{Lem_Cube2} does not hold when $r$ is even.

\begin{coro}\label{Cor_Cube1}
Suppose $n$ is even.
If $r$ is an odd positive integer with $1\leq r\leq n$, and 
\begin{equation*}
\binom{n-1}{r-1} \equiv 1 \pmod{2},
\end{equation*}
then there exist $\b, \b' \in \reals$ such that
\begin{equation*}
\sqrt{2^n}\expe^{-\irm \frac{\pi}{4} A_r} = \expe^{\irm \b} [I_2+\e \irmbis (J_2-I_2)]^{\otimes n}
\end{equation*}
and
\begin{equation*}
\sqrt{2^n}\expe^{-\irm \frac{\pi}{4} A_{n-r}} = \expe^{\irm \b'} [I_2+(-1)^{\frac{n+2}{2}} \e \irmbis (J_2-I_2)]^{\otimes n},
\end{equation*}
where $\e \in \{-1, 1\}$ satisfies
$\binom{n-1}{r-1} \equiv -\e \pmod{4}$.

In particular, 
$X_r$ and $X_{n-r}$ admit
\ium at time $\pi/4$.
\end{coro}
\begin{proof}
When $r=1$, we have $\binom{n-2}{r-2}=0$.
For $r\geq 3$, both $n-r$ and $r-2$ are odd, there is at least one carry (in the rightmost digit) in the addition of $n-r$ and $r-2$ in base $2$ representation.
By Theorem~\ref{Thm_Kummer}, $2$ divides $\binom{n-2}{r-2}$.
The result follows from applying Lemma~\ref{Lem_Cube2} with $\a=0$.
\end{proof}


\begin{coro}\label{Cor_Cube2}
Let $n=2^m(2 l+1)$, for integers $l \geq 0$ and $m\geq 1$.
For each odd $r$ satisfying $1\leq r < 2^m$,
there exist $\b, \b' \in \reals$ such that
\begin{equation*}
\sqrt{2^n}\expe^{-\irm \frac{\pi}{4} A_r} = \expe^{\irm \b} [I_2+\e \irmbis (J_2-I_2)]^{\otimes n}
\end{equation*}
and
\begin{equation*}
\sqrt{2^n}\expe^{-\irm \frac{\pi}{4} A_{n-r}} = \expe^{\irm \b'} [I_2+(-1)^{\frac{n+2}{2}} \e \irmbis (J_2-I_2)]^{\otimes n},
\end{equation*}
where $\e \in \{-1, 1\}$ satisfies
$\binom{n-1}{r-1} \equiv -\e \pmod{4}$.

In particular, 
$X_r$ and $X_{n-r}$ admit
\ium at time $\pi/4$.

\end{coro}

\begin{proof}
Let $r$ be an odd integer between $1$ and $2^m$.
In base $2$ representation, let $(n-1)$ and $(r-1)$ be $v_k\ldots v_0$ and $u_k\ldots u_0$, respectively.
Then 
$v_j=1$ for $j\leq m-1$ and $u_h=0$ for $h\geq m$, so $\binom{v_j}{u_j}=1$ for all $j$.
By Lucas' Theorem, we have
\begin{equation*}
\binom{n-1}{r-1} \equiv 1 \mod{2}.
\end{equation*}
The result follows from Corollary~\ref{Cor_Cube1}.
\end{proof}
 

We are now ready to 
show the existence of graphs that admit \ium earlier than time $\pi/4$.
\begin{theorem}
\label{Thm_Cube}
Let $n=2^{k+2}-8$, for some $k\geq 2$. For $j=1,3,5,7$,
there exists $\b_j \in \reals$ such that
\begin{equation}
\label{Eqn_Thm_Cube}
\sqrt{2^n}\expe^{-\irm \frac{\pi}{2^k} A_{(2^{k+1}-j)}} = \expe^{\irm \b_j} [I_2+\e_j \irmbis (J_2-I_2)]^{\otimes n},
\end{equation}
where $\e_j \in \{-1, 1\}$ satisfies
\begin{equation*}
\binom{n-1}{(2^{k+1}-j)-1} \equiv -\e_j 2^{k-2} \pmod{2^{k}}.
\end{equation*}
That is, $X_{2^{k+1}-1}$, $X_{2^{k+1}-3}$, $X_{2^{k+1}-5}$ and $X_{2^{k+1}-7}$ in $\cH(2^{k+2}-8,2)$ admit 
\ium at time $\pi/2^{k}$.
\end{theorem}

\begin{proof}
Let $n=2^{k+2}-8$ and $r=\frac{n}{2}-1$.
Then 
\begin{equation*}
n-r = 2^{k+1}-3 = 2^{k}+2^{k-1}+\cdots+1\cdot 2^3+1\cdot 2^2+0\cdot 2^1+1\cdot 2^0
\end{equation*}
and
\begin{equation*}
r-1 = 2^{k+1}-6 = 2^{k}+2^{k-1}+\cdots+1\cdot 2^3+0\cdot 2^2+1\cdot 2^1+0\cdot 2^0.
\end{equation*}
There are $(k-2)$ carries in the addition of $n-r$ and $r-1$ in base $2$ representation.
By Kummer's Theorem, the highest power of $2$ that divides $\binom{n-1}{r-1}$ is $2^{k-2}$.

We want to show that $2^{k-1-h}$ divides $\binom{n-2-h}{r-2-h}$, for $0 \leq h\leq k-2$.
When $h=0$,
\begin{equation*}
r-2 = 2^{k+1}-7 = 2^{k}+2^{k-1}+\cdots + 1\cdot 2^3+0\cdot 2^2+0\cdot 2^1+1\cdot 2^0,
\end{equation*}
so there are $(k-1)$ carries in the addition of $n-r$ and $r-2$ in base $2$ representation.
By Kummer's Theorem, $2^{k-1}$ divides $\binom{n-2}{r-2}$.

Similarly, there are $(k-2)$ carries in the addition of $n-r$ and $r-3$ in base $2$ representation, so
$2^{k-2}$ divides $\binom{n-3}{r-3}$.

As $h$ increments by 1, the number of $1$'s in the leftmost $(k-2)$ digits in the 
base $2$ representation of $r-2-h$ decreases by at most one. 
Hence there are at least $k-1-h$ carries in the addition of $n-r$ and $r-2-h$ in base $2$ representation,
and $2^{k-1-h}$ divides $\binom{n-2-h}{r-2-h}$, for $h=0,\ldots,k-2$.
 
Applying Lemma~\ref{Lem_Cube2} with $r=2^{k+1}-5$ and $\a=k-2$, Equation~\eqref{Eqn_Thm_Cube} holds for $j=5$ and $j=3$, and $X_{2^{k+1}-5}$ and $X_{2^{k+1}-3}$ admit \ium at time $\pi/{2^k}$.

A similar analysis shows that Equation~\eqref{Eqn_Thm_Cube} holds for $j=1$ and $j=7$, and \ium occurs in $X_{2^{k+1}-1}$ and $X_{2^{k+1}-7}$ at the same time.
\end{proof}



\section{Perfect State Transfer}

Let $u$ and $w$ be distinct vertices in $X$. 
We say that {\sl perfect state transfer} occurs from $u$ to $w$ in the continuous-time quantum walk on $X$ at time $\tau$ if
\begin{equation*}
|(\expe^{-\irm \tau A(X)})_{u,w}|=1.
\end{equation*}
We say that $X$ is {\sl periodic} at $u$ with period $\tau$ if
\begin{equation*}
|(\expe^{-\irm \tau A(X)})_{u,u}|=1.
\end{equation*}
If $A(X)$ belongs to the \BM algebra of an association scheme $\cA$ and $X$ is periodic at some vertex $u$, then
$X$ is periodic at every vertex because $I\in \cA$. In this case, we simply say that $X$ is {\sl periodic}.

Consider $X_r$ in the Hamming scheme $\cH(2^m,2)$ when $r$ is odd.
We see from the proof of Corollary~\ref{Cor_Cube2} that
$\binom{2^m-1}{r-1}$ is odd. It follows from Theorem~2.3 of
\cite{MR2811131} that perfect state transfer occurs in $X_r$ at time $\pi/2$.
Moreover, let $1\leq r' \leq 2^m$ be an odd integer distinct from $r$, then
the graph $X_r \cup X_{r'}$ is periodic with period $\pi/2$.


Let $X$ be one of the graphs considered in Corollary~\ref{Cor_Cube2} or
Theorem~\ref{Thm_Cube}. At the time $\tau$ of \ium in $X$, we have
\begin{equation*}
\expe^{-\irm \tau A(X)} = \frac{\expe^{\irm \beta}}{\sqrt{2^n}}
\begin{pmatrix}
1 & \e \irmbis\\
\e \irmbis & 1
\end{pmatrix}^{\otimes n},
\qquad \text{for some $\beta \in \reals$ and $\e \in \{-1,1\}$}.
\end{equation*}
Observe that, for $\e, \e' \in \{-1,1\}$,
\begin{equation}
\label{Eqn_PST1}
\begin{pmatrix}
1 & \e \irmbis\\
\e \irmbis & 1
\end{pmatrix}\begin{pmatrix}
1 & \e' i\\
\e' \irmbis & 1
\end{pmatrix}
=
\begin{cases}
2\begin{pmatrix}
0&\e \irmbis\\\e \irmbis&0
\end{pmatrix}
& \text{if $\e=\e'$},\\
2\begin{pmatrix}
1&0\\0&1
\end{pmatrix}
& \text{if $\e\not=\e'$}.\\
\end{cases}
\end{equation}
We see that 
\begin{equation*}
\expe^{-\irm 2 \tau A(X)} 
= \expe^{2\beta \irm} 
\begin{pmatrix}
0&\e \irmbis\\\e \irmbis&0
\end{pmatrix}^{\otimes n},
\end{equation*}
and $X$ has perfect state transfer at time $2\tau$.

We generalize the above observation by applying Equation~\eqref{Eqn_PST1} to the union of two graphs in $\cH(n,2)$.
\begin{lemma}
\label{Lem_IUM_PST}
Let $X$ and $X'$ be graphs in $\cH(n,2)$ such that $E(X) \cap E(X')=\emptyset$,\
and there exist $\beta, \beta' \in \reals$ and $\e, \e' \in \{-1, 1\}$ such that
\begin{equation*}
\expe^{-\irm \tau A(X)} = \frac{\expe^{\irm \beta}}{\sqrt{2^n}}
\begin{pmatrix}
1 & \e \irmbis\\
\e \irmbis & 1
\end{pmatrix}^{\otimes n}
\quad \text{and} \quad
\expe^{-\irm \tau A(X')}= \frac{\expe^{\irm \beta'}}{\sqrt{2^n}}
\begin{pmatrix}
1 & \e' \irmbis\\
\e' \irmbis & 1
\end{pmatrix}^{\otimes n}.
\end{equation*}
If $\e = \e'$ 
then $X \cup X'$ has perfect state transfer at time $\tau$. Otherwise, $X \cup X'$ is periodic at time $\tau$.
\end{lemma}
\begin{proof}
As $A(X)$ and $A(X')$ commute, it follows from Equation~\eqref{Eqn_PST1} that
\begin{equation*}
\expe^{-\irm \tau A(X\cup X')} = \expe^{-\irm \tau A(X)} \expe^{-\irm \tau A(X')} 
=
\begin{cases}
 \expe^{(\beta +\beta') \irm} 
\begin{pmatrix}
0&\e \irmbis\\\e \irmbis&0
\end{pmatrix}^{\otimes n} 
& \text{if $\e=\e'$,}\\
\expe^{(\beta +\beta') \irm} I_{2^n} & \text{otherwise}.
\end{cases}
\end{equation*}
\end{proof}


With the help of the following result in number theory, Theorem~1 of~\cite{MR1910963}, we find graphs in $\cH(2^m, 2)$
and $\cH(2^{k+2}-8,2)$ that have perfect state transfer earlier than $\pi/2$.

\begin{theorem}
\label{Thm_CG}
Let $p$ be prime, $n$ and $k$ be positive integers. If $p^k$ divides $n$ then
\begin{equation*}
\binom{n-1}{s} \equiv (-1)^{s- \lfloor s/p\rfloor} \binom{n/p-1}{\lfloor s/p \rfloor} \mod{p^k},
\end{equation*}
for $s=0,\ldots,n-1$.
%\qed
\end{theorem}

\begin{prop}
\label{Prop_PST1}
For $m\geq 3$, and for odd integers $r$ and $r'$ satisfying
\begin{equation}
\label{Cond_PST1}
1\leq r<r' < 2^{m-1} \qquad \text{or} \qquad 2^{m-1} < r < r' <2^m,
\end{equation}
perfect state transfer occurs in the graph $X_r \cup X_{r'}$ of $\cH(2^m,2)$ at time $\pi/4$.
\end{prop}
\begin{proof}
Let $r$ be an odd integer between $2^b$ and $2^{b+1}$ for some $b\leq m-1$.
Let $s_0=r-1$ and $s_i=\lfloor s_{i-1}/2\rfloor$, for $i=1,\ldots, b$.
Let $n=2^m$. Applying Theorem~\ref{Thm_CG} repeatedly gives
\begin{equation*}
\binom{n-1}{r-1} \equiv (-1)^{s_0-s_i}\binom{2^{m-i}-1}{s_i} \mod{2^{m-i+1}},
\qquad \text{for $1\leq i \leq b$}.
\end{equation*}
Since $s_b=1$ and $m-b+1\geq 2$, applying the above equation with $i=b$ yields
\begin{equation*}
\binom{n-1}{r-1} 
 \equiv (-1)^{r-2}(2^{m-b}-1) \mod{4}.
\end{equation*}
If $r<2^{m-1}$, we have $b\leq m-2$ and
\begin{equation*}
\binom{n-1}{r-1} \equiv 1 \mod{4}.
\end{equation*}
If $2^{m-1}<r $, we have $b=m-1$ and 
\begin{equation*}
\binom{n-1}{r-1} \equiv -1 \mod{4}.
\end{equation*}

It follows from Corollary~\ref{Cor_Cube2} that there exist $\b, \b' \in \reals$ such that
\begin{equation*}
\expe^{-\irm \frac{\pi}{4} A_r} = \frac{\expe^{\irm \beta}}{\sqrt{2^n}}
\begin{pmatrix}
1 & \e \irmbis\\
\e \irmbis & 1
\end{pmatrix}^{\otimes n}
\quad \text{and} \quad
\expe^{-\irm \frac{\pi}{4} A_{r'}}= \frac{\expe^{\irm \beta'}}{\sqrt{2^n}}
\begin{pmatrix}
1 & \e \irmbis\\
\e \irmbis & 1
\end{pmatrix}^{\otimes n},
\end{equation*}
where 
\begin{equation*}
\e=
\begin{cases}
-1 & \text{if $r$ and $r'$ are odd integers between $1$ and $2^{m-1}$,}\\
1 & \text{if $r$ and $r'$ are odd integers between $2^{m-1}$ and $2^{m}$.}
\end{cases}
\end{equation*}
By Lemma~\ref{Lem_IUM_PST}, perfect state transfer occurs in $X_r \cup X_{r'}$ at time $\frac{\pi}{4}$.
\end{proof}

\begin{prop}
\label{Prop_PST2}
For integer $k\geq 2$, perfect state transfer occurs in graphs 
\begin{equation*}
X_{2^{k+1}-5}\cup X_{2^{k+1}-7}
\quad \text{and} \quad
X_{2^{k+1}-1}\cup X_{2^{k+1}-3}
\end{equation*} 
of $\cH(2^{k+2}-8,2)$ at time $\pi/2^k$.
\end{prop}

\begin{proof}
Let $n=2^{k+2}-8$ and $m=\frac{n}{8}$.
Let $\e_1, \e_3, \e_5, \e_7$ be the integers defined in Theorem~\ref{Thm_Cube}.

Consider $4m-1=2^{k+1}-5 $ and $4m-3=2^{k+1}-7$.
From
\begin{equation*}
\binom{8m-1}{4m-4} = \left[1-4\frac{5m}{(4m+3)(2m+1)}\right] \binom{8m-1}{4m-2},
\end{equation*}
we get
\begin{align*}
\binom{n-1}{(2^{k+1}-7)-1} 
&= \left[1-4\frac{5m}{(4m+3)(2m+1)}\right] \binom{n-1}{(2^{k+1}-5)-1}\\
&\equiv \left[1-4\frac{5m}{(4m+3)(2m+1)}\right] (-\e_5 2^{k-2}) \pmod{2^k}.
\end{align*}
Since $4m+3$ and $2m+1$ are coprime with $2^{k}$, we have
\begin{equation*}
\binom{n-1}{(2^{k+1}-7)-1}\equiv -\e_5 2^{k-2} \pmod{2^k},
\end{equation*}
and $\e_7=\e_5$.
It follows from Theorem~\ref{Thm_Cube} and Lemma~\ref{Lem_IUM_PST} that perfect state transfer occurs in $X_{2^{k+1}-5}\cup X_{2^{k+1}-7}$ at time $\pi/2^k$.


For $X_{2^{k+1}-3}$ and $X_{2^{k+1}-1}$, we have $4m+1=2^{k+1}-3$ and $4m+3=2^{k+1}-1$.
From 
\begin{equation*}
 \binom{8m-1}{4m+2} = \left[1-4\frac{3m}{(4m+1)(2m+1)}\right] \binom{8m-1}{4m},
\end{equation*}
we have
\begin{align*}
\binom{n-1}{(2^{k+1}-1)-1} 
&= \left[1-4\frac{3m}{(4m+1)(2m+1)}\right]\binom{n-1}{(2^{k+1}-3)-1}\\
&\equiv \left[1-4\frac{3m}{(4m+1)(2m+1)}\right] (-\e_3 2^{k-2}) \pmod{2^k}.
\end{align*}
Since $4m+1$ and $2m+1$ are coprime with $2^{k}$, we have
\begin{equation*}
\binom{n-1}{(2^{k+1}-1)-1}\equiv -\e_3 2^{k-2} \pmod{2^k},
\end{equation*}
and $\e_1=\e_3$.
It follows from Theorem~\ref{Thm_Cube} and Lemma~\ref{Lem_IUM_PST} that perfect state transfer occurs in $X_{2^{k+1}-1}\cup X_{2^{k+1}-3}$ at time $\pi/2^k$.
\end{proof}



\section{Halved \texorpdfstring{$n$}{n}-Cube}
The $n$-cube $X$ is a connected bipartite graph of diameter $n$.
When $n\geq 2$, $X_2$ has two components, one of which has the set $\cE$ of binary words 
of even weights as its vertex set.
The {\sl halved $n$-cube}, denoted by $\hX$, is the subgraph of $X_2$ induced by $\cE$.
It is a distance regular graph on $2^{n-1}$ vertices with diameter $\lfloor \frac{n}{2}\rfloor$.
The intersection numbers of $\hX$ are
\begin{equation*}
\widehat{a}_j=2j(n-2j), \quad \widehat{b}_j = \frac{(n-2j)(n-2j-1)}{2}
\quad \text{and}\quad
\widehat{c}_j = j(2j-1),
\end{equation*}
for $j=0,\ldots, \lfloor \frac{n}{2}\rfloor$,
and the eigenvalues of $\hX$ are $p_2(0),p_2(1),\ldots, p_2(\lfloor n/2\rfloor)$.

Let $\widehat{\cA}=\{I,\hA_1, \ldots,\hA_{\lfloor n/2\rfloor}\}$
where $\hA_r= A(\hX_r)$.
We use $\hp_r(s)$ to denote the eigenvalues of $\widehat{\cA}$ and let $\hp_{-1}(s)=0$.
Equation~(11) on page~128 of~\cite{MR1002568} states that, 
for $r,s = 0,\ldots,\lfloor n/2\rfloor$,
\begin{equation*}
\hp_1(s) \hp_{r}(s) = \widehat{c}_{r+1} \hp_{r+1}(s) + \widehat{a}_r \hp_{r}(s) +\widehat{b}_{r-1}\hp_{r-1}(s).
\end{equation*}
It is straightforward to verify that $\hp_r(s)=p_{2r}(s)$ satisfies these recursions,
so the eigenvalues of $\widehat{\cA}$ are
\begin{equation}
\label{Eqn_Halvedpij}
\hp_r(s) = p_{2r}(s),
\qquad \text{for}\ r,s=0,\ldots,\lfloor \frac{n}{2}\rfloor.
\end{equation}
For more information on the halved $n$-cube, please see Sections~4.2 and 9.2D of~\cite{MR1002568}.

When $n=2m+1$, Equation~\eqref{Eqn_KrawSum} yields
\begin{equation*}
\sum_{h=0}^n p_h(s) i^h = (1+i)^{2m+1-s}(1-i)^s = 2^mi^{m-s}(1+i),
\qquad \text{for}\ s=0,\ldots,n.
\end{equation*}
The real part of this sum is
\begin{equation}
\begin{aligned}[t]
\label{Eqn_RealPart}
\sum_{r=0}^m p_{2r}(s) (-1)^r &= \sum_{r=0}^m \hp_{r}(s) (-1)^r\\
&=\begin{cases}
2^m & \text{if $m-s\equiv 0 \mod{4}$ or $m-s\equiv 3 \mod{4}$},\\ 
-2^m & \text{otherwise}.
\end{cases}
\end{aligned}
 \end{equation}
By Proposition~\ref{Prop_TypeII}, $\sum_{r=0}^m (-1)^r \hA_r$ is a (complex) Hadamard matrix.

\begin{theorem}
For $n \geq 3$, the adjacency algebra of the halved $n$-cube contains a complex Hadamard
matrix if and only if $n$ is odd.
\end{theorem}

\begin{proof}
Suppose $n=2m$.
Using Proposition~\ref{Prop_NecComHad}, it is sufficient to show that 
\begin{equation*}
\left[\sum_{r=0}^m |\hp_r(m-1)|\right]^2 < 2^{2m-1},
\qquad \text{for}\ m\geq 2.
\end{equation*}


It follows from Equations~\eqref{Eqn_KrawSum} and~\eqref{Eqn_Halvedpij} that for $r \geq 0$,
\begin{align*}
\hp_r(m-1) 
&= [x^{2r}] (1+x)^{m+1}(1-x)^{m-1} \\
&= [x^{2r}](1+2x+x^2)(1-x^2)^{m-1} \\
&= (-1)^r \left[ \binom{m-1}{r} - \binom{m-1}{r-1}\right].
\end{align*}
Hence
\begin{equation*}
|\hp_r(m-1)| = 
\begin{cases}
\binom{m-1}{r} -\binom{m-1}{r-1} & \text{if $0\leq r \leq \frac{m}{2}$}\\
\binom{m-1}{r-1}-\binom{m-1}{r} & \text{if $\frac{m}{2} < r \leq m$}
\end{cases}
\end{equation*}
and
\[
\begin{aligned}
\sum_{r=0}^m |\hp_r(m-1)|%\\
&= \sum_{r=0}^{\lfloor\frac{m}{2} \rfloor}\left[\binom{m-1}{r}-\binom{m-1}{r-1}\right]
+\sum_{r=\lfloor\frac{m}{2}\rfloor+1}^m \left[\binom{m-1}{r-1}-\binom{m-1}{r}\right]\\
&=2\binom{m-1}{\lfloor\frac{m}{2}\rfloor}.
\end{aligned}
\]
A simple mathematical induction on $m$ shows that 
$4\binom{m-1}{\lfloor \frac{m}{2} \rfloor}^2 < 2^{2m-1}$, 
for $m\geq 2$.

When $n$ is odd, $\sum_{r=0}^m (-1)^r\hA_r$ is a complex Hadamard matrix.
\end{proof}



\begin{theorem}\label{Thm_HalvedIUM}
For $n \geq 3$, the halved $n$-cube admits \ium if and only if $n$ is odd.
\end{theorem}

\begin{proof}
From the above theorem, the halved $n$-cube does not admit \ium 
when $n\geq 4$ is even.

Suppose $n=2m+1$ and $\expe^{-2\irm\tau}\in \{-i, i\}$.
For $s=0,\ldots,m$, we have 
\begin{equation*}
\hp_1(s)=2(m-s)(m-s+1)-m
\end{equation*}
and
\begin{align*}
\expe^{-\irm \tau\hp_1(s)}
&=
(\expe^{-2\irm\tau})^{(m-s)(m-s+1)} \expe^{\irm \tau m}\\
&= 
\begin{cases}
\expe^{\irm \tau m} & \text{if $m-s\equiv 0 \mod{4}$ or $m-s\equiv 3 \mod{4}$},\\ 
-\expe^{\irm \tau m} & \text{otherwise}.
\end{cases}
\end{align*}
We see from Equation~\eqref{Eqn_RealPart} that
\begin{equation*}
2^m \expe^{-\irm \tau\hp_1(s)} = \expe^{\irm \tau m}\sum_{r=0}^m (-1)^r \hp_r(s),
\qquad \text{for}\ s=0,\ldots,m.
\end{equation*}
Since $|\expe^{\irm \tau m}(-1)^r|=1$, it follows from 
Proposition~\ref{Prop_IUMeqn} that $\hX_1$ admits \ium at time $\frac{\pi}{4}$.
\end{proof}

The halved $2$-cube is the complete graph on two vertices and it admits \ium (see~\cite{MR2023606}).

When $n\geq 3$, the halved $n$-cube is isomorphic to the cubelike graph of $\ints_2^{n-1}$ with connection set 
\begin{equation*}
C=\left\{\mathbf{a} : \text{weight of $\mathbf{a}$ is $1$ or $2$}\right\}.
\end{equation*}
Applying Theorem~2.3 of~\cite{MR2811131} to the halved $n$-cube with even $n$, we see that perfect state
transfer occurs from $\mathbf{a}$ to $\mathbf{a} \oplus \one$ at time $\pi/2$. But this graph does not have instantaneous uniform mixing.



\section{Folded \texorpdfstring{$n$}{n}-Cube}
Let $\G$ be a distance regular graph on $v$ vertices with diameter $d$ and 
intersection array $\{b_0, b_1, \ldots, b_{d-1}; c_1, \ldots,c_d\}$.
We say $\G$ is {\sl antipodal} if $\G_d$ is a union of complete graph $K_R$'s, for some fixed $R$.
The vertex sets of the $K_R$'s in $\G_d$ form an equitable partition $\cP$ of $\G$
and the quotient graph of $\G$ with respect to $\cP$ is called
the {\sl folded graph} $\fG$ of $\G$.
When $d>2$,
$\fG$ is a distance regular graph on $\frac{v}{R}$ vertices with diameter $\lfloor \frac{d}{2}\rfloor$,
see Proposition~4.2.2~(ii) of~\cite{MR1002568}.
Moreover $\fG$ has intersection numbers $\fa_j=a_j$, $\fb_j=b_j$ and 
$\fc_j=c_j$ for $j=0,\ldots \lfloor \frac{d}{2}\rfloor-1$ and
\begin{equation*}
\fc_{\lfloor \frac{d}{2}\rfloor} = 
\begin{cases}
c_{\lfloor \frac{d}{2}\rfloor} & \text{if $d$ is odd},\\
R c_{\frac{d}{2}} & \text{if $d$ is even.}
\end{cases}
\end{equation*}
From Proposition~4.2.3~(ii) of~\cite{MR1002568}, we see that if the eigenvalues of $\G$ are 
$p_1(0)\geq p_1(1)\geq \ldots\geq p_1(d)$,
then $\fG$ has eigenvalues $\fp_1(j)=p_1(2j)$ for $j=0,\ldots,\lfloor \frac{d}{2}\rfloor$.
The eigenvalues for $\fA_j$'s and $A_j$'s satisfy the same recursive relation (Equation~(11) on Page~128 of~\cite{MR1002568}) 
for $j=0,\ldots, \lfloor \frac{d}{2}\rfloor$ when $d$ is odd and
for $j=0,\ldots, \frac{d}{2}-1$ when $d$ is even.
When $d$ is even, $\fp_{\frac{d}{2}}(s) = \frac{1}{R}p_{\frac{d}{2}}(2s)$.
Therefore 
\begin{equation}
\label{Eqn_Foldedpij}
\fp_r(s) = 
\begin{cases}
p_r(2s) & \text{if $0\leq r < \lfloor \frac{d}{2}\rfloor$},\\
p_{\lfloor \frac{d}{2}\rfloor}(2s) & \text{if $d$ is odd and $r={\lfloor \frac{d}{2}\rfloor}$},\\
\frac{1}{R}p_{\frac{d}{2}}(2s) & \text{if $d$ is even and $r={\frac{d}{2}}$}.
\end{cases}
\end{equation}

For each vertex $\mathbf{a}$ in the $n$-cube $X$, $\one \oplus \mathbf{a}$ is the unique vertex at distance $n$ from $\mathbf{a}$.
Therefore $X_n$ is a union of $K_2$'s. 
The {\sl folded $n$-cube} $\fX$ has $2^{n-1}$ vertices, diameter $\lfloor \frac{n}{2} \rfloor$, and eigenvalues
\begin{equation}
\label{Eqn_Foldedn}
\fp_r(s) = 
\begin{cases}
[x^r](1+x)^{n-2s}(1-x)^{2s} & \text{if $0\leq r < \lfloor \frac{n}{2}\rfloor$},\\
[x^{\lfloor \frac{n}{2}\rfloor}](1+x)^{n-2s}(1-x)^{2s} & \text{if $n$ is odd and $r={\lfloor \frac{n}{2}\rfloor}$},\\
[x^{\frac{n}{2}}]\frac{1}{2}(1+x)^{n-2s}(1-x)^{2s} & \text{if $n$ is even and $r={\frac{n}{2}}$}.
\end{cases}
\end{equation}

The folded $n$-cube is isomorphic to the graph obtained from an $(n-1)$-cube by adding the perfect matching in which a vertex $\mathbf{a}$ is
adjacent to $\one \oplus \mathbf{a}$.
Best et al. proved the following result, see Theorem~1 of~\cite{arXiv:0808.2382}.
\begin{theorem}
For $n \geq 3$, the folded $n$-cube admits \ium if and only if $n$ is odd.
%\qed
\end{theorem}
In particular, the adjacency algebra of the folded $n$-cube contains a complex Hadamard matrix when $n$ is odd.
\begin{theorem}
For $n \geq 3$, the adjacency algebra of the folded $n$-cube contains a complex Hadamard
matrix if and only if $n$ is odd.
\end{theorem}

\begin{proof}
Suppose $n=4m$, for some $m\geq 1$.
We have, for $r=0,\ldots, 2m-1$, 
\begin{align*}
\fp_r(m) 
&= [x^r](1+x)^{2m}(1-x)^{2m}\\
&= 
\begin{cases}
(-1)^{\frac{r}{2}}\binom{2m}{\frac{r}{2}} & \text{if $r$ is even,}\\
0 & \text{otherwise}
\end{cases}
\end{align*}
and
\begin{equation*}
\fp_{2m}(m) = (-1)^m\frac{1}{2}\binom{2m}{m}.
\end{equation*}
Now
\begin{align*}
\sum_{r=0}^{2m} |\fp_r(m)|
&= \sum_{r=0}^{m-1} \binom{2m}{r} + \frac{1}{2}\binom{2m}{m}\\
&= \frac{1}{2}\left[ \sum_{r=0}^{2m} \binom{2m}{r}\right]\\
&= 2^{2m-1}.
\end{align*}
We have $\left[\sum_{s=0}^{2m} |\fp_s(m)| \right]^2 < 2^{4m-1}$.
By Proposition~\ref{Prop_NecComHad}, the adjacency algebra of the folded $4m$-cube does not contain
a complex Hadamard matrix.

Suppose $n=4m+2$.
By Equation~\eqref{Eqn_Foldedn},
\[
\fp_r(m) 
=
\begin{cases}
1 & \text{if $r=0$,}\\
(-1)^{\lfloor \frac{r}{2}\rfloor}2 \binom{2m}{\lfloor \frac{r}{2}\rfloor} & \text{if $1\leq r< 2m$ is odd,}\\
(-1)^{\frac{r}{2}}\left[ \binom{2m}{\frac{r}{2}} - \binom{2m}{\frac{r}{2}-1}\right] & \text{if $2 \leq r\leq 2m$ is even,}\\
(-1)^m\binom{2m}{m} & \text{if $r=2m+1$.}
\end{cases}
\]
Now
\begin{align*}
\sum_{s=0}^{2m+1} |\fp_s(m)|
&= 1+\sum_{r=0}^{m-1} 2 \binom{2m}{r}+\sum_{r=1}^{m}\left[\binom{2m}{r}-\binom{2m}{r-1}\right]+\binom{2m}{m}\\
&= 2^{2m}+\binom{2m}{m}.
\end{align*}
A simple mathematical induction on $m$ shows that $\left[2^{2m}+\binom{2m}{m}\right]^2 < 2^{4m+1}$, for all integer $m\geq 2$.
We conclude that the adjacency algebra of the folded $(4m+2)$-cube does not contain
a complex Hadamard matrix, for $m\geq 2$.

The folded $6$-cube has eigenvalues
\begin{align*}
p_0(1)&=p_0(2)=1, &	 &&p_1(1)&=-p_1(2)=2,\\
p_2(1)&=p_2(2)=-1 & \text{and} &&p_3(1)&=-p_3(2)=-2.
\end{align*}
Let $W=\sum_{j=0}^3 t_j\fA_j$ be a type II matrix.
Adding the equations in Proposition~\ref{Prop_TypeII} for $s=1$ and $s=2$ gives
\begin{equation*}
-\left(\frac{t_0}{t_2}+\frac{t_2}{t_0}\right) - 4 \left(\frac{t_1}{t_3}+\frac{t_3}{t_1}\right)=22.
\end{equation*}
The left-hand side is at most ten if $|t_0|=|t_1|=|t_2|=|t_3|=1$.
Therefore, the adjacency algebra of the folded $6$-cube does not contain a complex Hadamard matrix.
\end{proof}

The folded $2$-cube is the complete graph on two vertices and it admits \ium (see~\cite{MR2023606}).



\section{Folded Halved \texorpdfstring{$2m$}{2m}-Cube}
According to Page~141 of~\cite{MR1002568}, the halved $2m$-cube $\hX$ is antipodal with antipodal classes of size two
and the folded $2m$-cube $\fX$ is bipartite for $m\geq 2$.
In addition, the folded graph of $\hX$ is isomorphic to the halved graph of $\fX$.
We use $\fhX$ to denoted the folded graph of $\hX$ which is a distance regular graph on
$2^{2m-2}$ vertices with diameter $\lfloor \frac{m}{2} \rfloor$.
Let $\cA_r=A(\fhX_r)$, for $r=0,\ldots,\lfloor \frac{m}{2}\rfloor$. 

By Equations~\eqref{Eqn_Halvedpij} and~\eqref{Eqn_Foldedpij}, the eigenvalues of the folded halved $2m$-cube are
\begin{equation}
\label{Eqn_FHpij}
\fhp_r(s) = 
\begin{cases}
p_{2r}(2s) & \text{if $0\leq r < \lfloor \frac{m}{2}\rfloor$},\\
p_{2\lfloor \frac{m}{2}\rfloor}(2s) & \text{if $m$ is odd and $r={\lfloor \frac{m}{2}\rfloor}$},\\
\frac{1}{2}p_{m}(2s) & \text{if $m$ is even and $r=\frac{m}{2}$}.
\end{cases}
\end{equation}



\begin{theorem}
The adjacency algebra of the folded halved $2m$-cube contains a complex Hadamard
matrix if and only if $m$ is even.
\end{theorem}

\begin{proof}
Suppose $m=2u+1$. Then
\begin{align*}
\fhp_r(u) 
&= [x^{2r}](1+2x+x^2)(1-x^2)^{2u}\\
&=
\begin{cases}
1 & \text{if $r=0$}\\
(-1)^r\binom{2u}{r}+(-1)^{r-1}\binom{2u}{r-1} & \text{if $1\leq r\leq u$.}
\end{cases}
\end{align*}
Then
\begin{equation*}
\sum_{r=0}^u |\fhp_r(u)| = 1+\sum_{r=1}^u \left[\binom{2u}{r}-\binom{2u}{r-1}\right]=\binom{2u}{u}.
\end{equation*}
Hence
\begin{equation*}
\left[\sum_{r=0}^u |\fhp_r(u)|\right]^2 < \left[\sum_{r=0}^{2u}\binom{2u}{r}\right]^2 = 2^{4u}.
\end{equation*}
By Proposition~\ref{Prop_NecComHad}, the adjacency algebra of the folded halved $(4u+2)$-cube 
does not contain a complex Hadamard matrix.

Suppose $m=2u$.
By Equations~\eqref{Eqn_FHpij} and~\eqref{Eqn_pij}, 
\[
\begin{aligned}
\sum_{r=0}^u (-1)^r \fhp_r(s)%\\
&= \sum_{r=0}^{u-1}(-1)^rp_{2r}(2s) + \frac{1}{2}(-1)^u p_{2u}(2s)\\
&= \frac{1}{2}\sum_{r=0}^{u-1}(-1)^rp_{2r}(2s) + \frac{1}{2}(-1)^u p_{2u}(2s) +
\frac{1}{2}\sum_{r=0}^{u-1}(-1)^r (-1)^{2s} p_{4u-2r}(2s)\\
&= \frac{1}{2} \sum_{r=0}^{2u}(-1)^rp_{2r}(2s),
\end{aligned}
\]
which is equal to the real part of $\frac{1}{2}\sum_{j=0}^{4u} i^j p_j(2s)$. 
By Equation~\eqref{Eqn_KrawSum},
\begin{equation}
\label{Eqn_FHeven}
\frac{1}{2}\sum_{j=0}^{4u} i^j p_j(2s)= \frac{1}{2} (1+i)^{4u-2s}(1-i)^{2s}=(-1)^{u-s}2^{2u-1}.
\end{equation}
By Proposition~\ref{Prop_TypeII}, $\sum_{s=0}^u (-1)^s \fhA_s$ is a complex Hadamard matrix.
\end{proof}



\begin{theorem}
The folded halved $2m$-cube admits \ium if and only if $m$ is even.
\end{theorem}

\begin{proof}
Suppose $m=2u$ and $\expe^{-8\irm\tau}=-1$.
For $s=0,\ldots,u$, 
\begin{equation*}
\fhp_1(s) = 8(u-s)^2-2u
\end{equation*}
and
\begin{equation*}
2^{2u-1}\expe^{-\irm \tau\fhp_1(s)}
= 2^{2u-1}(-1)^{(u-s)^2}\expe^{2\irm u\tau},
\end{equation*}
which is equal to $\expe^{2\irm u\tau}\sum_{r=0}^u (-1)^r \fhp_r(s)$ from Equation~\eqref{Eqn_FHeven}.
By Proposition~\ref{Prop_IUMeqn}, the folded halved $4u$-cube admits \ium at time $\pi/8$.
\end{proof}

 
\longthanks{The author would like to thank Chris Godsil, Natalie Mullin and Aidan Roy for many interesting discussions. The author is grateful for Akihiro Munemasa's advice on the exposition.}


%\nocite{*}
\bibliographystyle{amsplain-ac}
\bibliography{ALCO_Chan_332}
\end{document}