Spectrum
The behaviour of a quantum walk is closedly related to the spectrum of the graph. Let \[ H = \sum_r \theta_r E_r \] be the spectral decomposition of $H$. The eigenvalue support of a vertex $v$, denoted $S(v)$, is the set of eigenvalues $\theta_r$ such that $E_re_v \ne 0$, or equivalently, \[ S(v) = \{\theta_r: (E_r)_{vv}\ne 0\}. \] The following theorem in [1] characterizes the periodicity of a vertex in terms of its eigenvalue support.
- The eigenvalues in $S(v)$ are integers.
- There is a square-free integer $\Delta$, such that the eigenvalues in $S(v)$ are quadratic integers in $\rats\left(\sqrt{\Delta}\right)$, and the difference of any two eigenvalues in $S(v)$ is an integer multiple of $\sqrt{\Delta}$.
Thus it suffices to compute the eigenvalue support of $v$. Consider two characteristic polynomials \[ \phi(t) = \det(tI-H) \] and \[ \phi_v(t) = \det(tI-H(v:v)) \] where $H(v:v)$ is obtained from $H$ by removing the $v$-th row and the $v$-th column. Using the spectral decomposition of $H$, the ratio of $\phi(t)$ to $\phi_v(t)$ can be neatly expressed as \[ \frac{\phi_v(t)}{\phi(t)} = \sum_r \frac{1}{t-\theta_r} (E_r)_{vv}. \] If we let \[ g_v(t) = \gcd(\phi(t), \phi_v(t)) \] and \[ \psi_v(t) = \frac{\phi(t)}{g_v(t)} \] then the zeros of $\psi_v(t)$ are precisely the eigenvalue support of $v$.
Now suppose we have found a periodic vertex $v$. How do we determine its minimum period $\tau$? Let \[ U(\tau)_{vv}=\gamma \] for some phase factor $\gamma$. Spectral decomposition tells us that \[ e^{i\tau\theta_r} (E_r)_{vv} = \gamma (E_r)_{vv}. \] where $\theta_r$ is any eigenvalue in the eigenvalue support of $v$. For such an eigenvalue, the entry $(E_r)_{vv}$ is never zero, so it follows that \[ e^{i\tau\theta_r} = \gamma \] for all $\theta_r \in S(v)$. If the graph is connected, then $\left| S(v) \right|\ge 2$. Fixing any eigenvalue $\theta_0$ in $S(v)$, we see that $\theta_r-\theta_0$ divides $2\pi$ for the remaining eigenvalues $\theta_r$ in $S(v)$.