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

Interdisciplinary Information Sciences

Periodicity of the Discrete-time Quantum Walk on a Finite Graph

Yusuke Higuchi, Norio Konno, Iwao Sato, Etsuo Segawa

Published Jan 1, 2017• 26 citations
Publisher

Abstract

In this paper we discuss the periodicity of the evolution matrix of Szegedy walk, which is a special type of quantum walk induced by the classical simple random walk, on a finite graph. We completely characterize the periods of Szegedy walks for complete graphs, compete bipartite graphs and strongly regular graphs. In addition, we discuss the periods of Szegedy walk induced by a non-reversible random walk on a cycle.

DOI
10.4036/iis.2017.a.10

Related papers

Discrete-time semiclassical Szegedy quantum walks

Sergio A. Ortega, Miguel Angel Martin-Delgado

Quantum walks are promising tools based on classical random walks, with plenty of applications such as many variants of optimization. Here we introduce the semiclassical walks in discrete time, which are algorithms that combines classical and quantum dynamics. Specifically, a semiclassical walk can be understood as a classical walk where the transition matrix encodes the quantum evolution. We have applied this algorithm to Szegedy’s quantum walk, which can be applied to any arbitrary weighted graph. We first have solved the problem analytically on regular 1D cycles to show the performance of the semiclassical walks. Next, we have simulated our algorithm in a general inhomogeneous symmetric graph, finding that the inhomogeneity drives a symmetry breaking on the graph. Moreover, we show that this phenomenon is useful for the problem of ranking nodes in symmetric graphs, where the classical PageRank fails. We have demonstrated experimentally that the semiclassical walks can be applied on real quantum computers using the platform IBM Quantum.

arXiv:2303.18202•Physica A Statistical Mechanics and its Applications•Jul 8, 2023•5 citations

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

グラフの幾何とスペクトルに関する諸問題 (デザイン、符号、グラフおよびその周辺)

雄介 樋口

Among many kinds of approaches to study the relationship between geometry and spectra of graphs, in this note we focus on a kind of quantum walk, which is introduced by M. Szegedy, whose time evolution is induced by the transition probability of a random walk on a graph.In particular, we study the periodicity of the evolution operator of such a quantum walk by using spectral analysis and properies of the cyclotomic polynomials.This is ajoint work with Iwao Sato (Oyama National College of Technology).0. 序． 本講演の依頼を受けたとき，講演者である本稿の筆者は，従来より集中的に研究 してきた「無限グラフの幾何とスペクトル」についての話題提供を期待されている と思い，なおかつその話題で講演するつもりであった一方で，講演直前までに "面白 い " 話題が見つかったら方針変更できるように，上記のような大雑把なタイトルをつ けてしまった．実際には，ひよんなことから「有限グラフ上の量子ウォーク」のプ ロジエクトに参加することとなり，そこで当該研究集会に沿った (と個人的に考えて いる) 話題が提供可能となった．したがって講演および本稿は「有限グラフ上の量子 ウォークの evolution operator の性質」 にまつわる話題を提供することになり，それ により相応わしい題目としては「量子ウォークが周期をもつ有限グラフのいくつか の例」 (Some remarks on periodicity of discrete time quantum walks on finite graphs) であることをお詫びをかねてまずここにお伝えするものである． さて，量子ウオークは近年活発に研究されている対象であるが，残念ながら力不 足な筆者にはここで説明できるものではないので，興味のある方は，たとえば参考 文献に掲げた (十分ではないかも知れないが)[1,2,3,5,7,9,10,11,12,14] などの文献を 参照されたい．しかし，感覚的に語ることが許されるのであれば，次のように述べて

数理解析研究所講究録•Jul 1, 2013•0 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•9 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

Staggered quantum walks on graphs

Renato Portugal

