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•5 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

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•3 citations

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

Robustness of periodicity in Grover walks under a magnetic vector potential

Hiroto Sekido, Etsuo Segawa

We study the effect of magnetic vector potentials on periodic Grover walks on finite graphs. The magnetic vector potential is introduced through the framework of quantum graphs, which induces the Grover walk as a special case. We regard the magnetic vector potential as a perturbation of a periodic Grover walk and investigate the robustness of its periodicity. Our analysis reveals that the response to such perturbations depends on the spectral structure of the underlying graph. In particular, when the graph possesses at least one non-simple eigenvalue, we derive a Hermitian matrix that characterizes the robustness of its periodicity. As a consequence, for initial states orthogonal to the eigenspaces of the unperturbed Grover walk corresponding to the eigenvalues $\pm1$, we show that the perturbed dynamics is asymptotically described by a continuous-time quantum walk generated by this Hermitian matrix.

quant-pharXiv:2607.14797•Jul 17, 2026•0 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.
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.
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.
We study the effect of magnetic vector potentials on periodic Grover walks on finite graphs. The magnetic vector potential is introduced through the framework of quantum graphs, which induces the Grover walk as a special case. We regard the magnetic vector potential as a perturbation of a periodic Grover walk and investigate the robustness of its periodicity. Our analysis reveals that the response to such perturbations depends on the spectral structure of the underlying graph. In particular, when the graph possesses at least one non-simple eigenvalue, we derive a Hermitian matrix that characterizes the robustness of its periodicity. As a consequence, for initial states orthogonal to the eigenspaces of the unperturbed Grover walk corresponding to the eigenvalues ±1\pm1±1, we show that the perturbed dynamics is asymptotically described by a continuous-time quantum walk generated by this Hermitian matrix.