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

数理解析研究所講究録

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

雄介 樋口

Published Jul 1, 2013• 0 citations
OpenAlex

Abstract

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] などの文献を 参照されたい．しかし，感覚的に語ることが許されるのであれば，次のように述べて

Related papers

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

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

Yusuke Higuchi, Norio Konno, Iwao Sato +1 more

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.

Interdisciplinary Information Sciences•Jan 1, 2017•26 citations

Spectral mapping theorem of an abstract quantum walk

Yusuke Higuchi, Etsuo Segawa, Akito Suzuki

Given two Hilbert spaces, $\mathcal{H}$ and $\mathcal{K}$, we introduce an abstract unitary operator $U$ on $\mathcal{H}$ and its discriminant $T$ on $\mathcal{K}$ induced by a coisometry from $\mathcal{H}$ to $\mathcal{K}$ and a unitary involution on $\mathcal{H}$. In a particular case, these operators $U$ and $T$ become the evolution operator of the Szegedy walk on a graph, possibly infinite, and the transition probability operator thereon. We show the spectral mapping theorem between $U$ and $T$ via the Joukowsky transform. Using this result, we have completely detemined the spectrum of the Grover walk on the Sierpiński lattice, which is pure point and has a Cantor-like structure.

arXiv:1506.06457•Jun 22, 2015•9 citations

Spectral and asymptotic properties of Grover walks on crystal lattice

Yusuke Higuchi, Norio Konno, Iwao Sato +1 more

We propose a twisted Szegedy walk for estimating the limit behavior of a discrete-time quantum walk on a crystal lattice, an infinite abelian covering graph, whose notion was introduced by [14]. First, we show that the spectrum of the twisted Szegedy walk on the quotient graph can be expressed by mapping the spectrum of a twisted random walk onto the unit circle. Secondly, we show that the spatial Fourier transform of the twisted Szegedy walk on a finite graph with appropriate parameters becomes the Grover walk on its infinite abelian covering graph. Finally, as an application, we show that if the Betti number of the quotient graph is strictly greater than one, then localization is ensured with some appropriated initial state. We also compute the limit density function for the Grover walk on $\mathbb{Z}^d$ with flip flop shift, which implies the coexistence of linear spreading and localization. We partially obtain the abstractive shape of the limit density function: the support is within the $d$-dimensional sphere of radius $1/\sqrt{d}$, and $2^d$ singular points reside on the sphere's surface.

arXiv:1401.0154•Dec 31, 2013•2 citations

On Quantum Walks on Finite Graphs I:Denition and Conditions

章 根岸, Akira Negishi

有限グラフ上の量子ウォークについて, 正準基底の存在を仮定せずに一般的な形式での定義を行う.

•Jan 1, 2012•0 citations

Spectral quantization of discrete random walks on half-line and orthogonal polynomials on the unit circle

Adam Doliwa, Artur Siemaszko

Abstract We define quantization scheme for discrete-time random walks on the half-line consistent with Szegedy's quantization of finite Markov chains. Motivated by the Karlin and McGregor description of discrete-time random walks in terms of polynomials orthogonal with respect to a measure with support in the segment [-1,1], we represent the unitary evolution operator of the quantum walk in terms of orthogonal polynomials on the unit circle. We find the relation between transition probabilities of the random walk with the Verblunsky coefficients of the corresponding polynomials of the quantum walk. We show that the both polynomials systems and their measures are connected by the classical Szegö map. Our scheme can be applied to arbitrary Karlin and McGregor random walks and generalizes the so called Cantero--Grünbaum--Moral--Velázquez method. We illustrate our approach on example of random walks related to the Jacobi polynomials. Then we study quantization of random walks with constant transition probabilities where the corresponding polynomials on the unit circle have two-periodic real Verblunsky coefficients. We present geometric construction of the spectrum of such polynomials (in the general complex case) which generalizes the known construction for the Geronimus polynomials. In the Appendix we present the explicit form, in terms of Chebyshev polynomials of the second kind, of polynomials orthogonal on the unit circle and polynomials orthogonal on the real line with coefficients of arbitrary period. 2010 Mathematics Subject Classification. 81P68, 05C81, 42C05, 94A11.

arXiv:2306.12265•Quantum Information Processing•Nov 25, 2024•0 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] などの文献を 参照されたい．しかし，感覚的に語ることが許されるのであれば，次のように述べて
Given two Hilbert spaces, H\mathcal{H}H and K\mathcal{K}K, we introduce an abstract unitary operator UUU on H\mathcal{H}H and its discriminant TTT on K\mathcal{K}K induced by a coisometry from H\mathcal{H}H to K\mathcal{K}K and a unitary involution on H\mathcal{H}H. In a particular case, these operators UUU and TTT become the evolution operator of the Szegedy walk on a graph, possibly infinite, and the transition probability operator thereon. We show the spectral mapping theorem between UUU and TTT via the Joukowsky transform. Using this result, we have completely detemined the spectrum of the Grover walk on the Sierpiński lattice, which is pure point and has a Cantor-like structure.
We propose a twisted Szegedy walk for estimating the limit behavior of a discrete-time quantum walk on a crystal lattice, an infinite abelian covering graph, whose notion was introduced by [14]. First, we show that the spectrum of the twisted Szegedy walk on the quotient graph can be expressed by mapping the spectrum of a twisted random walk onto the unit circle. Secondly, we show that the spatial Fourier transform of the twisted Szegedy walk on a finite graph with appropriate parameters becomes the Grover walk on its infinite abelian covering graph. Finally, as an application, we show that if the Betti number of the quotient graph is strictly greater than one, then localization is ensured with some appropriated initial state. We also compute the limit density function for the Grover walk on Zd\mathbb{Z}^dZd with flip flop shift, which implies the coexistence of linear spreading and localization. We partially obtain the abstractive shape of the limit density function: the support is within the ddd-dimensional sphere of radius 1/d1/\sqrt{d}1/d​, and 2d2^d2d singular points reside on the sphere's surface.
Abstract We define quantization scheme for discrete-time random walks on the half-line consistent with Szegedy's quantization of finite Markov chains. Motivated by the Karlin and McGregor description of discrete-time random walks in terms of polynomials orthogonal with respect to a measure with support in the segment [-1,1], we represent the unitary evolution operator of the quantum walk in terms of orthogonal polynomials on the unit circle. We find the relation between transition probabilities of the random walk with the Verblunsky coefficients of the corresponding polynomials of the quantum walk. We show that the both polynomials systems and their measures are connected by the classical Szegö map. Our scheme can be applied to arbitrary Karlin and McGregor random walks and generalizes the so called Cantero--Grünbaum--Moral--Velázquez method. We illustrate our approach on example of random walks related to the Jacobi polynomials. Then we study quantization of random walks with constant transition probabilities where the corresponding polynomials on the unit circle have two-periodic real Verblunsky coefficients. We present geometric construction of the spectrum of such polynomials (in the general complex case) which generalizes the known construction for the Geronimus polynomials. In the Appendix we present the explicit form, in terms of Chebyshev polynomials of the second kind, of polynomials orthogonal on the unit circle and polynomials orthogonal on the real line with coefficients of arbitrary period. 2010 Mathematics Subject Classification. 81P68, 05C81, 42C05, 94A11.