Analysis of quantum walks on finite graphs

概要

博士論文
有限グラフ上の量子ウォークの解析
（Analysis of quantum walks on finite graphs）
横浜国立大学大学院
理工学府
齋藤 渓
（SAITO KEI）
学位授与 2020 年・3 月

目次
1

序文

1

2

有限グラフ上の量子ウォークの構成

3

有限グラフ上の split-step 量子ウォーク . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

12

量子ウォークの周期性

17

3.1

Grover walk における周期性 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

17

3.2

Fourier walk における周期性 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

18

3.3

自己ループ付きサイクルグラフ上の量子ウォーク . . . . . . . . . . . . . . . . . . . . . . . .

27

量子ウォークのスペクトル写像定理

31

量子ウォークの長時間平均分布 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

44

サイクル上の量子ウォークの二相系

49

2.1
3

4
4.1
5

1 序文
量子ウォークの起源は諸説があるが，20 世紀の終わりごろに量子コンピューターに代表される科学技術の
発展と共に脚光を浴び始めたことは確かである．種々の量子アルゴリズムへの応用，とりわけ Grover のアル
ゴリズムを模倣した量子探索は量子ウォークの主たる活躍の舞台であり，現在もなお様々な研究が行われてい
る [1, 2, 3, 4, 5, 6] ．量子ウォークはランダムウォークの量子版とも呼ばれる数理モデルであり，シンプルな
量子動力学を表すモデルとして量子計算や量子情報科学などといった分野への応用研究もまた盛んである．
量子ウォークのモデルは大きく分けて離散時間・連続時間のものが存在するが，本稿においては離散時間の
モデルのみを取り扱う．特に，離散時間の量子ウォークの中でもコイン型モデル，bipartite モデル，staggered
モデルなど様々なモデルが提唱されているが，本稿においては最も広く知られているコイン型モデルのみを扱
う．
ここで，Konno [7] などで定められる整数格子 Z 上の量子ウォークのモデルを 1 つ紹介する．まず，量子
ウォークが作用する量子系の状態空間を次のような二乗総和可能な関数からなるヒルベルト空間 H で与える．

(

H = ℓ2 (Z; C2 ) =

Ψ : Z → C2 |

X

)

∥Ψ(x)∥2 < ∞ .

x∈Z

次に 2 × 2 のユニタリ行列 Cloc を与え，これを各行ごとに分割したものを P, Q とする．すなわち，以下のよ
うに定める．



Cloc


a b
=
∈ U(2),
c d



a
P =
0


b
,
0




0 0
Q=
.
c d

ただし，U(n) は n × n のユニタリ行列全体の集合を意味する．時刻 t ∈ Z≥ における量子状態を Ψt ∈ H と
し，その時間発展を

Ψt+1 (x) = P Ψt (x + 1) + QΨt (x − 1),

∀x ∈ Z

(1)

によって定義する．このように時間発展により隣接頂点へと値を移す Ψt (x) はランダムウォークとの対応か
ら量子ウォーカーの持つ状態ベクトルと呼ばれ，行列 P, Q は量子ウォーカーが隣接する頂点へと推移する際
の重み行列と捉えられる．ここで (1) 式の時間発展を H 上の 2 つのユニタリ作用素 S, C によって分割する．
任意の Ψ ∈ H, x ∈ Z に対し S, C の作用を





1 0
0
(SΨ)(x) =
Ψ(x + 1) +
0 0
0


0
Ψ(x − 1),
1

(CΨ)(x) = Cloc Ψ(x)

のように定めれば，確かに (SCΨ)(x) が (1) 式の左辺における Ψt+1 (x) に対応することがわかる．このよう
に，時間発展がシフトオペレーター S とコインオペレーター C の積によって与えられるもの，すなわち時間
発展作用素 U = SC で定められる量子ウォークが一般にコイン型モデルと呼ばれるものである．
もう 1 つ，典型的な量子ウォークのモデルである Grover walk を紹介する．Grover walk はその拡張も
含め，一般の対称グラフ G = (V, E) 上を量子ウォーカーが推移するモデルとして頻繁に研究されている

[11, 12, 13, 14, 15, 16, 17] ．このモデルにおいて，辺集合 E から導出される対称な有向辺全体の集合 A とし
たとき，すなわち

A = {(u, v), (v, u) | uv ∈ E}
1

