Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1907.01725 · Quantum Information and Computation

Periodicity for the 3-state quantum walk on cycles

Takeshi Kajiwara, Norio Konno, Shohei Koyama, Kei Saito

Published Nov 1, 2019• 12 citations
arXivHTMLPDF

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 the cyclotomic field. This method gives a necessary condition for the coin operator for quantum walks to be periodic. Moreover, we reveal the period T_N of typical two kinds of 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).

DOI
10.26421/qic19.13-14-1

Related papers

Periodicity for the Hadamard Walk on Cycles

Norio Konno, Yuki Shimizu, Masato Takei

The present paper treats the period TN of the Hadamard walk on a cycle CN with N vertices. Dukes (2014) considered the periodicity of more general quantum walks on CN and showed T2=2, T4=8, T8=24 for the Hadamard walk case. We prove that the Hadamard walk does not have any period except for his case, i.e., N = 2,4,8. Our method is based on a path counting and cyclotomic polynomials which is different from his approach based on the property of eigenvalues for unitary matrix that determines the evolution of the walk.

arXiv:1504.06396•Interdisciplinary Information Sciences•Jan 1, 2017•21 citations

Periodicity for the Fourier quantum walk on regular graphs

Kei Saito

Quantum walks determined by the coin operator on graphs have been intensively studied. The typical examples of coin operator are the Grover and Fourier matrices. The periodicity of the Grover walk is well investigated. However, the corresponding result on the Fourier walk is not known. In this paper, we present a necessary condition for the Fourier walk on regular graphs to have the finite period. As an application of our result, we show that the Fourier walks do not have any finite period for some classes of regular graphs such as complete graphs, cycle graphs with selfloops, and hypercubes.

arXiv:1811.03235•Quantum Information and Computation•Feb 1, 2019•10 citations

Periodicity and absolute zeta functions of multi-state grover walks on cycles

Jirô Akahori, Norio Konno, Iwao Sato +1 more

Quantum walks, the quantum counterpart of classical random walks, are extensively studied for their applications in mathematics, quantum physics, and quantum information science. This study explores the periods and absolute zeta functions of Grover walks on cycle graphs. Specifically, we investigate Grover walks with an odd number of states and determine their periods for cycles with any number of vertices greater than or equal to two. In addition, we compute the absolute zeta functions of M-type Grover walks with finite periods. These results advance the understanding of the properties of Grover walks and their connection to absolute zeta functions.

arXiv:2501.18600•International Journal of Quantum Information•Mar 1, 2025•1 citation

Periodicity for space-inhomogeneous quantum walks on the cycle

Arai, Toshiyuki, Choon-Lin Ho, Ide, Yusuke +1 more

In this paper, we consider periodicity for space-inhomogeneous quantum walks on the cycle. For isospectral coin cases, we propose a spectral analysis. Based on the analysis, we extend the result for periodicity for Hadamard walk to some isospectral coin cases. For non-isospectral coin cases, we consider the the system that uses only one general coin at the origin and the identity coin at the other sites. In this case, we show that the periodicity of the general coin at the origin determines the periodicity for the whole system.

arXiv:1611.09583•Nov 29, 2016•5 citations

Absolute Zeta functions and periodicity of quantum walks on cycles

Jirô Akahori, Norio Konno, Iwao Sato +1 more

The quantum walk is a quantum counterpart of the classical random walk. On the other hand, absolute zeta functions can be considered as zeta functions over $\mathbf{F}_1$. This study presents a connection between quantum walks and absolute zeta functions. In this paper, we focus on Hadamard walks and $3$-state Grover walks on cycle graphs. The Hadamard walks and the Grover walks are typical models of the quantum walks. We consider the periods and zeta functions of such quantum walks. Moreover, we derive the explicit forms of the absolute zeta functions of corresponding zeta functions. Also, it is shown that our zeta functions of quantum walks are absolute automorphic forms.

arXiv:2405.05995•Quantum Information and Computation•Oct 1, 2024•0 citations

Quantum Walks on the Line with Phase Parameters

Marcos Villagra, Masaki Nakanishi, Shigeru Yamashita +1 more

