Periodicity for the 3-state quantum walk on cycles

Kei Saito; Norio Konno; Shohei Koyama; Takeshi Kajiwara

arxiv: 1907.01725 · v1 · pith:Q6CBPNBBnew · submitted 2019-07-03 · 🪐 quant-ph

Periodicity for the 3-state quantum walk on cycles

Takeshi Kajiwara , Norio Konno , Shohei Koyama , Kei Saito This is my paper

Pith reviewed 2026-05-25 10:41 UTC · model grok-4.3

classification 🪐 quant-ph

keywords quantum walkcycle graphperiodicityGrover walkFourier walkcyclotomic field3-state walk

0 comments

The pith

3-state Grover and Fourier quantum walks on cycles have finite period only for N=3.

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

The paper proves that standard 3-state quantum walks on cycle graphs C_N are periodic only in the single case N=3. For the Grover coin the period is exactly 6; for the Fourier coin it is exactly 12. All other cycle lengths yield aperiodic walks. The proof rests on a new necessary condition, obtained by embedding the eigenvalues of the time-evolution operator into cyclotomic fields, that any coin operator must satisfy before finite periodicity can occur. Readers care because exact return after a fixed number of steps controls recurrence, localization, and the possibility of perfect state transfer in these discrete quantum systems.

Core claim

Both the Grover and Fourier 3-state quantum walks on C_N possess no finite period except when N=3, in which case the periods are T_3=6 for Grover and T_3=12 for Fourier. This follows from a cyclotomic-field technique that first extracts a necessary algebraic condition on the coin operator for any finite period to exist and then verifies that the standard Grover and Fourier matrices satisfy the condition only for the triangle.

What carries the argument

Cyclotomic-field criterion on the eigenvalues of the unitary time-evolution operator U = S C (shift plus coin) that supplies a necessary condition for finite periodicity.

If this is right

For every N not equal to 3 the walks are aperiodic under both coins.
The cyclotomic necessary condition rules out finite periods for any coin operator whose eigenvalues fail to lie in the appropriate cyclotomic extension.
Periodicity on C_3 is completely classified for the two canonical coins.
The method separates the algebraic obstruction from the concrete verification step.

Where Pith is reading between the lines

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

The same cyclotomic test can be applied to other 3-state coins or to higher-state walks to decide periodicity without computing the full spectrum.
Aperiodic walks on large cycles imply that recurrence probabilities decay rather than oscillate with a fixed period.
The result supplies a concrete obstruction that any search for perfect state transfer on cycles must overcome.

Load-bearing premise

The coin operators must be exactly the standard Grover and Fourier matrices and the evolution operator must be the usual shift-plus-coin unitary on the cycle.

What would settle it

An explicit integer N greater than 3 together with a finite T such that the Grover or Fourier walk returns exactly to its initial state after T steps on C_N.

read the original abstract

Dukes (2014) and Konno, Shimizu, and Takei (2017) studied the periodicity for 2-state quantum walks whose coin operator is the Hadamard matrix on cycle graph C_N with N vertices. The present paper treats the periodicity for 3-state quantum walks on C_N. Our results follow from a new method based on cyclotomic field. This method shows a necessary condition for the coin operator of quantum walks to have the finite period. Moreover, we reveal the period T_N of two kinds of typical quantum walks, the Grover and Fourier walks. We prove that both walks do not have any finite period except for N=3, in which case T_3=6 (Grover), =12 (Fourier).

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.

Desk Editor's Note private letter to a colleague

Cyclotomic fields give a necessary condition for finite periods in 3-state cycle walks, with explicit non-periodicity for N>3 on the standard Grover and Fourier coins.

read the letter