としたとき，Grover walk における状態空間を与えるヒルベルト空間は

H = ℓ2 (A)
によって与えられる．ここで，e ∈ A に対し t(e) で有向辺 e の終点，o(e) で e の始点を与えるものとし，e¯ で
逆辺を表す．そして，Grover walk における時間発展作用素 U は Ψ ∈ H に対し

(U Ψ)(e) =

X



f | t(f )=o(e)

2
− δe¯,f
deg(t(f ))


Ψ(f )

(2)

によって定められる．ただし，deg(·) は頂点の次数であり，δe,f はクロネッカーのデルタである．
実は (2) 式で与えた Grover walk も S と C の積により書き表すことができるコイン型モデルの一種であ
る．また，最初に紹介した Z 上の量子ウォークは頂点上に値を取るヒルベルト空間の上で定義されたのに対
し，Grover walk は有向辺の上に値を取る空間の上で定義された．これも実は，頂点上に値を取るモデルと有
向辺の上に値を取るモデルはある対応を与えることで本質的に同値なものとして解釈することができる．その
ような対応関係も含め，本論文の導入として一般的な有限グラフ上におけるコイン型量子ウォークの構成を第

2 章にて与える．なお，この構成法については Higuchi, Konno, Sato, Segawa [9] を参考に本論文にて必要と
なる種々の記号を付け加え拡張したものである．
第 2 章以降は，グラフ上の量子ウォークについていくつかのトピックを単発的に取り扱う．
まず，第 3 章においては量子ウォークの周期性についての研究を紹介する．周期性とは一定時刻ごとに量子状
態が初期状態へと完全に再帰する性質であり，古典系であるランダムウォークには存在しえない量子ウォーク
特有の性質である1 ．量子ウォークの周期によるグラフの特徴づけを用いたグラフ同型問題への応用や，完全
状態遷移（perfect state transfer）といった現象との関連なども研究されている [18, 19, 20, 21, 22, 23, 24] ．
特に筆者により得られた Fourier walk と呼ばれるモデルにおける結果（定理 3.3）は隣接行列という代数的グ
ラフ理論の道具を用いて量子ウォークの周期性の有無を判定することを可能とした定理であり，既存の周期性
の研究とは全く異なるアプローチにより得られたことからも本論文の主定理の 1 つとして大きな意義を持つ．
第 4 章は Suzuki, Segawa [25, 26] などで与えられる量子ウォークのスペクトル写像定理の導入を行う．ス
ペクトル写像定理はいくつかの条件が課されたモデルに対して適用可能な定理であり，量子ウォークが作用す
るヒルベルト空間よりも低次元の空間上で与えられる自己共役作用素 T のスペクトルから時間発展作用素 U
のスペクトルを導き出す定理である．特に，Grover walk においては T は対応するグラフ上の対称ランダム
ウォークと一致するため，量子系と古典系を繋ぐ非常に重要な定理として知られている．また，スペクトル写
像定理の強力な点は，定理を適用可能となる条件を満たした上であれば，頂点に依存したダイナミクスを持つ
量子ウォークの解析も可能となる点である．一般にそのようなモデルは Fourier 解析を用いることができない
など，よく知られた研究手法によって解析することは難しい．続く第 5 章においては，このスペクトル写像定
理を用いることにより，サイクル上の量子ウォークの二相系の固有値解析を行う．

1

量子ウォークの時間発展作用素はユニタリであるため，多くのランダムウォークと違い収束することがない．したがって状態が周
期的に再帰することも有り得る．

2

2 有限グラフ上の量子ウォークの構成
本章では有限グラフ上の一般的なコイン型量子ウォーク2 の定義を記す．ここで記す量子ウォークモデルの
構成法は，Higuchi, Konno, Sato, Segawa [9] で与えられた方法を基にし，本論文において必要となる記号を
付け加えたものである．
本稿では，多重辺を持たない有限な無向グラフを対象とする．すなわち，グラフ G = (V, E) に対し，

(1) 任意の頂点 u, v ∈ V に対して，uv ∈ E であれば辺 e = uv ∈ E が一意に定まる．
(2) 頂点数が有限である．すなわち |V | < ∞．
を満たし，辺が指向性を持たない場合を考える3 ．ここで，辺集合 E から導出される対称な有向辺（arc）全体
の集合 A を以下で与える．

