pith. sign in

arxiv: 2605.02254 · v1 · submitted 2026-05-04 · 🧮 math.CO · quant-ph

Perfect state transfer in Grover walks on dihedral Cayley graphs

Koushik Bhakta , Bikash Bhattacharjya , Xiwang Cao This is my paper

Pith reviewed 2026-05-08 18:41 UTC · model grok-4.3

classification 🧮 math.CO quant-ph
keywords perfect state transferGrover walksCayley graphsdihedral groupquantum walksnon-abelian groupsrepresentation theory
0
0 comments X

The pith

Grover walks on dihedral Cayley graphs exhibit perfect state transfer exactly when n is even or the graph is non-normal.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper determines the precise conditions for perfect state transfer to occur in Grover walks on Cayley graphs Cay(D_n, S) where D_n is the dihedral group. Most earlier work on quantum walks and state transfer stayed within abelian groups, so extending the analysis to this non-abelian family matters for designing quantum networks that exploit richer symmetries. The authors split the problem by the parity of n and by whether S is a union of conjugacy classes, making the graph normal or non-normal. They prove that transfer is impossible for normal graphs when n is odd and supply necessary and sufficient conditions that cover every remaining case, together with explicit infinite families where transfer does succeed.

Core claim

Using the irreducible representations of the dihedral group D_n to diagonalize the Grover walk operator, the authors obtain necessary and sufficient conditions on the parity of n and the normality of S for perfect state transfer to occur on Cay(D_n, S). In particular, when the Cayley graph is normal and n is odd, the phases arising from the eigenvalues never permit perfect transfer at any integer time; for all other parity-normality combinations they derive the exact algebraic requirements on S and construct infinite families satisfying those requirements.

What carries the argument

The irreducible representations of the dihedral group D_n that diagonalize the Grover walk operator and supply the eigenvalues whose phases determine whether the amplitude returns exactly to the target vertex at some time.

If this is right

  • PST never occurs on normal Cayley graphs when n is odd.
  • Necessary and sufficient conditions cover every possible S for both normal and non-normal graphs.
  • Infinite families of both normal and non-normal graphs supporting PST are constructed explicitly.
  • The representation-theoretic method applies directly to quantum walks on this non-abelian group.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same diagonalization technique could be tried on Cayley graphs of other small non-abelian groups to find further families supporting PST.
  • Concrete small-order examples from the constructed families supply test cases for numerical simulation of quantum walks on finite graphs.
  • Network architectures that rely on dihedral symmetry might achieve reliable state transfer in regimes where abelian Cayley graphs fail.

Load-bearing premise

The time-evolution operator of the Grover walk must be completely diagonalizable in the basis furnished by the irreducible representations of D_n, so that the phases for state transfer can be read off directly from the eigenvalues.

What would settle it

Take n=3 (odd) and any normal connection set S that is a single conjugacy class; compute the eigenvalues of the corresponding Grover walk operator and check whether any integer time t produces unit overlap between an initial basis state and a distinct target state. Any such overlap would falsify the claim that PST never occurs for odd-n normal graphs.

Figures

Figures reproduced from arXiv: 2605.02254 by Bikash Bhattacharjya, Koushik Bhakta, Xiwang Cao.

Figure 1
Figure 1. Figure 1: Classification of PST on Cay(Dn, S) Several natural directions for future research arise from this work. One immediate extension is to investigate PST on Cayley graphs over other families of non-abelian groups and to explore whether similar classification results can be obtained. It is well known that PST is a relatively rare phenomenon. For this reason, even when PST does not occur, a natural question is … view at source ↗
read the original abstract

