Perfect State Transfer on Quotient Graphs in Shunt Decomposition-Based Quantum Walks

Abstract

This paper investigates perfect state transfer (PST) in discrete-time quantum walks constructed via the shunt decomposition method. The walks are defined on a graph $G$ and its associated quotient graph $G/π$, induced by an equitable partition $π$. Through the shunt decomposition of $G$, we derive an explicit relation between the shift operator of the parent graph $G$ and that of its quotient graph $G/π$. We construct a reflection operator based on the characteristic matrix, which establishes a connection between the transition operator of the parent graph and that of its lower-dimensional quotient graph. We then prove that PST occurs on $G$ if and only if it occurs on $G/π$. Furthermore, we express the unitary evolution operator of the quotient graph in terms of Chebyshev polynomials of the first kind, from which we derive explicit criteria for PST. As an application, we establish PST on the cycle graph $C_{n}$ at time $k = n/2$, and lift the result to the parent graph $C_{2n}$ via the equitable partition $π$. We further show that if an equitable partition $π$ of $G$ induces a quotient isomorphic to $K_n^{\circlearrowleft}$, the complete digraph on $n$ vertices with a loop at every vertex, then PST occurs at step $k = n$, and the walk is periodic at $k = 2n$. This framework is applied to two families of graphs, which are the complete bipartite digraph $K_{n,n}^{\rightleftharpoons}$ and the circulant graph $\operatorname{Circ}(2n, S)$, where $S$ consists of all odd residues modulo $2n$ and $n = 2^s$ for some $s \geq 1$, establishing PST in their respective line digraphs. Collectively, these results also answer the question posed by Godsil and Zhan concerning which shunt decompositions or embeddings of a graph admit PST.