On the Ihara expression of graph zeta functions corresponding to quantum walks
概要
グラフゼータ函数の研究は,伊原[9]により定義された2×2p-進特殊線形群のある離散群の共役類の数え上げに関するゼータ函数(伊原ゼータ函数)の研究が発端である.当初,伊原ゼータ函数はグラフゼータ函数と解釈されていなかったが,Serre[17]によって,伊原ゼータ函数が正則グラフに対するゼータ函数であることが指摘され,その後,砂田[19]により伊原ゼータ函数のグラフ理論的解釈による定義が与えられた.この結果が発端となり,橋本,Bass,Bartholdi,そして今日までに水野,佐藤をはじめとする様々な研究者によって,多岐にわたるグラフゼータ函数が研究されている(cf.[1,2,7,14]).現在,グラフゼータ函数は様々な分野への応用にも用いられており,本論文の主題にもある量子ウォークにおいては,特に盛んに研究が行われている.そのきっかけは,量子ウォークにおいて非常に重要な定理であり,尚且つグラフゼータ函数と量子ウォークの関係を初めて明らかにした「今野-佐藤の定理」[12]である.この結果は,佐藤ゼータ函数[16]によってGroverウォーク[6]の遷移行列の特性多項式が得られることを示し,これにより遷移行列の固有値集合が与えられた.Groverウォークは量子ウォークの代表的なモデルの一つであり,数学のみならず,情報数学や量子物理などの分野でも広く興味が持たれている研究対象である.通常,量子ウォークの挙動を明らかにするには膨大な計算を行なう必要があるが,遷移行列の固有値が分かれば,局在化などの特徴的な挙動を突き止めることができる.ただし,扱うグラフや遷移行列が複雑であれば,計算もより複雑になってしまう.今野-佐藤の定理は,グラフが有限単純グラフであれば,どのようなグラフの上でもGroverウォークの挙動を特定することを可能にした.一方,佐藤ゼータ函数とはグラフゼータ函数の一つである.今野-佐藤の定理は,佐藤ゼータ函数が橋本表示,伊原表示という2種類の行列式を持つという結果が基盤にあって成り立っている.
Groverウォークには,その一般化の一つであるSzegedyウォーク[20]というモデルが考えられている.Szegedyウォークも,やはり様々な分野で研究されている量子ウォークモデルであり,その挙動の特定はどの分野でも興味を持たれている.しかし,Szegedyウォークの遷移行列の特性多項式や固有値集合を与えるような,今野-佐藤の定理のSzegedyウォークへの拡張は未だ得られていない.その一番の原因は,Groverウォークと対応関係をもつ佐藤ゼータ函数のように,Szegedyウォークに対応するようなグラフゼータ函数が知られていないことにある.そこで,本論文では,そのような対応関係を持つ「一般化佐藤ゼータ函数」を定義し,遷移行列の固有値集合を与えるのに必要な伊原表示を導出した.その結果を用いて,今野-佐藤の定理をSzegedyウォークへ拡張することに成功した.これにより,任意の有限グラフ上でのSzegedyウォークの遷移行列の固有値集合を与えることが可能となった.
一般化佐藤ゼータ函数の橋本表示は佐藤ゼータ函数と同様の方法で得られるが,伊原表示はその限りではない.それは,橋本表示が一般のグラフゼータ函数に対して定義され,その導出方法が確立されているのに対し,伊原表示は定義すら曖昧であり,導出方法も扱うグラフゼータ函数によって異なるからである,さらに,伊原表示に現れる行列は,有限無向グラフに一対一対応する対称有向グラフを扱うか,一般の有限有向グラフを扱うかにより異なることも知られている.伊原表示はこのように非常に曖昧な表示ではあるが,実はグラフゼータ函数でしか確認されていない表示であるため,グラフゼータ函数の応用では伊原表示を持つグラフゼータ函数が扱われている.扱うグラフやグラフゼータに依らない伊原表示を定義するには,まずは各グラフゼータにおいて,グラフに依らない「伊原表示の標準形」を導出する必要がある.本論文では,これまでの導出方法とは異なる,伊原表示の新しい導出方法を採用し,先行研究のどの伊原表示とも異なる形の「伊原表示」を導出した,この新しい導出方法はグラフに依存しない方法であり,さらに,この方法で得た伊原表示に現れる行列もグラフに依存しない.すなわち,本主定理では一般化佐藤ゼータにおける伊原表示の標準形を与えたと言える.
以降,各章節の内容を簡単に説明する.本章である第1章では,以降,ここで用いる記号や用語の定義を紹介する.第2章はグラフゼータ函数を指数表示で定義し,これがオイラー表示,橋本表示を持つことを示す.伊原表示に関しては,現状,具体的な荷重を持つグラフゼータ函数でなければ導出できていないため,先行研究のいくつかのグラフゼータ函数とその伊原表示を紹介する.それら伊原表示の導出については,先行研究のグラフゼータ函数を特別な場合に持つ「一般荷重ゼータ函数」を用いて一挙に証明する.主題であるSzegedyウォークに対応するグラフゼータ函数は,第3章で導入する.まず,有限無向グラフに対する対称有向グラフに対しての伊原表示を導出し,今野-佐藤の定理の拡張を行う.ここでの伊原表示の導出方法は,従来の方法に従う.その後,一般の有限有向グラフ上の一般化伊原ゼータ函数を扱う.新しい導出方法はここで採用する.さらに,有限無向グラフに対する対称有向グラフに対しての伊原表示を,改めて新しい方法により導出し,一般化伊原ゼータ函数の標準形を与える.
以下,単に「ゼータ」と言えばグラフゼータ函数を指すこととする.