The main result is a necessary condition on the coin operator, obtained from cyclotomic field properties, that must hold if the evolution operator on C_N has finite order. The paper then checks the two usual 3-state coins and finds that only N=3 works, with periods 6 for Grover and 12 for Fourier. For N>3 both coins fail the condition, so they have no finite period. This is the first place the cyclotomic approach appears for these walks, and the non-periodicity statement for N>3 is new relative to the 2-state Hadamard papers cited in the abstract. The method is external to the specific matrices, which keeps the reasoning non-circular. The assumptions are the standard coin-plus-shift form, so they match what anyone working in the area would expect. The explicit periods for N=3 are stated cleanly and follow from the same condition. The central claim therefore stands on its own terms. The main limitation is scope rather than a flaw in the argument. The paper does not test other 3-state coins that might satisfy the necessary condition, nor does it move beyond cycles. Those choices keep the work focused but also mean the result stays inside a narrow slice of quantum-walk problems. No load-bearing gaps appear in the logic that is described. Readers already following periodicity questions in discrete quantum walks will find the technique and the concrete non-periodicity result directly usable. The paper is a self-contained algebraic contribution that deserves referee time so the details of the cyclotomic derivation can be checked and the method can be assessed for reuse on other coins or graphs.

Referee Report

0 major / 2 minor

Summary. The manuscript develops a cyclotomic-field method to derive a necessary condition on the coin operator for the time-evolution operator U of a 3-state quantum walk on the cycle C_N to satisfy U^T = I for some finite T. It applies the condition to the standard Grover coin (2/3 J - I) and Fourier coin (DFT matrix), proving that finite periods exist only for N=3, with explicit values T_3=6 (Grover) and T_3=12 (Fourier).

Significance. If the central derivation holds, the work supplies a concrete algebraic tool extending the 2-state periodicity results of Dukes (2014) and Konno et al. (2017) to the 3-state setting. The explicit periods for N=3 are directly falsifiable by matrix powering on the small graph, and the method is parameter-free once the standard coins are fixed.

minor comments (2)

[§2] §2, definition of the shift operator: the action on the three internal states is stated only implicitly; an explicit matrix form for the shift on C_N would clarify the subsequent eigenvalue analysis.
[§4] The proof that the necessary condition fails for all N>3 is given via cyclotomic-field degree arguments, but the explicit check for N=3 (where the condition holds) is only sketched; a short table of the relevant cyclotomic orders for N=3,4,5 would make the contrast immediate.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the careful summary of our manuscript and for recommending minor revision. No specific major comments were listed in the report, so we have no points requiring direct response or revision at this time.

Circularity Check

0 steps flagged

No significant circularity; derivation relies on external cyclotomic-field properties

full rationale

The paper derives a necessary condition for finite periodicity of the standard coin-plus-shift evolution operator on C_N by invoking algebraic properties of cyclotomic fields, which are independent number-theoretic facts external to the quantum-walk model. This condition is then checked directly against the Grover and Fourier coins, yielding the stated periods only for N=3. No step reduces by construction to a fitted parameter, self-defined quantity, or load-bearing self-citation chain; the cited prior works on 2-state walks supply context but are not invoked to justify the 3-state result. The argument is therefore self-contained against external mathematical benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper rests on standard algebraic number theory (cyclotomic fields) and the definition of discrete-time quantum walk evolution; no free parameters or invented entities are indicated in the abstract.

axioms (2)

standard math Properties of cyclotomic fields determine the eigenvalues of the evolution operator on C_N
Invoked to obtain the necessary condition for finite period
domain assumption The time-evolution operator is the standard coin-plus-shift unitary on the cycle
Standard definition of coined quantum walk

pith-pipeline@v0.9.0 · 5660 in / 1232 out tokens · 33973 ms · 2026-05-25T10:41:11.634115+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

18 extracted references · 18 canonical work pages · 2 internal anchors

[1]

Aharonov, Y., Davidovich, L., Zagury, N., Quantum rando m walks, Phys. Rev. A, 48, 1687–1690 (1993)

work page 1993
[2]

