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:2211.02752 · Physica Scripta

Periodicity of bipartite walk on biregular graphs with conditional spectra

Qiuting Chen

Published Aug 21, 2024• 5 citations
arXivHTMLPDF

Abstract

Abstract In this paper we study a class of discrete quantum walks, known as bipartite walks. These include the well-known Grover’s walks. A discrete quantum walk is given by the powers of a unitary matrix U indexed by arcs or edges of the underlying graph. The walk is periodic if U k = I for some positive integer k. Kubota has given a characterization of periodicity of Grover’s walk when the walk is defined on a regular bipartite graph with at most five eigenvalues. We extend Kubota’s results—if a biregular graph G has eigenvalues whose squares are algebraic integers with degree at most two, we characterize periodicity of the bipartite walk over G in terms of its spectrum. We apply periodicity results of bipartite walks to get a characterization of periodicity of Grover’s walk on regular graphs.

DOI
10.1088/1402-4896/ad71ff

Related papers

Characterizations of graphs to induce periodic grover walk

Yusuke Yoshie

Recently, a research on quantum walks has been developed in various areas.In this paper we focus on the periodicity of the Grover walk which is one of the quantum walks on the discrete graphs.Then we find some special graphs to induce a periodic Grover walk: At some time k, the quantum state φ k returns its initial quantum state φ 0 .Our purpose is to characterize graphs which induce a k-periodic Grover walk for a fixed integer k.We do it for k = 2, 3, 4, 5 and gain a necessary condition for odd k.

•Jan 1, 2017•0 citations

Grover walks on unitary Cayley graphs and integral regular graphs

Koushik Bhakta, Bikash Bhattacharjya

The unitary Cayley graph has vertex set $\{0,1, \hdots ,n-1\}$, where two vertices $u$ and $v$ are adjacent if $\gcd(u - v, n) = 1$. In this paper, we study periodicity and perfect state transfer of Grover walks on the unitary Cayley graphs. We characterize all periodic unitary Cayley graphs. We prove that periodicity is a necessary condition for occurrence of perfect state transfer on a vertex-transitive graph. Also, we provide a necessary and sufficient condition for the occurrence of perfect state transfer on circulant graphs. Using these, we prove that only four graphs in the class of unitary Cayley graphs exhibit perfect state transfer. Also, we provide a spectral characterization of the periodicity of Grover walks on integral regular graphs.

arXiv:2405.01020•May 2, 2024•10 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

Strongly regular and strongly walk-regular graphs that admit perfect state transfer

Sho Kubota, Hiroto Sekido, Harunobu Yata +1 more

We study perfect state transfer in Grover walks on two important classes of graphs: strongly regular graphs and strongly walk-regular graphs. The latter class is a generalization of the former. We first give a complete classification of strongly regular graphs that admit perfect state transfer. The only such graphs are the complete bipartite graph $K_{2,2}$ and the complete tripartite graph $K_{2,2,2}$. We then show that, if a connected strongly walk-regular graph that is not a strongly regular graph admits perfect state transfer, then its spectrum must be of the form $\{[k]^1, [\frac{k}{2}]^α, [0]^β, [-\frac{k}{2}]^γ\}$, and we enumerate all feasible spectra of this form up to $k=20$ with the help of a computer. These results are obtained using techniques from algebraic number theory and spectral graph theory, particularly through the analysis of eigenvalues and eigenprojections of a normalized adjacency matrix. While the setting is in quantum walks, the core discussion is developed entirely within the framework of spectral graph theory.

arXiv:2506.02530•Jun 3, 2025•3 citations

Spectral characterization of the uniform theta graph $Θ(t,2)$ and classification of 6-periodic Grover walks

Sho Kubota

We characterize the uniform theta graph $Θ(t,2)$ by the spectrum of its normalized adjacency matrix, or equivalently, by the spectrum of its normalized Laplacian matrix. We also investigate the periodicity of Grover walks on nonregular graphs, which is closely related to the eigenvalues of the normalized adjacency matrix and those of the time evolution matrix of the Grover walk. We show that the Dutch windmill graph $D_n^{(t)}$ is $2n$-periodic and that the uniform theta graph $Θ(t,n)$ is $(2n+2)$-periodic. Furthermore, we completely determine the connected $6$-periodic graphs and prove that they are precisely $D_3^{(t)}$ with $t \geq 2$ and $Θ(t,2)$ with $t \geq 1$.

math.COCross-listedarXiv:2609.08315•Sep 9, 2026

Hamiltonians of Bipartite Walks

Qiuting Chen, Chris D. Godsil, Mariia Sobchuk +1 more

In this paper, we introduce a discrete quantum walk model called bipartite walks. Bipartite walks include many known discrete quantum walk models, like Grover’s walks, vertex-face walks. For the transition matrix of a quantum walk, there is a Hamiltonian associated with it. We will study the Hamiltonians of the bipartite walks. Let $S$ be a skew-symmetric matrix. We are mainly interested in the Hamiltonians of the form $iS$. We show that the Hamiltonian can be written as $iS$ if and only if the adjacency matrix of the bipartite graph is invertible. We show that Grover’s walks and vertex-face walks are special cases of bipartite walks. Via the Hamiltonians, phenomena of bipartite walks lead to phenomena of continuous walks. We show in detail how we use bipartite walks on paths to construct universal perfect state transfer in continuous walks.

