arXiv:2610.21946
A complete classification of perfect state transfer in Grover walks on abelian Cayley graphs
Koushik Bhakta, Bikash Bhattacharjya
Abstract
We completely classify connected Cayley graphs over finite abelian groups that exhibit perfect state transfer in Grover walks. First, we show that a Cayley graph over any finite group exhibiting perfect state transfer has valency $1$, $2$, or $4$. For valency $4$, we prove that an abelian Cayley graph $\operatorname{Cay}(Γ,S)$ exhibits perfect state transfer if and only if $S=\{a,-a,a+h,-a+h\}$, where $h$ has order $2$, and $4\nmid |Γ|/2$. Combining this characterization with the valency-one and valency-two cases, we explicitly determine all pairs $(Γ,S)$ for which $\operatorname{Cay}(Γ,S)$ exhibits perfect state transfer. Our results extend the classification of circulant graphs of valency at most four obtained by Kubota and Yoshino [Circulant graphs with valency up to 4 that admit perfect state transfer in Grover walks, \emph{J. Comb. Theory Ser. A.}, 216 (2025) 106064] to Cayley graphs over arbitrary finite abelian groups and to all valencies.
AI Summary
The paper asks which connected Cayley graphs over finite abelian groups admit perfect state transfer in discrete-time Grover walks. Transfer is restricted to vertex-type states: uniform superpositions over arcs terminating at a vertex, rather than arbitrary states in the walk Hilbert space. A first result applies to Cayley graphs over any finite group, including nonabelian groups: perfect state transfer requires valency $1$, $2$, or $4$. For connected abelian Cayley graphs of valency four, transfer occurs exactly when the connection set has the form $S=\{a,-a,a+h,-a+h\}$, where $h$ has order two and $4\nmid |\Gamma|/2$. Writing $m=|\Gamma|/2$, transfer is only from $u$ to $u+h$, and occurs precisely at times satisfying $m\mid\tau$ and $\tau\equiv2\pmod4$; the minimum time is $\operatorname{lcm}(2,m)$. Together with $K_2$ and even cycles, this yields a complete classification, including all group–connection-set representations up to group isomorphisms preserving the connection set. The proofs express vertex transfer through Chebyshev polynomials of the normalized adjacency matrix. Algebraic-integrality constraints, trace–rank inequalities, and a block decomposition along transfer pairs exclude other valencies and force paired vertices to have identical neighborhoods. Translation operators and finite abelian group structure then establish sufficiency and classify the representations. This extends the previous classification of circulants of valency at most four. The complete classification is confined to connected abelian Cayley graphs; for nonabelian groups, the result is the valency restriction.
During the preparation of this work, the authors used ChatGPT to suggest proof ideas for few results and to generate examples.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.