Ambainis, A., Bach, E., Nayak, A., Vishwanath, A., Watro us, J., One-dimensional quantum walks, In: Proceed- ings of the 33rd Annual ACM Symposium on Theory of Computing, pp.37–49 (2001)

work page 2001
[3]

Higuchi, Y., Konno, N., Sato, I., Segawa, E., Periodicit y of the discrete-time quantum walk on a ﬁnite graph, Interdiscip. Inf. Sci., 23, 75–86 (2017)

work page 2017
[4]

Full state revivals in higher dimensional quantum walks

Jayakody, M. N., Nanayakkara, A., Full state revivals in higher dimensional quantum walks, arXiv:1806.07032 (2018)

work page internal anchor Pith review Pith/arXiv arXiv 2018
[5]

R., Quantum state revivals in quantum walks on c ycles, Results in Physics, 4, 189–197 (2014)

Dukes, P. R., Quantum state revivals in quantum walks on c ycles, Results in Physics, 4, 189–197 (2014)

work page 2014
[6]

Konno, N., Shimizu, Y., Takei, M., Periodicity for the Ha damard walk on cycles, Interdiscip. Inf. Sci., 23, 1–8 (2017)

work page 2017
[7]

L., Ide, Y., Konno, N., Periodicity for sp ace-inhomogeneous quantum walks on the cycle, Yokohama Math

Arai, T., Ho, C. L., Ide, Y., Konno, N., Periodicity for sp ace-inhomogeneous quantum walks on the cycle, Yokohama Math. J., 62, 39–50 (2016)

work page 2016
[8]

Kubota, S., Segawa, S., Taniguchi, T., Yoshie, Y., Perio dicity of Grover walks on generalized Bethe trees, Linear Algebra Its Appl., 554, 371–391 (2018)

work page 2018
[9]

J., 63, 9–23 (2017)

Yoshie, Y., A characterization of the graphs to induce pe riodic Grover walk, Yokohama Math. J., 63, 9–23 (2017)

work page 2017
[10]

Yoshie, Y., Periodicity of Grover walks on distance-re gular graphs, arXiv:1805.07681 (2018)

work page internal anchor Pith review Pith/arXiv arXiv 2018
[11]

Comput., 19, 23–34 (2018)

Saito, K., Periodicity for the Fourier quantum walk on r egular graphs, Quantum Inf. Comput., 19, 23–34 (2018)

work page 2018
[12]

A., Ostaszewski, M., Lively quantum walks on cycles, J

Sadowski, P., Miszczak, J. A., Ostaszewski, M., Lively quantum walks on cycles, J. Phys. A., 49, 375302 (2016)

work page 2016
[13]

Inui, N., Konno, N., Segawa, E., One-dimensional three -state quantum walk, Phys. Rev. E., 72, 056112 (2005)

work page 2005
[14]

Comput., 15, 406–418 (2015)

Machida, T., Limit theorems of a 3-state quantum walk an d its application for discrete uniform measures, Quantum Inf. Comput., 15, 406–418 (2015)

work page 2015
[15]

E., Quantum Walks for Computer Sci entists, Morgan and Claypool (2008)

Venegas-Andraca, S. E., Quantum Walks for Computer Sci entists, Morgan and Claypool (2008)

work page 2008
[16]

E., Quantum walks: a comprehensiv e review, Quantum Inf

Venegas-Andraca, S. E., Quantum walks: a comprehensiv e review, Quantum Inf. Process., 11, 1015–1106 (2012)

work page 2012
[17]

Manouchehri, K., Wang, J., Physical Implementation of Quantum Walks, Springer, Berlin (2014)

work page 2014
[18]

Porugal, R., Quantum Walks and Search Algorithms, Spri nger, Berlin (2013). 6

work page 2013

[1] [1]

Aharonov, Y., Davidovich, L., Zagury, N., Quantum rando m walks, Phys. Rev. A, 48, 1687–1690 (1993)

work page 1993