arXiv:2207.01673•The Electronic Journal of Combinatorics•Oct 3, 2024•8 citations
Abstract In this paper we study a class of discrete quantum walks, known as bipartite walks. These include the well-known Grover’s walks. A discrete quantum walk is given by the powers of a unitary matrix U indexed by arcs or edges of the underlying graph. The walk is periodic if U k = I for some positive integer k. Kubota has given a characterization of periodicity of Grover’s walk when the walk is defined on a regular bipartite graph with at most five eigenvalues. We extend Kubota’s results—if a biregular graph G has eigenvalues whose squares are algebraic integers with degree at most two, we characterize periodicity of the bipartite walk over G in terms of its spectrum. We apply periodicity results of bipartite walks to get a characterization of periodicity of Grover’s walk on regular graphs.
Recently, a research on quantum walks has been developed in various areas.In this paper we focus on the periodicity of the Grover walk which is one of the quantum walks on the discrete graphs.Then we find some special graphs to induce a periodic Grover walk: At some time k, the quantum state φ k returns its initial quantum state φ 0 .Our purpose is to characterize graphs which induce a k-periodic Grover walk for a fixed integer k.We do it for k = 2, 3, 4, 5 and gain a necessary condition for odd k.
The unitary Cayley graph has vertex set $\{0,1, \hdots ,n-1\}$, where two vertices uuu and vvv are adjacent if gcd⁡(u−v,n)=1\gcd(u - v, n) = 1gcd(u−v,n)=1. In this paper, we study periodicity and perfect state transfer of Grover walks on the unitary Cayley graphs. We characterize all periodic unitary Cayley graphs. We prove that periodicity is a necessary condition for occurrence of perfect state transfer on a vertex-transitive graph. Also, we provide a necessary and sufficient condition for the occurrence of perfect state transfer on circulant graphs. Using these, we prove that only four graphs in the class of unitary Cayley graphs exhibit perfect state transfer. Also, we provide a spectral characterization of the periodicity of Grover walks on integral regular graphs.
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.
We study perfect state transfer in Grover walks on two important classes of graphs: strongly regular graphs and strongly walk-regular graphs. The latter class is a generalization of the former. We first give a complete classification of strongly regular graphs that admit perfect state transfer. The only such graphs are the complete bipartite graph K2,2K_{2,2}K2,2​ and the complete tripartite graph K2,2,2K_{2,2,2}K2,2,2​. We then show that, if a connected strongly walk-regular graph that is not a strongly regular graph admits perfect state transfer, then its spectrum must be of the form {[k]1,[k2]α,[0]β,[−k2]γ}\{[k]^1, [\frac{k}{2}]^α, [0]^β, [-\frac{k}{2}]^γ\}{[k]1,[2k​]α,[0]β,[−2k​]γ}, and we enumerate all feasible spectra of this form up to k=20k=20k=20 with the help of a computer. These results are obtained using techniques from algebraic number theory and spectral graph theory, particularly through the analysis of eigenvalues and eigenprojections of a normalized adjacency matrix. While the setting is in quantum walks, the core discussion is developed entirely within the framework of spectral graph theory.
Spectral characterization of the uniform theta graph Θ(t,2)Θ(t,2)Θ(t,2) and classification of 6-periodic Grover walks
We characterize the uniform theta graph Θ(t,2)Θ(t,2)Θ(t,2) by the spectrum of its normalized adjacency matrix, or equivalently, by the spectrum of its normalized Laplacian matrix. We also investigate the periodicity of Grover walks on nonregular graphs, which is closely related to the eigenvalues of the normalized adjacency matrix and those of the time evolution matrix of the Grover walk. We show that the Dutch windmill graph Dn(t)D_n^{(t)}Dn(t)​ is 2n2n2n-periodic and that the uniform theta graph Θ(t,n)Θ(t,n)Θ(t,n) is (2n+2)(2n+2)(2n+2)-periodic. Furthermore, we completely determine the connected 666-periodic graphs and prove that they are precisely D3(t)D_3^{(t)}D3(t)​ with t≥2t \geq 2t≥2 and Θ(t,2)Θ(t,2)Θ(t,2) with t≥1t \geq 1t≥1.
In this paper, we introduce a discrete quantum walk model called bipartite walks. Bipartite walks include many known discrete quantum walk models, like Grover’s walks, vertex-face walks. For the transition matrix of a quantum walk, there is a Hamiltonian associated with it. We will study the Hamiltonians of the bipartite walks. Let SSS be a skew-symmetric matrix. We are mainly interested in the Hamiltonians of the form iSiSiS. We show that the Hamiltonian can be written as iSiSiS if and only if the adjacency matrix of the bipartite graph is invertible. We show that Grover’s walks and vertex-face walks are special cases of bipartite walks. Via the Hamiltonians, phenomena of bipartite walks lead to phenomena of continuous walks. We show in detail how we use bipartite walks on paths to construct universal perfect state transfer in continuous walks.