The paper investigates perfect state transfer (PST) in Grover walks on Cayley graphs over the dihedral group $D_n$. The Grover walk is a discrete-time quantum walk widely studied in quantum information processing. A Cayley graph $\operatorname{Cay}(\Gamma,S)$ is called normal if $S$ is the union of some conjugacy classes of the group $\Gamma$; otherwise, it is called non-normal. Most existing studies have been restricted to Cayley graphs over abelian groups. In contrast, we investigate both normal and non-normal cases for Cayley graphs over the non-abelian group $D_n$. By examining the parity of $n$ and the normality of the Cayley graph, we obtain a complete characterization of PST on $\operatorname{Cay}(D_n,S)$. In particular, we establish necessary and sufficient conditions for the occurrence of PST in all possible cases, and prove that PST does not occur for normal Cayley graphs when $n$ is odd. Furthermore, we construct several infinite families of normal and non-normal Cayley graphs $\operatorname{Cay}(D_n,S)$ that exhibit PST, illustrating the application of the main result. Our approach is based on the representation theory of the dihedral group.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The paper claims a complete characterization of perfect state transfer (PST) for Grover walks on Cayley graphs Cay(D_n, S) of the dihedral group. It distinguishes normal (S a union of conjugacy classes) versus non-normal cases and even versus odd n, proves that PST never occurs for normal graphs when n is odd, gives necessary and sufficient conditions in all cases via the eigenvalues of the walk operator, and constructs infinite families of both normal and non-normal examples that realize PST. The method relies on the irreducible representations of D_n to block-diagonalize the Grover walk operator on the arc space and to extract the phase-alignment conditions for PST.

Significance. If the derivations hold, the work is a useful extension of PST results from abelian to non-abelian Cayley graphs. The explicit case-by-case eigenvalue formulas obtained from the 1- and 2-dimensional irreps of D_n, together with the infinite families constructed for both normal and non-normal generators, supply concrete, checkable examples that can be used for further numerical or experimental study. The approach demonstrates how standard representation-theoretic tools can be applied systematically to Grover walks and may serve as a template for other small non-abelian groups.

minor comments (3)
  1. The definition of the Grover walk operator (presumably in §2) would be clearer if the authors included an explicit 2-by-2 or 4-by-4 matrix example for a small dihedral group (e.g., D_3 or D_4) before moving to the general irrep decomposition.
  2. In the statement of the main characterization theorem, a compact table summarizing the four combinations (normal/odd, normal/even, non-normal/odd, non-normal/even) together with the precise phase conditions would improve readability.
  3. A few citations to the standard references on Grover walks (e.g., the original Szegedy or Ambainis papers) and on PST criteria for coined walks would help situate the eigenvalue condition used in §3.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of our manuscript and for recommending minor revision. The referee's summary correctly captures our main results: the necessary and sufficient conditions for perfect state transfer in Grover walks on both normal and non-normal Cayley graphs of the dihedral group D_n, the proof that PST never occurs for normal graphs when n is odd, the eigenvalue formulas derived from the irreducible representations, and the construction of infinite families realizing PST.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The derivation applies standard representation theory of the finite dihedral group D_n to block-diagonalize the Grover walk operator on the arc space via its left-regular action, then extracts explicit eigenvalue formulas case-by-case from the 1- and 2-dimensional irreps according to parity of n and normality of S. These eigenvalues are inserted into the known phase-alignment criterion for perfect state transfer; the resulting necessary-and-sufficient conditions are obtained by direct computation without any self-referential definitions, fitted parameters, or load-bearing self-citations. The argument is self-contained against external benchmarks (Schur's lemma, completeness of the irrep list for D_n, and the standard PST criterion for Grover walks) and covers all symmetric generating sets by exhaustive case distinction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper builds on standard tools from group representation theory without introducing new free parameters, axioms beyond the domain, or invented entities.

axioms (1)
  • domain assumption The eigenvalues and eigenvectors of the Grover walk transition operator are determined by the irreducible representations of the dihedral group D_n.
    This is invoked to find when the phase condition for PST is satisfied.

pith-pipeline@v0.9.0 · 5520 in / 1329 out tokens · 49940 ms · 2026-05-08T18:41:19.153119+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

