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:1211.4719

Quantum graph walks II: Quantum walks on graph coverings

Yusuke Higuchi, Norio Konno, Iwao Sato, Etsuo Segawa

Published Nov 20, 2012• 3 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.1211.4719

Related papers

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

Zeta Functions with Respect to General Coined Quantum Walk of Periodic Graphs

Takashi Komatsu, Norio Konno, Iwao Sato

We define a zeta function of a graph by using the time evolution matrix of a general coined quantum walk on it, and give a determinant expression for the zeta function of a finite graph. Furthermore, we present a determinant expression for the zeta function of an (inifinite) periodic graph.

arXiv:1910.12782•The Electronic Journal of Combinatorics•Jul 9, 2020•1 citation

A note on the discrete-time evolutions of quantum walk on a graph

Yusuke Higuchi, Norio Konno, Iwao Sato +1 more

For a quantum walk on a graph, there exist many kinds of operators for the discrete-time evolution. We give a general relation between the characteristic polynomial of the evolution matrix of a quantum walk on edges and that of a kind of transition matrix of a classical random walk on vertices. Furthermore we determine the structure of the positive support of the cube of some evolution matrix, which is said to be useful for isospectral problem in graphs, under a certain condition.

arXiv:1207.4987•Jul 20, 2012•13 citations

A simple method for finding the scattering coefficients of quantum graphs

Seth Stannard Cottrell

Quantum walks are roughly analogous to classical random walks, and similar to classical walks they have been used to find new (quantum) algorithms. When studying the behavior of large graphs or combinations of graphs, it is useful to find the response of a subgraph to signals of different frequencies. In doing so, we can replace an entire subgraph with a single vertex with variable scattering coefficients. In this paper, a simple technique for quickly finding the scattering coefficients of any discrete-time quantum graph will be presented. These scattering coefficients can be expressed entirely in terms of the characteristic polynomial of the graph’s time step operator. This is a marked improvement over previous techniques which have traditionally required finding eigenstates for a given eigenvalue, which is far more computationally costly. With the scattering coefficients we can easily derive the “impulse response” which is the key to predicting the response of a graph to any signal. This gives us a powerful set of tools for rapidly understanding the behavior of graphs or for reducing a large graph into its constituent subgraphs regardless of how they are connected.

arXiv:1503.00253•Journal of Mathematical Physics•Sep 1, 2015•9 citations

Quantum Walks on Strongly Regular Graphs

Krystal Guo

This thesis studies the transition matrix of a quantum walk on strongly regular graphs. It is proposed by Emms, Hancock, Severini and Wilson in 2006, that the spectrum of a matrix based on the amplitudes of walks in the quantum walk, distinguishes strongly regular graphs. \n \nWe begin by finding the eigenvalues of matrices describing the quantum walk for regular graphs. We also show that if two graphs are isomorphic, then the corresponding matrices produced by the procedure of Emms et al. are cospectral. We then look at the entries of the cube of the transition matrix and find an expression for the matrices produced by the procedure of Emms et al. in terms of the adjacency matrix and incidence matrices of the graph.

•Aug 30, 2010•4 citations

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

Takashi Komatsu, 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 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.

The Electronic Journal of Combinatorics•Nov 5, 2021•3 citations
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.
Quantum walks are roughly analogous to classical random walks, and similar to classical walks they have been used to find new (quantum) algorithms. When studying the behavior of large graphs or combinations of graphs, it is useful to find the response of a subgraph to signals of different frequencies. In doing so, we can replace an entire subgraph with a single vertex with variable scattering coefficients. In this paper, a simple technique for quickly finding the scattering coefficients of any discrete-time quantum graph will be presented. These scattering coefficients can be expressed entirely in terms of the characteristic polynomial of the graph’s time step operator. This is a marked improvement over previous techniques which have traditionally required finding eigenstates for a given eigenvalue, which is far more computationally costly. With the scattering coefficients we can easily derive the “impulse response” which is the key to predicting the response of a graph to any signal. This gives us a powerful set of tools for rapidly understanding the behavior of graphs or for reducing a large graph into its constituent subgraphs regardless of how they are connected.
This thesis studies the transition matrix of a quantum walk on strongly regular graphs. It is proposed by Emms, Hancock, Severini and Wilson in 2006, that the spectrum of a matrix based on the amplitudes of walks in the quantum walk, distinguishes strongly regular graphs. \n \nWe begin by finding the eigenvalues of matrices describing the quantum walk for regular graphs. We also show that if two graphs are isomorphic, then the corresponding matrices produced by the procedure of Emms et al. are cospectral. We then look at the entries of the cube of the transition matrix and find an expression for the matrices produced by the procedure of Emms et al. in terms of the adjacency matrix and incidence matrices of the 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 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.