A := {(u, v), (v, u) | uv ∈ E, u ̸= v} ∪ {(u, v) | uv ∈ E, u = v}.
さらに，有向辺 e = (u, v), u, v ∈ V に対し，始点（origin）と終点（terminus）をそれぞれ

o(e) = v,

t(e) = u

とし，逆辺を e¯ = (v, u) と表記する．これらについては第 1 章にて記述したものと同じ記号である．
多くの先行研究においてグラフ上の量子ウォークは各有向辺上に複素数値を与える関数空間上のダイナミク
スとして定義されるが，多次元正方格子，半直線などといった対称性の良いグラフに対しては頂点上にベク
トル値を与える形で記述されることが多い．後述するようにこれらは同一のモデルとして対応付けられるが，
扱う問題や設定に応じて使い分けることが重要である．まず初めにこれらの対応を与える写像について記述
する．
量子ウォークを有向辺上のダイナミクスとして考える場合は以下のヒルベルト空間 HA を量子系の状態空
間とする．

(
HA = ℓ (A) =
2

Ψ:A→C|

X

)
|Ψ(e)| < ∞ .
2

(3)

e∈A

これに対し，各頂点毎にそれを終点とする有向辺上の値を並べることで各頂点上にベクトル値を与えることが
できる．ここで，ベクトルの定め方に一意性を与えるため次のラベリング L を与える．
定義 2.1. ラベリング L :

L : A → Z≥0
ただし，L は以下を満たす．

(i) 任意の e, f ∈ A (e ̸= f ) に対し t(e) = t(f ) であれば L(e) ̸= L(f ).
S
(ii) 任意の v ∈ V に対し e | t(e)=v {L(e)} = {0, 1, · · · , deg(v) − 1}.
2
3

序文で述べたように，時間発展が U = SC によるシフト・コインオペレーターの積で定義されるモデルのことを指す．
多重辺については許容したモデルを考えることもできるがここでは扱わない．また，無限グラフを扱う場合は以後の議論における
固有値を一般的なスペクトルへと分類する必要があるなどいくつかの修正を要する．

3

deg(v) は頂点 v の次数4 ，すなわち頂点 v から出る辺の総本数である．したがって，L とは各頂点ごとに，
それを終点とする有向辺それぞれに 0∼deg(v) − 1 の番号付けを与えるものである．
次に，量子ウォークを頂点上のダイナミクスとして考える場合は以下のヒルベルト空間 HV を量子系の状
態空間とする．

HV =

M

ℓ2 (v ; Cdeg(v) ).

(4)

v∈V

このとき，上で定めたラベリングを用いることで次の対応が与えられる．
定義 2.2. 有向辺ベース ↔ 頂点ベースの対応 : 定義 2.1 で与えられた L に対し，作用素 ι : HA → HV を以
下で与える．

X

˜
(ιΨ)(v)
=

˜
Ψ(e)
|L(e)⟩,

˜ ∈ HA , v ∈ V.
∀Ψ

e | t(e)=v

ただし，|L(e)⟩ は Cdeg(t(e)) の標準基底ベクトルとして定める．すなわち，
0 行目

