A continuous-time quantum walk is a process on a network of quantum particles that is governed by the transition matrix
U(t)=e−itA, where is
A is the adjacency matrix of the graph representing the network. Certain instantaneous phenomena occuring in quantum walks can be utilized in quantum computing algorithms. The two-vertex phenomenon fractional revival occurs between vertices
u and
v at time
t if the columns of
U(t) corresponding to
u and
v are only supported on the rows indexed by those same two vertices. This means that given any initial state supported only on vertices
u and
v, the state of the system at time
t will again be supported only on those same two vertices. Fractional revival can be used to generate entanglement between two quantum particles. We will discuss
K-fractional revival, the generalization of fractional revival to
K, a larger subset of the vertices in our graph. We will also explore the related concept approximate
K-fractional revival, which denotes the existence of a sequence of times for which
U(t) comes arbitrarily close to achieving
K-fractional revival. Next, we will examine some spectral characterizations of these phenomena, which will allow us to determine if a given graph exhibits either
K-fractional revival or approximate
K-fractional revival. Lastly, we will detail families of examples of approximate
K-fractional revival on path graphs.--Author's abstract
We develop the theory of fractional revival in the quantum walk on a graph using its Laplacian matrix as the Hamiltonian. We first give a spectral characterization of Laplacian fractional revival, which leads to a polynomial time algorithm to check this phenomenon and find the earliest time when it occurs. We then apply the characterization theorem to special families of graphs. In particular, we show that no tree admits Laplacian fractional revival except for the paths on two and three vertices, and the only graphs on a prime number of vertices that admit Laplacian fractional revival are double cones. Finally, we construct, through Cartesian products and joins, several infinite families of graphs that admit Laplacian fractional revival; some of these graphs exhibit polygamous fractional revival.