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

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

Sho Kubota

math.COquant-phSubmitted Sep 8, 2026• Announced Sep 9, 2026
arXivHTMLPDF

Abstract

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$.

Comments
22 pages, 13 figures

Related papers

Periodicity of bipartite walk on biregular graphs with conditional spectra

Qiuting Chen

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.

arXiv:2211.02752•Physica Scripta•Aug 21, 2024•2 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•0 citations

Odd-periodic Grover walk

Yusuke Yoshie

The Grover walk is one of the most well-studied quantum walks on graphs. In this paper, we investigate its periodicity to reveal the relationship between the quantum walk and the underlying graph, focusing particularly on the characterization of graphs exhibiting a periodic Grover walk. Graphs having a periodic Grover walk with periods of $2, 3, 4$, and $5$ have previously been characterized. It is expected that graphs exhibiting a periodic Grover walk with odd period correspond to cycles with odd length. We address that problem and are able to perfectly characterize the class of graphs exhibiting an odd-periodic Grover walk by using a combinatorial method.

arXiv:2106.06710•Jun 12, 2021•0 citations

A group structure arising from Grover walks on complete graphs with self-loops and its application

Tatsuya Tsurii, Naoharu Ito

This paper introduces a group-theoretic framework to analyze the algebraic structure of the Grover walk on a complete graph with self-loops. We construct a group generated by the Grover matrix and a diagonal matrix whose entries are powers of a complex root of unity. We then characterize the resulting quotient group, which is defined using a subgroup formed by commutators involving these matrices. We show that this quotient group is isomorphic to a finite cyclic group whose structure depends on the parity of the number of vertices. This group-theoretic characterization reveals underlying symmetries in the time evolution of the Grover walk and provides an algebraic framework for understanding its periodic behavior.

quant-pharXiv:2602.13686•Discrete Mathematics•Feb 17, 2026•0 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•0 citations

A Characterization of the Graphs to Induce Periodic Grover Walk

Yusuke Yoshie

This paper explains the periodicity of the Grover walk on finite graphs. We characterize the graphs to induce 2, 3, 4, 5-periodic Grover walk and obtain a necessary condition of the graphs to induce an odd-periodic Grover walk.

arXiv:1703.06286•Mar 18, 2017•4 citations
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.
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.
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.
The Grover walk is one of the most well-studied quantum walks on graphs. In this paper, we investigate its periodicity to reveal the relationship between the quantum walk and the underlying graph, focusing particularly on the characterization of graphs exhibiting a periodic Grover walk. Graphs having a periodic Grover walk with periods of 2,3,42, 3, 42,3,4, and 555 have previously been characterized. It is expected that graphs exhibiting a periodic Grover walk with odd period correspond to cycles with odd length. We address that problem and are able to perfectly characterize the class of graphs exhibiting an odd-periodic Grover walk by using a combinatorial method.
This paper introduces a group-theoretic framework to analyze the algebraic structure of the Grover walk on a complete graph with self-loops. We construct a group generated by the Grover matrix and a diagonal matrix whose entries are powers of a complex root of unity. We then characterize the resulting quotient group, which is defined using a subgroup formed by commutators involving these matrices. We show that this quotient group is isomorphic to a finite cyclic group whose structure depends on the parity of the number of vertices. This group-theoretic characterization reveals underlying symmetries in the time evolution of the Grover walk and provides an algebraic framework for understanding its periodic behavior.
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.