REVIEW 4 major objections 4 minor 1 cited by
Perfect state transfer in Grover walks on association schemes and distance-regular graphs
T0 review · 4 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash
Pith's one-line read Perfect state transfer in a Grover walk is decided by one algebraic object: a fixed-point-free involution class of the graph's association scheme.
desk verdict A useful framework with a fixable but real eigenvalue-indexing flaw; the classifications likely survive, but the main theorem needs reformulation. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing identity is Lemma 3.3: $NU^\tau N^* = T_\tau(P)$, where $N$ is the boundary matrix of the Grover walk, $U$ its time-evolution operator, $P = D^{-1/2}AD^{-1/2}$ the degree-normalized adjacency matrix (the discriminant), and $T_\tau$ the Chebyshev polynomial of the first kind, which satisfies $T_\tau(\cos\theta)=\cos(\tau\theta)$. This identity converts the dynamical definition of perfect state transfer, $|\langle U^\tau\Phi_u,\Phi_v\rangle|=1$, into the matrix equation $T_\tau(P)e_u=e_v$. Since $T_\tau(P)$ is a polynomial in the adjacency matrix of the graph, it lies in the Bose–Mesner algebra of the scheme, so the equality forces $T_\tau(P)$ to be one of the scheme's own classes — a symmetric permutation matrix of order 2 with no fixed points. The proof then compares, on the idempotent basis, whether $T_\tau$ matches that class's eigenvalue $+1$ on the $I^+_B$ block and $-1$ on the $I^-_B$ block, which yields both the transfer time and the destination vertex.
What would settle it
Simulate the Grover walk directly on a graph the paper rules out, such as the Hamming class $H(6,2,3)$, scanning all vertex pairs and all times up to the graph's period for a squared transfer amplitude $|\langle U^\tau\Phi_u,\Phi_v\rangle|^2$ equal to 1; the paper's theorems predict none exists, so a single observed perfect transfer would refute the classification. Conversely, the positive list is directly checkable: $H(2,2,1)$ should transfer at time 2, $J(4,2,1)$ at time 6, and $C_6$ at time 3.
Extended reading notes
Core claim
The paper's central claim is that perfect state transfer in a Grover walk is a statement about the graph's association scheme rather than about the walk's time evolution: for a graph $G$ in a scheme whose discriminant has distinct eigenvalues $\mu_0 > \cdots > \mu_d$ on the principal idempotents $E_j$, transfer from $u$ to $v$ at time $\tau$ occurs exactly when the scheme contains a class $B$ that is a fixed-point-free involution with $B_{uv}=1$, and $T_\tau(\mu_j)=1$ for every $j$ with $BE_j=E_j$ while $T_\tau(\mu_j)=-1$ for every $j$ with $BE_j=-E_j$ (Theorem 3.7). Because both $T_\tau(P)$ and $B$ live in the Bose–Mesner algebra of the scheme, this says the time-$\tau$ transfer matrix literally realizes the class $B$. For distance-regular graphs (Theorem 4.2) the condition collapses to: $G$ is antipodal with two-vertex fibres and $T_\tau(\mu_j)=(-1)^j$, with transfer between antipodal vertices. The paper's classifications are exhaustive for the families it treats: among Hamming classes only $H(d,2,d)$ and $H(2,2,1)$ transfer; among Johnson classes only $J(2k,k,0)$ and $J(4,2,1)$; among cycles only the even ones; among complete graphs only $K_2$; among integral distance-regular graphs only $K_2$, $C_4$, $C_6$, and $K_{2,2,2}$, with $C_4$ and $K_{2,2,2}$ the complete diameter-2 answer and $C_6$ the complete diameter-3 answer.
Load-bearing premise
The negative half of every classification rests on a periodicity theorem imported from the authors' own earlier preprint rather than proven here — the claim that a periodic regular graph can have rational discriminant eigenvalues only among $\pm 1$, $\pm 1/2$, and $0$ — and if that restriction gives way, the 'only if' half of the paper's classifications would collapse.
Editorial extensions
If this is right
- Any graph in an association scheme that exhibits perfect state transfer is periodic with transfer time exactly half the period, and the destination vertex is unique: a vertex cannot transfer its state to two different receivers (Lemma 3.5, Proposition 3.6).
- For distance-regular graphs, perfect state transfer forces the graph to be antipodal with two-vertex fibres, and transfer always occurs between antipodal vertices at a time fixed by the alternating Chebyshev signs (Theorem 4.2).
- The Hamming and Johnson classifications are complete: the hypercube transfers only in dimensions 1 and 2, Hamming classes only for $(d,2,d)$ and $(2,2,1)$, and Johnson classes only for $(2k,k,0)$ and $(4,2,1)$ (Theorems 3.10 and 3.13, Corollary 3.10.1).
- The distance-regular classifications are closed: among diameter-2 graphs only $C_4$ and $K_{2,2,2}$ transfer, among diameter-3 graphs only $C_6$, and among integral distance-regular graphs only $K_2$, $C_4$, $C_6$, and $K_{2,2,2}$ (Theorems 4.5, 4.6, and 4.8).
- A direct corollary is that familiar symmetric graphs such as the Petersen graph and every complete graph beyond $K_2$ never transfer a vertex state perfectly.
Reading between the lines
- Because the criterion is stated purely in terms of the scheme's eigenvalue table, it offers a template for screening other association schemes — Grassmann, bilinear-forms, or biweight schemes, for example — for perfect state transfer by computation alone, without simulating the walk.
- The negative results lean on a periodicity theorem proven elsewhere; deriving those eigenvalue restrictions from first principles, or verifying them independently, would make the classifications fully self-contained.
- The uniqueness of the destination (Proposition 3.6) implies that these symmetric networks cannot act as quantum routers that split one incoming state between two different outputs — a constraint worth testing in quantum network designs.
- The sign condition $T_\tau(\mu_j)=\pm 1$ forces each discriminant eigenvalue to be the cosine of a rational multiple of $\pi$, so for any fixed scheme one can precompute all candidate transfer times from the eigenvalue table before doing any dynamical simulation.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies perfect state transfer (PST) in discrete-time Grover walks on graphs that belong to association schemes. It first proves (Theorem 3.4) that PST from a vertex u to a vertex v at time τ is equivalent to Tτ(P) being a fixed-point-free involution class B in the scheme with B_{uv}=1, where P is the discriminant matrix. Theorem 3.7 reformulates this in terms of the eigenvalues of P on the principal idempotents, and Theorems 3.10 and 3.13 give complete classifications for the graphs H(d,q,i) and J(n,k,i) in the Hamming and Johnson schemes, with the only PST cases being H(d,2,d), H(2,2,1), J(2k,k,0), and J(4,2,1). For distance-regular graphs, Theorem 4.2 characterizes PST as antipodality with fibres of size two plus a Chebyshev sign condition, leading to classifications for diameter 2 and 3 (C4 and K_{2,2,2}; C6), for cycles and complete graphs, and for integral distance-regular graphs (K2, C4, C6, K_{2,2,2}).
Significance. If the main characterization is repaired as described below, the paper gives a clean algebraic criterion for Grover-walk PST on association-scheme graphs and settles the Hamming and Johnson classes and several distance-regular families. The positive constructions are simple and easy to verify, and the transfer times are explicit (τ=1 for the perfect-matching classes, τ=2 for C4, τ=6 for K_{2,2,2} and J(4,2,1), τ=3 for C6). The arithmetic in the exclusion arguments is consistent, and the connection between Chebyshev polynomials and the scheme idempotents is a natural and useful framework. The paper is a potentially valuable contribution, provided the distinct-eigenvalue hypothesis in Theorem 3.7 is replaced by the scheme-eigenvalue formulation and the results imported from unpublished preprints are either proved or clearly identified as external. As written, the central theorem is not correct as a universal statement because it excludes the paper's own positive examples.
major comments (4)
- [Theorem 3.7 (and Theorems 3.9, 3.12)] The main characterization is stated with a hypothesis that is not satisfied by the paper's own positive examples. Theorem 3.7 assumes the discriminant P has distinct eigenvalues μ0>...>μd and, via Lemma 2.10, uses the spectral idempotents of P as the scheme's principal idempotents E0,...,Ed. This requires G to have d+1 distinct adjacency eigenvalues. However, the graphs H(d,2,d) for d≥2 and J(2k,k,0) for k≥2, which the paper proves exhibit PST in Theorems 3.10 and 3.13, have Spec P={1,-1} and hence do not have d+1 distinct eigenvalues while their schemes have d+1 (resp. k+1) classes. For these graphs the premise μ0>...>μd cannot be met, so the universal statement is undefined for the central positive constructions. The proof should be recast by defining μ_j through P E_j = μ_j E_j on the scheme's principal idempotents, with repetitions allowed; the distinct-eigenvalue version then becomes the nondegenerate special case. Theorems 3.9 and 3.12 need the same reformulation, indexing the μ_j by the scheme classes rather than by a sorted distinct list.
- [Lemma 3.3] In the proof of Lemma 3.3, after obtaining Tτ(P)e_u=γ e_v with γ∈{±1}, the passage showing γ=1 is garbled. The correct argument is to use the idempotent E0 for the eigenvalue 1 and take inner products with D^{1/2}j, which gives sqrt(deg u)=γ sqrt(deg v); the printed equations instead sum over all vertices and conclude γ times the total degree sum, which does not follow. The conclusion γ=1 is valid for the regular graphs on which the paper's later results rely, so the lemma is repairable, but the proof as written is wrong.
- [Proposition 3.6] The proof of Proposition 3.6 is a non-sequitur. It states that if G has PST from u to v and from u to w, then by Lemma 3.5 the transfers occur at the same time τ; Lemma 3.5 only asserts that the minimum transfer time τ makes the graph 2τ-periodic and says nothing about the transfer times to the two destinations. The proposition is not used later, so this does not by itself affect the main classifications, but a correct proof or a reformulated statement is needed.
- [Theorems 3.10, 3.13, 4.5, 4.6, 4.8] The negative classifications rely on Theorem 2.5, imported from the authors' unpublished preprint [5], and Theorem 4.8 relies on [4, Theorem 5.9] from another unpublished preprint. Since these results are not proved in this manuscript, the completeness claims are conditional on external work that the reader cannot verify. The rational-eigenvalue consequences used in Theorems 3.10, 3.13, 4.5, and 4.6 can be derived from Lemma 3.5 together with Niven's theorem (rational values of cosines of rational multiples of π are 0, ±1/2, ±1), so those cases are robust; the integral classification in Theorem 4.8, however, uses the full classification [4, Theorem 5.9] and should either be proved here or explicitly flagged as conditional.
minor comments (4)
- [Lemma 2.7] The expressions 'cos s/m π' should read cos(sπ/m), and the case μ=1 (s=0) is not covered by 'positive integers s'.
- [Theorem 3.12] In the statement and proof, the index d is used for the number of classes of the Johnson scheme; it should be k, so the eigenvalues should be μ0>...>μk and the index set should be {0,...,k}.
- [Lemma 4.3] For an even cycle C_n, the distinct discriminant eigenvalues are cos(2πj/n) for j=0,...,n/2, not j=0,...,n/2−1; the omitted j=n/2 eigenvalue also satisfies the stated sign condition, so the conclusion is unaffected.
- [Theorem 4.5] The phrase 'complete (n−k)-partite graph' is nonstandard: for K_{2,2,2}, n−k=2 but the graph has three parts of size two. Please state the number of parts and the part size explicitly (parts of size n−k, i.e. n/(n−k) parts).
Circularity Check
Self-cited periodicity classifications from [4,5] are load-bearing in the negative classifications; the central scheme theorem itself is derived from external lemmas.
-
uniqueness imported from authors
[Theorem 3.10 proof, using Theorem 2.5 (stated in Section 2 from [5]); also used in Theorems 3.13, 4.5, and 4.6]
"Applying Theorem 2.5 together with the Equation (3.4), we find that µ_i_1 = 1 − 2i/d ∈ {±1, ±1/2, 0}, which implies that i ∈ {d/2, d/4, 3d/4}."
Theorem 2.5 is imported from the authors' own unpublished preprint [5], is not proved in the present paper, and has no machine-checked or externally verified status supplied here. It is the sole step that restricts the Hamming eigenvalue µ_i_1 to {±1, ±1/2, 0}, and therefore it is the sole mechanism eliminating all but finitely many parameter pairs in the negative classification. The exclusion argument reduces to this unverified self-citation rather than to a derivation contained in the paper.
-
self citation load bearing
[Theorem 4.8 proof, using Theorem 4.7 ([4, Theorem 5.9])]
"In [4], we presented a characterization of integral periodic regular graphs. Theorem 4.7 ([4, Theorem 5.9]). A graph G is regular, integral and periodic if and only if it is either the cycle C6 or the complete bipartite graph K_{k,k} or the complete tripartite graph K_{k,k,k} or Spec P(G) = {1, ±1/2, 0} or Spec P(G) = {±1, ±1/2, 0}."
Theorem 4.7 is taken verbatim from the authors' own prior work [4] with no proof and no independent verification in the present manuscript, and the proof of Theorem 4.8 depends on it to reduce all integral distance-regular graphs to the four named candidates. If [4, Theorem 5.9] were absent or incomplete, the integral classification would not follow from anything proved here. Thus the final classification is load-bearing on a self-citation chain.
full rationale
The paper's main algebraic criterion, Theorem 3.7, is not circular by construction: it is derived in-paper from Lemma 3.3 and standard spectral facts, and the positive examples (H(d,2,d), J(2k,k,0), C4, C6, K_{2,2,2}) are verified by direct Chebyshev-polynomial evaluation. However, the exclusion halves of Theorems 3.10, 3.13, 4.5, 4.6, and 4.8 all rely on the authors' own unproved-in-paper classifications: Theorem 2.5 from [5] and Theorem 4.7 from [4]. These are imported as black boxes and are the only mechanism that cuts the relevant parameter sets down to finitely many candidates; no independent proof, code, or machine verification is offered here. That makes the negative classifications reduce to a self-citation chain, even though the positive direction and the central scheme-level characterization retain independent content. A separate correctness concern, not a circularity, is that Theorem 3.7 assumes distinct eigenvalues µ0 > ... > µd while the paper's own positive examples H(d,2,d) and J(2k,k,0) have repeated discriminant eigenvalues; this is a rigor gap in the theorem statement, not a circular reduction.
Assumptions & free parameters
assumptions (6)
- standard math Theorem 2.1: eigenvalues of the Grover time evolution matrix are {e^{±i arccos μ_j}} plus ±1 from cycles and bipartiteness (from Kubota et al.).
- standard math Lemma 2.8: N U^τ N* = T_τ(P) (from Kubota-Segawa).
- domain assumption Theorem 2.5: classification of periodic regular Grover walks by rational, quadratic, and irrational discriminant eigenvalue sets.
- domain assumption Theorem 4.7: classification of integral periodic regular graphs as C6, K_{k,k}, K_{k,k,k}, or two spectrum types.
- standard math Krawtchouk eigenvalue formulas (3.2) and (3.8) for Hamming and Johnson schemes.
- standard math An antipodal distance-regular graph of diameter 3 is an r-fold cover of K_n with spectrum given by (4.1).
Cite this review
Pith. "Pith review of Perfect state transfer in Grover walks on association schemes and distance-regular graphs." pith.science (2026). https://pith.science/paper/3W5365V7
@misc{pith2026250607439,
author = {Pith},
title = {Pith review of: Perfect state transfer in Grover walks on association schemes and distance-regular graphs},
year = {2026},
howpublished = {\url{https://pith.science/paper/3W5365V7}},
note = {Machine review of arXiv:2506.07439}
}
abstract
This paper investigates perfect state transfer in Grover walks, a model of discrete-time quantum walks. We establish a necessary and sufficient condition for the occurrence of perfect state transfer on graphs belonging to an association scheme. Our focus includes specific association schemes, namely the Hamming and Johnson schemes. We characterize all graphs on the classes of Hamming and Johnson schemes that exhibit perfect state transfer. Furthermore, we study perfect state transfer on distance-regular graphs. We provide complete characterizations for exhibiting perfect state transfer on distance-regular graphs of diameter $2$ and diameter $3$, as well as integral distance-regular graphs.
Forward citations
Cited by 1 Pith paper
-
Perfect state transfer in Grover walks on normal Cayley graphs
Perfect state transfer in Grover walks on normal Cayley graphs occurs exactly when the target is a central involution and the Chebyshev polynomials of the discriminant eigenvalues have prescribed signs, yielding exact...
Reference graph
Works this paper leans on
-
[5]
K. Bhakta and B. Bhattacharjya. Periodicity and perfect state transfer of Grover walks on quadratic unitary Cayley graphs.arXiv:2408.08715. 2024
arXiv 2024
-
[1]
B. Ahmadi, M.H.S. Haghighi, and A. Mokhtar. Perfect quantum state transfer on the Johnson scheme.Linear Algebra and its Applications. 584:326–342, 2020
work page 2020
- [2]
-
[3]
E. Bannai and T. Ito. Algebraic Combinatorics I: Association Schemes.Mathematics Lecture Note Series, 1984
work page 1984
-
[4]
K. Bhakta and B. Bhattacharjya. Grover walks on unitary Cayley graphs and integral regular graphs. arXiv:2405.01020. 2024
arXiv 2024
-
[6]
K. Bhakta and B. Bhattacharjya. State transfer in Grover walks on unitary and quadratic unitary Cayley graphs over finite commutative rings.arXiv:2502.10217. 2025. 21
work page Pith review arXiv 2025
-
[7]
A.E. Brouwer, A.M. Cohen, and A. Neumaier. Distance-Regular Graphs.Springer-Verlag, 1989
work page 1989
-
[8]
A.E. Brouwer and W.H. Haemers. Spectra of Graphs.Universitext, Springer, NewYork, 2012
work page 2012
Show all 39 references
-
[9]
Chan and H
A. Chan and H. Zhan. Pretty good state transfer in discrete-time quantum walks.Journal of Physics A: Mathematical and Theoretical. 56:165305, 2023
2023
-
[10]
Q. Chen, C. Godsil, M. Sobchuk, and H. Zhan. Hamiltonians of bipartite walks.The Electronic Journal of Combinatorics. 31(4):#P4.10, 2024
2024
-
[11]
Coutinho, C
G. Coutinho, C. Godsil, K. Guo, and F. Vanhove. Perfect state transfer on distance-regular graphs and association schemes.Linear Algebra and its Applications. 478:108–130, 2015
2015
-
[12]
Coutinho, E
G. Coutinho, E. Juliano, and T.J. Spier. No perfect state transfer in trees with more than 3 vertices. Journal of Combinatorial Theory, Series B. 168:68–85, 2024
2024
-
[13]
Delsarte
P. Delsarte. An Algebraic Approach to the Association Schemes of Coding Theory.N.V. Philips’ Gloeilampenfabrieken, 1973
1973
-
[14]
Gamble, M
J.K. Gamble, M. Friesen, D. Zhou, R. Joynt, and S.N. Coppersmith. Two-particle quantum walks applied to the graph isomorphism problem.Physical Review A. 81(5):052313, 2010
2010
-
[15]
C. Godsil. State transfer on graphs.Discrete Mathematics. 312(1):129–147, 2012
2012
-
[16]
Godsil and A
C. Godsil and A. Hensel. Distance regular covers of the complete graph.Journal of Combinatorial Theory, Series B. 56(2):205–238, 1992
1992
-
[17]
Godsil and H
C. Godsil and H. Zhan. Discrete-time quantum walks and graph structures.Journal of Combinatorial Theory, Series A. 167:181–212, 2019
2019
-
[18]
Greaves and L.H
G.R.W. Greaves and L.H. Soicher. On the clique number of a strongly regular graph.The Electronic Journal of Combinatorics. 25(4):#P4.15, 2018
2018
-
[19]
Guo and V
K. Guo and V. Schmeits. State transfer in discrete-time quantum walks via projected transition matrices.arXiv:2411.05560. 2025
2025 arXiv
-
[20]
Higuchi, N
Y. Higuchi, N. Konno, I. Sato, and E. Segawa. Periodicity of the discrete-time quantum walk on a finite graph.Interdisciplinary Information Sciences. 23:75–86, 2017
2017
-
[21]
Higuchi, N
Y. Higuchi, N. Konno, I. Sato, and E. Segawa. Spectral and asymptotic properties of Grover walks on crystal lattices.Journal of Functional Analysis. 267(11):4197–4235, 2014
2014
-
[22]
N. Ito, T. Matsuyama, and T. Tsurii. Periodicity of Grover walks on complete graphs with self-loops. Linear Algebra and its Applications. 599:121–132, 2020. 22
2020
-
[23]
V. Kendon. Quantum walks on general graphs.International Journal of Quantum Information. 4(5):791–805, 2006
2006
-
[24]
S. Kubota. Combinatorial necessary conditions for regular graphs to induce periodic quantum walks. Linear Algebra and its Applications. 673:259–279, 2023
2023
-
[25]
S. Kubota. Periodicity of Grover walks on bipartite regular graphs with at most five distinct eigen- values.Linear Algebra and its Applications. 654:125–142, 2022
2022
-
[26]
Kubota and E
S. Kubota and E. Segawa. Perfect state transfer in Grover walks between states associated to vertices of a graph.Linear Algebra and its Applications. 646:238–251, 2022
2022
-
[27]
Kubota, E
S. Kubota, E. Segawa, and T. Taniguchi. Quantum walks defined by digraphs and generalized Hermitian adjacency matrices.Quantum Information Processing. 20:95, 2021
2021
-
[28]
Kubota, E
S. Kubota, E. Segawa, T. Taniguchi, and Y. Yoshie. Periodicity of Grover walks on generalized Bethe trees.Linear Algebra and its Applications. 554:371–391, 2018
2018
-
[29]
Kubota, H
S. Kubota, H. Sekido, and H. Yata. Periodicity of quantum walks defined by mixed paths and mixed cycles.Linear Algebra and its Applications. 630:15–38, 2021
2021
-
[30]
Kubota, H
S. Kubota, H. Sekido, and H. Yoshino. Regular graphs to induce even periodic Grover walks.Discrete Mathematics. 348(3):114345, 2025
2025
-
[31]
Kubota and K
S. Kubota and K. Yoshino. Circulant graphs with valency up to 4 that admit perfect state transfer in Grover walks.Journal of Combinatorial Theory, Series A. 216:106064, 2025
2025
-
[32]
MacWilliams and N.J.A
F.J. MacWilliams and N.J.A. Sloane. The Theory of Error-Correcting Codes.Vol. 16. Elsevier, 1977
1977
-
[33]
Mandal, R.S
A. Mandal, R.S. Sarkar, and B. Adhikari. Localization of two dimensional quantum walks defined by generalized Grover coins.Journal of Physics A: Mathematical and Theoretical. 56:025303, 2023
2023
-
[34]
Shenvi, J
N. Shenvi, J. Kempe, and K.B. Whaley. A quantum random-walk search algorithm.Physical Review A. 67(5):052307, 2003
2003
-
[35]
Y. Yoshie. Odd-periodic Grover walks.Quantum Information Processing. 22:316, 2023
2023
-
[36]
Y. Yoshie. Periodicity of Grover walks on distance-regular graphs.Graphs and Combinatorics. 35:1305–1321, 2019
2019
-
[37]
H. Zhan. An infinite family of circulant graphs with perfect state transfer in discrete quantum walks. Quantum Information Processing. 18:369, 2019. 23
2019
-
[38]
H. Zhan. Factoring discrete-time quantum walks on distance regular graphs into continuous-time quantum walks.Linear Algebra and its Applications. 648:88–103, 2022
2022
-
[39]
H. Zhan. Quantum walks on embeddings.Journal of Algebraic Combinatorics. 53:1187–1213, 2021. 24
2021
Reviewed August 7, 2026 · model on record in the stance chip above.
Discussion (0). Sign in to comment.