量子ウォーク
ここでは、Gudder (1988)とMeyer (1996)に基づく一次元格子上の離散時間量子ウォークの定義を与える 。
一般のグラフに関する情報は、例えばAmbainis (2004)やその参考文献を辿ることで得られる 。説明の便宜上、Gudderが導入したモデルの修正版を導入するが、どれも本質的に等価である 。より詳細についてはKonno (2008)等を参照されたい 。
量子ウォークは、以下の全空間 H {\displaystyle {\mathcal {H}}} 、その空間上の時間発展作用素 U {\displaystyle U} 、これらから決まる分布列 { μ n } n = 0 , 1 , 2 , ... {\displaystyle \{\mu _{n}\}_{n=0,1,2,\ldots }} の3つから成り立っている 。但し、 n {\displaystyle n} は時刻を表す 。
量子ウォークの全空間は H = H P ⊗ H C {\displaystyle {\mathcal {H}}={\mathcal {H}}_{P}\otimes {\mathcal {H}}_{C}} で定義される 。但し、 H P = S p a n { | x ⟩ ; x ∈ Z } {\displaystyle {\mathcal {H}}_{P}=\mathrm {Span} \{|x\rangle ;x\in \mathbb {Z} \}} は粒子の場所を、 H C = S p a n { | J ⟩ ; J ∈ { L , R } } {\displaystyle {\mathcal {H}}_{C}=\mathrm {Span} \{|J\rangle ;J\in \{L,R\}\}} は粒子の自由度をそれぞれ表すヒルベルト空間である 。非自明な時間発展を与えるユニタリ作用素を定義するために、粒子の場所を記述する空間 H P {\displaystyle {\mathcal {H}}_{P}} に2次の自由度を持つ空間 H C {\displaystyle {\mathcal {H}}_{C}} が付随する 。
量子ウォークでは、初期状態 Ψ 0 ∈ H {\displaystyle \Psi _{0}\in {\mathcal {H}}} (但し、 | | Ψ 0 | | = 1 {\displaystyle ||\Psi _{0}||=1} とする)を与え、以下のように H {\displaystyle {\mathcal {H}}} 上のユニタリ作用素 U {\displaystyle U} を繰り返し作用させる 。
Ψ 0 ↦ U Ψ 1 ↦ U Ψ 2 ↦ U ⋯ {\displaystyle \Psi _{0}{\stackrel {U}{\mapsto }}\Psi _{1}{\stackrel {U}{\mapsto }}\Psi _{2}{\stackrel {U}{\mapsto }}\cdots }
つまり、
Ψ n = U n Ψ 0 ( n = 0 , 1 , 2 , ... ) {\displaystyle \Psi _{n}=U^{n}\Psi _{0}\quad (n=0,1,2,\ldots )}
によって時間発展を定義する 。ここで、 U {\displaystyle U} のユニタリ性からノルムが保存され、 | | Ψ n | | 2 = 1 {\displaystyle ||\Psi _{n}||^{2}=1} が全ての時刻 n = 0 , 1 , 2 , ... {\displaystyle n=0,1,2,\ldots } で成り立つ 。