In this paper, a study on discrete-time coined quantum walks on the line is presented. Clear mathematical foundations are still lacking for this quantum walk model. As a step toward this objective, the following question is being addressed: Given a graph, what is the probability that a quantum walk arrives at a given vertex after some number of steps? This is a very natural question, and for random walks it can be answered by several different combinatorial arguments. For quantum walks this is a highly non-trivial task. Furthermore, this was only achieved before for one specific coin operator (Hadamard operator) for walks on the line. Even considering only walks on lines, generalizing these computations to a general SU(2) coin operator is a complex task. The main contribution is a closed-form formula for the amplitudes of the state of the walk (which includes the question above) for a general symmetric SU(2) operator for walks on the line. To this end, a coin operator with parameters that alters the phase of the state of the walk is defined. Then, closed-form solutions are computed by means of Fourier analysis and asymptotic approximation methods. We also present some basic properties of the walk which can be deducted using weak convergence theorems for quantum walks. In particular, the support of the induced probability distribution of the walk is calculated. Then, it is shown how changing the parameters in the coin operator affects the resulting probability distribution.

arXiv:1109.1866•IEICE Transactions on Information and Systems•Jan 1, 2012•4 citations
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 the cyclotomic field. This method gives a necessary condition for the coin operator for quantum walks to be periodic. Moreover, we reveal the period T_N of typical two kinds of 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).
The present paper treats the period TN of the Hadamard walk on a cycle CN with N vertices. Dukes (2014) considered the periodicity of more general quantum walks on CN and showed T2=2, T4=8, T8=24 for the Hadamard walk case. We prove that the Hadamard walk does not have any period except for his case, i.e., N = 2,4,8. Our method is based on a path counting and cyclotomic polynomials which is different from his approach based on the property of eigenvalues for unitary matrix that determines the evolution of the walk.
Quantum walks determined by the coin operator on graphs have been intensively studied. The typical examples of coin operator are the Grover and Fourier matrices. The periodicity of the Grover walk is well investigated. However, the corresponding result on the Fourier walk is not known. In this paper, we present a necessary condition for the Fourier walk on regular graphs to have the finite period. As an application of our result, we show that the Fourier walks do not have any finite period for some classes of regular graphs such as complete graphs, cycle graphs with selfloops, and hypercubes.
Quantum walks, the quantum counterpart of classical random walks, are extensively studied for their applications in mathematics, quantum physics, and quantum information science. This study explores the periods and absolute zeta functions of Grover walks on cycle graphs. Specifically, we investigate Grover walks with an odd number of states and determine their periods for cycles with any number of vertices greater than or equal to two. In addition, we compute the absolute zeta functions of M-type Grover walks with finite periods. These results advance the understanding of the properties of Grover walks and their connection to absolute zeta functions.
In this paper, we consider periodicity for space-inhomogeneous quantum walks on the cycle. For isospectral coin cases, we propose a spectral analysis. Based on the analysis, we extend the result for periodicity for Hadamard walk to some isospectral coin cases. For non-isospectral coin cases, we consider the the system that uses only one general coin at the origin and the identity coin at the other sites. In this case, we show that the periodicity of the general coin at the origin determines the periodicity for the whole system.
The quantum walk is a quantum counterpart of the classical random walk. On the other hand, absolute zeta functions can be considered as zeta functions over F1\mathbf{F}_1F1​. This study presents a connection between quantum walks and absolute zeta functions. In this paper, we focus on Hadamard walks and 333-state Grover walks on cycle graphs. The Hadamard walks and the Grover walks are typical models of the quantum walks. We consider the periods and zeta functions of such quantum walks. Moreover, we derive the explicit forms of the absolute zeta functions of corresponding zeta functions. Also, it is shown that our zeta functions of quantum walks are absolute automorphic forms.
In this paper, a study on discrete-time coined quantum walks on the line is presented. Clear mathematical foundations are still lacking for this quantum walk model. As a step toward this objective, the following question is being addressed: Given a graph, what is the probability that a quantum walk arrives at a given vertex after some number of steps? This is a very natural question, and for random walks it can be answered by several different combinatorial arguments. For quantum walks this is a highly non-trivial task. Furthermore, this was only achieved before for one specific coin operator (Hadamard operator) for walks on the line. Even considering only walks on lines, generalizing these computations to a general SU(2) coin operator is a complex task. The main contribution is a closed-form formula for the amplitudes of the state of the walk (which includes the question above) for a general symmetric SU(2) operator for walks on the line. To this end, a coin operator with parameters that alters the phase of the state of the walk is defined. Then, closed-form solutions are computed by means of Fourier analysis and asymptotic approximation methods. We also present some basic properties of the walk which can be deducted using weak convergence theorems for quantum walks. In particular, the support of the induced probability distribution of the walk is calculated. Then, it is shown how changing the parameters in the coin operator affects the resulting probability distribution.