1 行目

 z}|{ z}|{
0
0
··· 0
|L(e)⟩ =

L(e) 行目

deg t(e)−1 行目

z}|{
1

T

0 ···

z}|{
0



∈ Cdeg(t(e)) .

また，ベクトルの左上添え字の T は転置を意味する．このとき逆作用 ι−1 は以下となる．
系 2.3. 定義 2.2 で与えられた ι に対し，逆作用 ι−1 : HV → HA は以下となる．

(ι−1 Ψ)(e) = ⟨L(e)|Ψ(t(e)),

∀Ψ ∈ HV , e ∈ A.

証明. まず，Ψ ∈ HV に対し，

(ιι−1 Ψ)(v) =

X

|L(e)⟩(ι−1 Ψ)(e)

e | t(e)=v

=

X

|L(e)⟩⟨L(e)|Ψ(t(e))

e | t(e)=v

であり，L の定義から

S

e | t(e)=v {L(e)}
5

= {0, 1, · · · , deg(v) − 1} であるので

P
e | t(e)=v

|L(e)⟩⟨L(e)| = I で

ある．ただし，I は単位行列を表す ．したがって

(ιι−1 Ψ)(v) = Ψ(v)
˜ ∈ HA に対し，
が成り立つ．次に，Ψ
˜
˜
(ι−1 ιΨ)(e)
= ⟨L(e)|(ιΨ)(t(e))
X
˜ )|L(f )⟩
= ⟨L(e)|
Ψ(f
f | t(f )=t(e)

=

X

˜ ).
⟨L(e), L(f )⟩Ψ(f

f | t(f )=t(e)
4
5

本論文では自己ループについては次数を 1 本分と計上する．
本論文中においては I を単位行列の意味でも，恒等作用素の意味でも同一な記号を使用するが，これらは本質的に同じものである．
また，その行列のサイズ，および定義域については適宜文脈によって判断されたい．

4

これも L の定義から t(e) = t(f ), e ̸= f であれば L(e) ̸= L(f ) であるため，⟨L(e), L(f )⟩ = δe,f である．た
だし，δe,f はクロネッカーのデルタ，すなわち δe,f = 1 (e = f ), = 0 (e ̸= f ) である．したがって

˜
˜
(ι−1 ιΨ)(e)
= Ψ(e).

このように ι は全単射であるため，確かに HA と HV は同型であることがわかる．本稿では HA 上で与え
られるダイナミクスを有向辺ベース，HV 上で与えられるダイナミクスを頂点ベースと記述する．
本稿にて扱う離散時間コイン型量子ウォークとは時間発展作用素が HA あるいは HV 上のユニタリ作用素
であるシフトオペレーターとコインオペレーターの積によって与えられるモデルを指す．頂点ベースの表記と
して，HV 上の時間発展作用素 U を同じく HV 上の作用素であるシフトオペレーター S とコインオペレー
ター C の積で定める．すなわち

U = SC.
˜ を同様にシフトオペレーター S˜ とコイ
これに対し，有向辺ベースの記述として，HA 上の時間発展作用素 U
˜ の積で定める．ただし，
ンオペレーター C
S˜ = ιSι−1 ,

C˜ = ιCι−1 ,

(5)

˜
S = ι−1 Sι,

˜
C = ι−1 Cι,

(6)

すなわち

の関係で与えられるものとする．これらを以下にまとめておく．
定義 2.4. 時間発展作用素 :

• 頂点ベース HV 上の時間発展作用素 :

U = SC.
˜ = S˜C.
˜
• 有向辺ベース HA 上の時間発展作用素 : U
˜ = ι−1 Xι (X = U, S, C) であり，S, S,
˜ C, C˜ はそれぞれ定義 2.10，定義 2.7，定義 2.11，定義 2.12
ただし，X
で与えられる．
以下，シフトオペレーター及びコインオペレーターの定義をそれぞれ記述する．特に，シフトオペレーター
については有向辺ベースのシフトオペレーター S˜ の定義を初めに与え，(6) の関係を用いることで頂点ベース
のシフトオペレーター S の定義を与える．また，それとは逆に，コインオペレーターについては頂点ベースの

˜ を定める．
コインオペレーター C の定義を先に与え，(5) の関係から有向辺ベースのコインオペレーター C
• シフトオペレーター
グラフ上の量子ウォークは後述する flip-flop shift と呼ばれるシフトオペレーターを定めるのが典型的だが，
一般の場合におけるシフトオペレーターは次のような有向辺の集合 A の分割 Π によって構成される．
定義 2.5. 有向辺の分割 Π :

Π = {Π1 , Π2 , · · · , Πr },
ただし，これは以下を満たす：

5

r ∈ N,

Πi ⊂ A.

(i)

Sr
i=1

Πi = A.

(ii) Πi ∩ Πj = ∅,
(iii) Πi =

i ̸= j.

{ei0 , ei1 , · · ·

, ein−1 } に対し，t(eij ) = o(eij+1

mod n )

かつ j ̸= k のとき eij ̸= eik .

ここで (iii) の条件は各 Πi が素な向き付きの閉歩道であることを意味している6 ．(i) および (ii) の条件か
ら，Π が与えられたとき任意の e ∈ A はいずれかの Πi に含まれ，それも一意であることがわかる．したがっ
て，以下のような全単射が自然に定義される．
定義 2.6. 定義 2.5 で与えられた Π に対し，任意の e ∈ A に対し，e = eij ∈ Πi = {ei0 , ei1 , · · · , ei|Πi | } を満た
す i, j が一意に存在する．このとき，全単射 τ : A → A を以下で定める．

τ (e) = eij+1

∀e = eij ∈ Πi .

mod |Πi | ,

(7)

これを用いて，有向辺ベースのシフトオペレーター S˜ を次で定める．
定義 2.7. シフトオペレーター（有向辺ベース） : 定義 2.5，定義 2.6 で定められた Π, τ に対し HA 上のユ
ニタリ作用素 S˜ を以下で定める．

˜
˜ −1 (e)),
(S˜Ψ)(e)
= Ψ(τ

˜ ∈ HA , e ∈ A.
∀Ψ

このように分割 Π を与えることで自動的にシフトオペレーターが定められるが，任意のグラフに対して “自
然な”量子ウォークモデルを構成するためにはどのように Π を与えればよいか？という問題に直面する．その
解答の 1 つとしては，各辺ごとに Πi を与える分割が考えられる．すなわち，r = |Π| = |E| であり，任意の辺

ei の端点を ui , vi ∈ V (ui ̸= vi ) としたとき
Πi = {(ui , vi ), (vi , ui )},

ei = ui vi ∈ E,

ui ̸= vi

(8)

を与え，ui = vi ，すなわち ei が自己ループである場合は

Πi = {(ui , vi )},

ei = ui vi ∈ E,

u i = vi

(9)

として与える．この分割は任意のグラフに対して与えることができ，しかも一意であることから自然な分割で
あると言える．この分割の下では任意の e ∈ A に対し τ (e) = τ −1 (e) = e¯ が成り立ち，これにより定義される
シフトは flip-flop shift と呼ばれる．
定義 2.8. flip-flop shift : (8)(9) で定められた Π に対し，定義 2.7 で与えられる有向辺ベースのシフトオ
ペレーターを S˜ = S˜ff と記述する．このとき

˜ ∈ HA , e ∈ A.
∀Ψ

˜
˜ e),
(S˜ff Ψ)(e)
= Ψ(¯

また，頂点ベースの flip-flop シフトについても Sff = ιS˜ff ι−1 で定める．
系 2.9. S˜ff2 = I, Sff2 = I.

˜ ∈ HA に対し，(S˜2 Ψ)(e)
˜
˜ e) = Ψ(e)
˜
証明. 任意の Ψ
= (S˜ff Ψ)(¯
であるため，S˜ff2 = I である．したがって，
ff
Sff2 = ιS˜ff2 ι−1 = I も明らかである．
6

無限グラフを扱う場合は素な無限長のパスも許容する．例えばパスグラフ（整数格子 Z）上の moving-shift と呼ばれる典型的な
量子ウォークは正方向・負方向の 2 本の長さ無限長のパスによって分割される．

6

他にも自然な分割の与え方としては，向き付け可能な閉曲面に埋め込まれたグラフに対して，各領域毎に

Πi を対応させるなど考えられる．
定義 2.7 により有向辺ベースのシフトオペレーターが与えられたことで，これを用いて頂点ベースのシフト
オペレーター S が以下で与えられる．
定義 2.10. シフトオペレーター（頂点ベース） : 定義 2.7 で与えられた S˜ に対し，HV 上のユニタリ作用素

˜ −1 を定める．このとき，S は以下によって与えられる．
S = ιSι
X
(SΨ)(v) =
|L(v, u)⟩⟨L(τ −1 (v, u))| Ψ(u),

∀Ψ ∈ HV , v ∈ V.

u | uv∈E

証明. Ψ ∈ HV に対し，系 2.3 から任意の e ∈ A に対して

(ι−1 Ψ)(e) = ⟨L(e)|Ψ(t(e))
˜ −1 Ψ)(e) = (ι−1 Ψ)(τ −1 (e)) であるので
であり，S˜ の定義から (Sι
˜ −1 Ψ)(e) = ⟨L(τ −1 (e))|Ψ(t(τ −1 (e))).
(Sι
したがって，任意の v ∈ V に対して

˜ −1 Ψ)(v)
(SΨ)(v) = (ιSι
X
=
|L(e)⟩(Sι−1 Ψ)(e)
e | t(e)=v

X

=

|L(e)⟩⟨L(τ −1 (e))|Ψ(t(τ −1 (e))). ...