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

The Electronic Journal of Combinatorics

A Characteristic Polynomial for the Transition Probability Matrix of Correlated Random Walks on a Graph

Takashi Komatsu, Norio Konno, Iwao Sato

Published Nov 5, 2021• 3 citations
Publisher

Abstract

We define a correlated random walk (CRW) induced from the time evolution matrix (the Grover matrix) of the Grover walk on a graph $G$, and present a formula for the characteristic polynomial of the transition probability matrix of this CRW by using a determinant expression for the generalized weighted zeta function of $G$. As an application, we give the spectrum of the transition probability matrices for the CRWs induced from the Grover matrices of regular graphs and semiregular bipartite graphs. Furthermore, we consider another type of the CRW on a graph.

DOI
10.37236/10108

Related papers

A Characteristic Polynomial for The Transition Probability Matrix of A Correlated Random Walk on A Graph

Komatsu, Takashi, Norio Konno, Iwao Sato

We define a correlated random walk (CRW) induced from the time evolution matrix (the Grover matrix) of the Grover walk on a graph $G$, and present a formula for the characteristic polynomial of the transition probability matrix of this CRW by using a determinant expression for the generalized weighted zeta function of $G$. As applications, we give the spectrum of the transition probability matrices for the CRWs induced from the Grover matrices of regular graphs and semiregular bipartite graphs. Furthermore, we consider another type of the CRW on a graph.

arXiv:2012.09619•Dec 17, 2020•0 citations

A weighted graph zeta function involved in the Szegedy walk

Ayaka Ishikawa, Norio Konno

We define a new weighted zeta function for a finite graph and obtain its determinant expression. This result gives the characteristic polynomial of the transition matrix of the Szegedy walk on a graph.

arXiv:2110.05068•Quantum Information and Computation•Dec 28, 2021•1 citation

A family of quantum walks on a finite graph corresponding to the generalized weighted zeta function

Ayaka Ishikawa

This paper gives the quantum walks determined by graph zeta functions. The result enables us to obtain the characteristic polynomial of the transition matrix of the quantum walk, and it determines the behavior of the quantum walk. We treat finite graphs allowing multi-edges and multi-loops.

arXiv:2211.00904•Nov 2, 2022•0 citations

The absolute zeta function with respect to a bipartite walk on a bipartite graph

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

Abstract We consider the zeta function associated with the time evolution matrix of a bipartite walk on a bipartite graph and derive a formula for its absolute zeta function. Furthermore, we give formulas for the absolute zeta functions of the zeta functions of the time evolution matrices of bipartite walks on the complete bipartite graph and an even cycle graph. As an application, we obtain formulas for the absolute zeta functions of the zeta functions of the Grover matrices of the complete bipartite graph and an even cycle graph.

Quantum Studies Mathematics and Foundations•Mar 4, 2026•0 citations

Quantum graph walks II: Quantum walks on graph coverings

Yusuke Higuchi, Norio Konno, Iwao Sato +1 more

We give a new determinant expression for the characteristic polynomial of the bond scattering matrix of a quantum graph G. Also, we give a decomposition formula for the characteristic polynomial of the bond scattering matrix of a regular covering of G. Furthermore, we define an L-function of G, and give a determinant expression of it. As a corollary, we express the characteristic polynomial of the bond scattering matrix of a regular covering of G by means of its L-functions. As an application, we introduce three types of quantum graph walks, and treat their relation.

arXiv:1211.4719•Nov 20, 2012•3 citations

A spectral analysis of the correlated random walk

Yusuke Ide, Akihiro Narimatsu

In this paper, we consider a spectral analysis of the Correlated Random Walk (CRW) on the path. We apply an analytical method for the Quantum Walk to CRW. For the isospectral coin cases, we obtain all of the eigenvalues and the corresponding eigenvectors of the time evolution operator of CRW. We show that most of them are described by the eigenvalues and the eigenvectors of the Jacobi matrix related to the random walks on the path (the birth and death chains). The remaining eigenvector corresponding to an eigenvalue 1, is characterized by the stationary measure of the same birth and death chain. As a consequence, we derive the limiting distribution.

arXiv:2310.20220•Linear and Multilinear Algebra•Mar 28, 2026•0 citations
We define a correlated random walk (CRW) induced from the time evolution matrix (the Grover matrix) of the Grover walk on a graph GGG, and present a formula for the characteristic polynomial of the transition probability matrix of this CRW by using a determinant expression for the generalized weighted zeta function of GGG. As an application, we give the spectrum of the transition probability matrices for the CRWs induced from the Grover matrices of regular graphs and semiregular bipartite graphs. Furthermore, we consider another type of the CRW on a graph.
We define a correlated random walk (CRW) induced from the time evolution matrix (the Grover matrix) of the Grover walk on a graph GGG, and present a formula for the characteristic polynomial of the transition probability matrix of this CRW by using a determinant expression for the generalized weighted zeta function of GGG. As applications, we give the spectrum of the transition probability matrices for the CRWs induced from the Grover matrices of regular graphs and semiregular bipartite graphs. Furthermore, we consider another type of the CRW on a graph.
Abstract We consider the zeta function associated with the time evolution matrix of a bipartite walk on a bipartite graph and derive a formula for its absolute zeta function. Furthermore, we give formulas for the absolute zeta functions of the zeta functions of the time evolution matrices of bipartite walks on the complete bipartite graph and an even cycle graph. As an application, we obtain formulas for the absolute zeta functions of the zeta functions of the Grover matrices of the complete bipartite graph and an even cycle graph.
We give a new determinant expression for the characteristic polynomial of the bond scattering matrix of a quantum graph G. Also, we give a decomposition formula for the characteristic polynomial of the bond scattering matrix of a regular covering of G. Furthermore, we define an L-function of G, and give a determinant expression of it. As a corollary, we express the characteristic polynomial of the bond scattering matrix of a regular covering of G by means of its L-functions. As an application, we introduce three types of quantum graph walks, and treat their relation.
In this paper, we consider a spectral analysis of the Correlated Random Walk (CRW) on the path. We apply an analytical method for the Quantum Walk to CRW. For the isospectral coin cases, we obtain all of the eigenvalues and the corresponding eigenvectors of the time evolution operator of CRW. We show that most of them are described by the eigenvalues and the eigenvectors of the Jacobi matrix related to the random walks on the path (the birth and death chains). The remaining eigenvector corresponding to an eigenvalue 1, is characterized by the stationary measure of the same birth and death chain. As a consequence, we derive the limiting distribution.