## Introduction

Let $H$ be an $n\times n$ symmetric integer matrix. We can view $H$ as the adjacency matrix of a weighted graph $X$ on $n$ vertices. A *quantum walk* on $X$ is determined the transition matrix
\[
U(t) = \exp(itH).
\]
An important phenomenon in quantum walks is *perfect state transfer* from vertex $u$ to vertex $v$, that is,
\[
U(\tau)e_u = \gamma e_v
\]
for some time $\tau$, and some complex number $\gamma$ called the *phase factor*. Since $U(t)$ is unitary, the phase factor must have absolute value one. It is not hard to see that if there is perfect state transfer from $u$ to $v$ at time $\tau$, then there is perfect state transfer from $v$ to $u$ at the same time, with the same phase factor. Therefore,
\[U(2\tau)e_u = \gamma U(\tau) e_b = \gamma^2 e_u\]
and the quantum walk returns to $u$ at time $2\tau$.

Formally, if for some time $\tau$ and some complex number $\gamma$ we have
\[U(\tau) e_u = \gamma e_u\]
then we say $u$ is *periodic* with period $\tau$. If perfect state transfer occurs between $u$ and $v$, then a necessary condition is that both $u$ and $v$ are periodic. Thus it helps to know how common periodic vertices are.

Given an undirected graph $X$, there are two choices of $H$ that have been used in quantum walks: the adjacency matrix $A(X)$ and the Laplacian matrix $L(X)$. We will study them separately.