[2] [2]

Ambainis, A., Bach, E., Nayak, A., Vishwanath, A., Watro us, J., One-dimensional quantum walks, In: Proceed- ings of the 33rd Annual ACM Symposium on Theory of Computing, pp.37–49 (2001)

work page 2001

[3] [3]

Higuchi, Y., Konno, N., Sato, I., Segawa, E., Periodicit y of the discrete-time quantum walk on a ﬁnite graph, Interdiscip. Inf. Sci., 23, 75–86 (2017)

work page 2017

[4] [4]

Full state revivals in higher dimensional quantum walks

Jayakody, M. N., Nanayakkara, A., Full state revivals in higher dimensional quantum walks, arXiv:1806.07032 (2018)

work page internal anchor Pith review Pith/arXiv arXiv 2018

[5] [5]

R., Quantum state revivals in quantum walks on c ycles, Results in Physics, 4, 189–197 (2014)

Dukes, P. R., Quantum state revivals in quantum walks on c ycles, Results in Physics, 4, 189–197 (2014)

work page 2014

[6] [6]

Konno, N., Shimizu, Y., Takei, M., Periodicity for the Ha damard walk on cycles, Interdiscip. Inf. Sci., 23, 1–8 (2017)

work page 2017

[7] [7]

L., Ide, Y., Konno, N., Periodicity for sp ace-inhomogeneous quantum walks on the cycle, Yokohama Math

Arai, T., Ho, C. L., Ide, Y., Konno, N., Periodicity for sp ace-inhomogeneous quantum walks on the cycle, Yokohama Math. J., 62, 39–50 (2016)

work page 2016

[8] [8]

Kubota, S., Segawa, S., Taniguchi, T., Yoshie, Y., Perio dicity of Grover walks on generalized Bethe trees, Linear Algebra Its Appl., 554, 371–391 (2018)

work page 2018

[9] [9]

J., 63, 9–23 (2017)

Yoshie, Y., A characterization of the graphs to induce pe riodic Grover walk, Yokohama Math. J., 63, 9–23 (2017)

work page 2017

[10] [10]

Yoshie, Y., Periodicity of Grover walks on distance-re gular graphs, arXiv:1805.07681 (2018)

work page internal anchor Pith review Pith/arXiv arXiv 2018

[11] [11]

Comput., 19, 23–34 (2018)

Saito, K., Periodicity for the Fourier quantum walk on r egular graphs, Quantum Inf. Comput., 19, 23–34 (2018)

work page 2018

[12] [12]

A., Ostaszewski, M., Lively quantum walks on cycles, J

Sadowski, P., Miszczak, J. A., Ostaszewski, M., Lively quantum walks on cycles, J. Phys. A., 49, 375302 (2016)

work page 2016

[13] [13]

Inui, N., Konno, N., Segawa, E., One-dimensional three -state quantum walk, Phys. Rev. E., 72, 056112 (2005)

work page 2005

[14] [14]

Comput., 15, 406–418 (2015)

Machida, T., Limit theorems of a 3-state quantum walk an d its application for discrete uniform measures, Quantum Inf. Comput., 15, 406–418 (2015)

work page 2015

[15] [15]

E., Quantum Walks for Computer Sci entists, Morgan and Claypool (2008)

Venegas-Andraca, S. E., Quantum Walks for Computer Sci entists, Morgan and Claypool (2008)

work page 2008

[16] [16]

E., Quantum walks: a comprehensiv e review, Quantum Inf

Venegas-Andraca, S. E., Quantum walks: a comprehensiv e review, Quantum Inf. Process., 11, 1015–1106 (2012)

work page 2012

[17] [17]

Manouchehri, K., Wang, J., Physical Implementation of Quantum Walks, Springer, Berlin (2014)

work page 2014

[18] [18]

Porugal, R., Quantum Walks and Search Algorithms, Spri nger, Berlin (2013). 6

work page 2013