33 extracted references · 33 canonical work pages

  1. [1]

    Discrete quantum walks on the symmetric group.Quantum Stud.: Math

    Avah Banerjee. Discrete quantum walks on the symmetric group.Quantum Stud.: Math. Found., 11(3):477–490, 2024

    work page 2024

  2. [2]

    Non-uniform mixing of quantum walks on the symmetric group.Linear Algebra Appl., 742:37–65, 2026

    Avah Banerjee. Non-uniform mixing of quantum walks on the symmetric group.Linear Algebra Appl., 742:37–65, 2026

    work page 2026

  3. [3]

    Bhakta and B

    Koushik Bhakta and Bikash Bhattacharjya. Grover walks on unitary Cayley graphs and integral regular graphs.arXiv.2405.01020, 2024

    work page arXiv 2024

  4. [4]

    Perfect state transfer in Grover walks on association schemes and distance-regular graphs.arXiv.2506.07439, 2025

    Koushik Bhakta and Bikash Bhattacharjya. Perfect state transfer in Grover walks on association schemes and distance-regular graphs.arXiv.2506.07439, 2025

    work page arXiv 2025

  5. [5]

    Periodicity and perfect state transfer of Grover walks on quadratic unitary Cayley graphs.Quantum Inf

    Koushik Bhakta and Bikash Bhattacharjya. Periodicity and perfect state transfer of Grover walks on quadratic unitary Cayley graphs.Quantum Inf. Process., 24(8):Paper No. 260, 21, 2025

    work page 2025

  6. [6]

    Pretty good state transfer in Grover walks on abelian Cayley graphs.arXiv:2508.09711, 2025

    Koushik Bhakta and Bikash Bhattacharjya. Pretty good state transfer in Grover walks on abelian Cayley graphs.arXiv:2508.09711, 2025

    work page arXiv 2025

  7. [7]

    State transfer in Grover walks on unitary and quadratic unitary Cayley graphs over finite commutative rings.Discrete Math., 349(8):115151, 2026

    Koushik Bhakta and Bikash Bhattacharjya. State transfer in Grover walks on unitary and quadratic unitary Cayley graphs over finite commutative rings.Discrete Math., 349(8):115151, 2026

    work page 2026

  8. [8]

    Quantum communication through an unmodulated spin chain.Phys

    Sougato Bose. Quantum communication through an unmodulated spin chain.Phys. Rev. Lett., 91(20):Paper No. 207901, 4, 2003

    work page 2003

  9. [9]

    Cambridge Studies in Advanced Mathematics

    Tullio Ceccherini-Silberstein, Fabio Scarabotti, and Filippo Tolli.Representation Theory of the Symmetric Groups. Cambridge Studies in Advanced Mathematics. Cambridge University Press, 2010

    work page 2010

  10. [10]

    Hamiltonians of bipartite walks

    Qiuting Chen, Chris Godsil, Mariia Sobchuk, and Hanmeng Zhan. Hamiltonians of bipartite walks. Electron. J. Combin., 31(4):Paper No. 4.10, 24, 2024

    work page 2024

  11. [11]

    Matthias Christandl, Nilanjana Datta, Artur Ekert, and Andrew J. Landahl. Perfect state transfer in quantum spin networks.Phys. Rev. Lett., 92(18):Paper No. 187902, 4, 2004. 26

    work page 2004

  12. [12]

    State transfer on graphs.Discrete Math., 312(1):129–147, 2012

    Chris Godsil. State transfer on graphs.Discrete Math., 312(1):129–147, 2012

    work page 2012

  13. [13]

    Discrete-time quantum walks and graph structures.J

    Chris Godsil and Hanmeng Zhan. Discrete-time quantum walks and graph structures.J. Combin. Theory Ser. A, 167:181–212, 2019

    work page 2019

  14. [14]

    State transfer in discrete-time quantum walks via projected transition matrices.arXiv:2411.05560, 2025

    Krystal Guo and Vincent Schmeits. State transfer in discrete-time quantum walks via projected transition matrices.arXiv:2411.05560, 2025

    work page arXiv 2025

  15. [15]

    Spectral and asymptotic properties of Grover walks on crystal lattices.J

    Yusuke Higuchi, Norio Konno, Iwao Sato, and Etsuo Segawa. Spectral and asymptotic properties of Grover walks on crystal lattices.J. Funct. Anal., 267(11):4197–4235, 2014

    work page 2014

  16. [16]

    Quantum walks induced by Dirichlet random walks on infinite trees.J

    Yusuke Higuchi and Etsuo Segawa. Quantum walks induced by Dirichlet random walks on infinite trees.J. Phys. A, 51(7):Paper No. 075303, 21, 2018

    work page 2018

  17. [17]

    A random walk approach to quantum algorithms.Philos

    Vivien M Kendon. A random walk approach to quantum algorithms.Philos. Trans. Roy. Soc. A, 364(1849):3407–3422, 2006

    work page 2006

  18. [18]

    Perfect state transfer in Grover walks between states associated to vertices of a graph.Linear Algebra Appl., 646:238–251, 2022

    Sho Kubota and Etsuo Segawa. Perfect state transfer in Grover walks between states associated to vertices of a graph.Linear Algebra Appl., 646:238–251, 2022

    work page 2022

  19. [19]

    Periodicity of Grover walks on generalized Bethe trees.Linear Algebra Appl., 554:371–391, 2018

    Sho Kubota, Etsuo Segawa, Tetsuji Taniguchi, and Yusuke Yoshie. Periodicity of Grover walks on generalized Bethe trees.Linear Algebra Appl., 554:371–391, 2018

    work page 2018

  20. [20]

    Regular graphs to induce even periodic Grover walks.Discrete Math., 348(3):Paper No

    Sho Kubota, Hiroto Sekido, and Kiyoto Yoshino. Regular graphs to induce even periodic Grover walks.Discrete Math., 348(3):Paper No. 114345, 9, 2025

    work page 2025

  21. [21]

    Circulant graphs with valency up to 4 that admit perfect state transfer in Grover walks.J

    Sho Kubota and Kiyoto Yoshino. Circulant graphs with valency up to 4 that admit perfect state transfer in Grover walks.J. Combin. Theory Ser. A, 216:Paper No. 106064, 31, 2025

    work page 2025

  22. [22]

    Ram Murty

    M. Ram Murty. Ramanujan graphs.J. Ramanujan Math. Soc., 18(1):33–52, 2003

    work page 2003

  23. [23]

    Discrete-time quantum walks on Cayley graphs of dihedral groups using generalized Grover coins.Quantum Inf

    Rohit Sarma Sarkar and Bibhas Adhikari. Discrete-time quantum walks on Cayley graphs of dihedral groups using generalized Grover coins.Quantum Inf. Process., 23(5):Paper No. 172, 28, 2024

    work page 2024

  24. [24]

    Periodicity of lively quantum walks on cycles with generalized Grover coin.Linear Algebra Appl., 604:399–424, 2020

    Rohit Sarma Sarkar, Amrita Mandal, and Bibhas Adhikari. Periodicity of lively quantum walks on cycles with generalized Grover coin.Linear Algebra Appl., 604:399–424, 2020

    work page 2020

  25. [25]

    Volume 42 of Graduate Texts in Math- ematics

    Jean-Pierre Serre.Linear Representations of Finite Groups. Volume 42 of Graduate Texts in Math- ematics. Springer New York, 1996

    work page 1996

  26. [26]

    Perfect state transfer on hyper- cubes and its implementation using superconducting qubits.Phys

    Siddhant Singh, Bibhas Adhikari, Supriyo Dutta, and David Zueco. Perfect state transfer on hyper- cubes and its implementation using superconducting qubits.Phys. Rev. A, 102(6):Paper No. 062609, 9, 2020. 27

    work page 2020

  27. [27]

    Universi- text

    Benjamin Steinberg.Representation Theory of Finite Groups: An Introductory Approach. Universi- text. Springer New York, 2011

    work page 2011

  28. [28]

    Rodrigues, Paulo Mateus, N

    Chrysoula Vlachou, J. Rodrigues, Paulo Mateus, N. Paunkovic, and Andr´ e Souto. Quantum walk public-key cryptographic system.Int. J. Quantum Inf., 13(7):Paper No. 1550050, 2015

    work page 2015

  29. [29]

    Quantum simulations of classical random walks and undirected graph connectivity

    John Watrous. Quantum simulations of classical random walks and undirected graph connectivity. J. Comput. System Sci., 62(2):376–391, 2001

    work page 2001

  30. [30]

    Periodicities of Grover walks on distance-regular graphs.Graphs Combin., 35(6):1305–1321, 2019

    Yusuke Yoshie. Periodicities of Grover walks on distance-regular graphs.Graphs Combin., 35(6):1305–1321, 2019

    work page 2019

  31. [31]

    An infinite family of circulant graphs with perfect state transfer in discrete quantum walks.Quantum Inf

    Hanmeng Zhan. An infinite family of circulant graphs with perfect state transfer in discrete quantum walks.Quantum Inf. Process., 18(12):Paper No. 369, 26, 2019

    work page 2019

  32. [32]

    Quantum walks on embeddings.J

    Hanmeng Zhan. Quantum walks on embeddings.J. Algebraic Combin., 53(4):1187–1213, 2021

    work page 2021

  33. [33]

    Algebraic Combin., 61(4):Paper No

    Hanmeng Zhan.ϵ-uniform mixing in discrete quantum walks.J. Algebraic Combin., 61(4):Paper No. 46, 35, 2025. 28

    work page 2025