グラフの幾何とスペクトルに関する諸問題 (デザイン、符号、グラフおよびその周辺)
雄介 樋口
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