Periodic Vertices

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.

Home