The staggered quantum-walk model makes it possible to establish an unprecedented connection between discrete-time quantum walks and graph theory. We call attention to the fact that a large subclass of the coined model is included in Szegedy's model, which in its turn is entirely included in the staggered model. In order to compare those three quantum-walk models, we put them in the staggered formalism and show that the Szegedy and coined models are defined on a special subclass of graphs. This inclusion scheme is also true when the searching framework is added. We use graph theory to characterize which staggered quantum walks can be reduced to the Szegedy or coined quantum-walk model. We analyze a staggered-based search that cannot be included in Szegedy's model and show numerically that this search is more efficient than a random-walk-based search.

arXiv:1603.02210•Physical Review A•Jun 27, 2016•44 citations
In this paper we discuss the periodicity of the evolution matrix of Szegedy walk, which is a special type of quantum walk induced by the classical simple random walk, on a finite graph. We completely characterize the periods of Szegedy walks for complete graphs, compete bipartite graphs and strongly regular graphs. In addition, we discuss the periods of Szegedy walk induced by a non-reversible random walk on a cycle.
Quantum walks are promising tools based on classical random walks, with plenty of applications such as many variants of optimization. Here we introduce the semiclassical walks in discrete time, which are algorithms that combines classical and quantum dynamics. Specifically, a semiclassical walk can be understood as a classical walk where the transition matrix encodes the quantum evolution. We have applied this algorithm to Szegedy’s quantum walk, which can be applied to any arbitrary weighted graph. We first have solved the problem analytically on regular 1D cycles to show the performance of the semiclassical walks. Next, we have simulated our algorithm in a general inhomogeneous symmetric graph, finding that the inhomogeneity drives a symmetry breaking on the graph. Moreover, we show that this phenomenon is useful for the problem of ranking nodes in symmetric graphs, where the classical PageRank fails. We have demonstrated experimentally that the semiclassical walks can be applied on real quantum computers using the platform IBM Quantum.
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.
Among many kinds of approaches to study the relationship between geometry and spectra of graphs, in this note we focus on a kind of quantum walk, which is introduced by M. Szegedy, whose time evolution is induced by the transition probability of a random walk on a graph.In particular, we study the periodicity of the evolution operator of such a quantum walk by using spectral analysis and properies of the cyclotomic polynomials.This is ajoint work with Iwao Sato (Oyama National College of Technology).0. 序． 本講演の依頼を受けたとき，講演者である本稿の筆者は，従来より集中的に研究 してきた「無限グラフの幾何とスペクトル」についての話題提供を期待されている と思い，なおかつその話題で講演するつもりであった一方で，講演直前までに "面白 い " 話題が見つかったら方針変更できるように，上記のような大雑把なタイトルをつ けてしまった．実際には，ひよんなことから「有限グラフ上の量子ウォーク」のプ ロジエクトに参加することとなり，そこで当該研究集会に沿った (と個人的に考えて いる) 話題が提供可能となった．したがって講演および本稿は「有限グラフ上の量子 ウォークの evolution operator の性質」 にまつわる話題を提供することになり，それ により相応わしい題目としては「量子ウォークが周期をもつ有限グラフのいくつか の例」 (Some remarks on periodicity of discrete time quantum walks on finite graphs) であることをお詫びをかねてまずここにお伝えするものである． さて，量子ウオークは近年活発に研究されている対象であるが，残念ながら力不 足な筆者にはここで説明できるものではないので，興味のある方は，たとえば参考 文献に掲げた (十分ではないかも知れないが)[1,2,3,5,7,9,10,11,12,14] などの文献を 参照されたい．しかし，感覚的に語ることが許されるのであれば，次のように述べて
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.
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 staggered quantum-walk model makes it possible to establish an unprecedented connection between discrete-time quantum walks and graph theory. We call attention to the fact that a large subclass of the coined model is included in Szegedy's model, which in its turn is entirely included in the staggered model. In order to compare those three quantum-walk models, we put them in the staggered formalism and show that the Szegedy and coined models are defined on a special subclass of graphs. This inclusion scheme is also true when the searching framework is added. We use graph theory to characterize which staggered quantum walks can be reduced to the Szegedy or coined quantum-walk model. We analyze a staggered-based search that cannot be included in Szegedy's model and show numerically that this search is more efficient than a random-walk-based search.