量子ウォーク

量子ウォークには離散時間量子ウォークと連続時間量子ウォークがあるが、ここでは離散時間量子ウォークについて述べる 。

離散時間量子ウォークのプライオリティーに関しては諸説あるが、少なくともGudderによる本 (1988)^[1]の中に、既に現れている 。他にもAharonov et al. (1993)^[2]、Meyer (1996)^[3]などにより、量子情報、量子セルオートマトンの視点でそれぞれ独立に導入されている 。 また、Watrous (2001)^[4]では、一般のグラフ上での量子ウォークの原型にあたるものを見ることができる 。さらに、Severini (2002)^[5]には、より詳細で数学的な量子ウォークの構成が述べられている 。

量子情報の分野では、Shor (1994)^[6]、Grover (1996)^[7]により、それぞれ因数分解、探索問題に関する量子力学に基づいた超高速計算アルゴリズムが提案され、量子コンピュータの実効性が示された 。そのような中、Ambainis et al. (2001)^[8]によって、量子情報の観点から離散時間量子ウォークが扱われ、詳細な結果が得られたことが、量子ウォークが着目されるきっかけになったと考えられている 。実際に超高速計算を実現する量子探索では、量子ウォークがアルゴリズムの主要な一部分を担うことがある^[9] 。

現在では、グラフの同型問題^[10]、単位円周上の固有値解析^[11]、ランダムウォークとの統計的性質の比較^[12]、アンダーソン局在^[13][14]等が量子ウォークに関連付けられて盛んに議論されている 。さらに光格子^[15]、イオントラップ^[16]、光子^[17][18]などを用いて、量子ウォークを実験室で実現できることが、幾つかの研究グループによって報告されている 。より詳細な量子情報の観点からのレビューとしてVenegas-Andraca (2008)^[19]、(2012)^[20]が挙げられる 。また、日本語の解説書として今野(2008)^[21]、(2014)^[22]、町田(2018)^[23]、図解本として町田(2015)^[24]、プログラミングのための本として町田(2025)^[25]がある。

Summarize Timeline Top Qs Fact Check

ここでは、Gudder (1988)^[1]とMeyer (1996)^[3]に基づく一次元格子上の離散時間量子ウォークの定義を与える 。

一般のグラフに関する情報は、例えばAmbainis (2004)^[9]やその参考文献を辿ることで得られる 。説明の便宜上、Gudderが導入したモデルの修正版を導入するが、どれも本質的に等価である 。より詳細についてはKonno (2008)^[12]等を参照されたい 。

量子ウォークは、以下の全空間${\displaystyle {\mathcal {H}}}$、その空間上の時間発展作用素${\displaystyle U}$、これらから決まる分布列${\displaystyle \{\mu _{n}\}_{n=0,1,2,\ldots }}$ の3つから成り立っている 。ただし、${\displaystyle n}$は時刻を表す 。

量子ウォークの全空間は${\displaystyle {\mathcal {H}}={\mathcal {H}}_{P}\otimes {\mathcal {H}}_{C}}$で定義される 。ただし、${\displaystyle {\mathcal {H}}_{P}=\mathrm {Span} \{|x\rangle ;x\in \mathbb {Z} \}}$は粒子の場所を、${\displaystyle {\mathcal {H}}_{C}=\mathrm {Span} \{|J\rangle ;J\in \{L,R\}\}}$は粒子の自由度をそれぞれ表すヒルベルト空間である 。非自明な時間発展を与えるユニタリ作用素を定義するために、粒子の場所を記述する空間${\displaystyle {\mathcal {H}}_{P}}$に2次の自由度を持つ空間${\displaystyle {\mathcal {H}}_{C}}$が付随する^[3] 。

量子ウォークの時間発展作用素は${\displaystyle U=SC}$で定義される 。ここで、

${\displaystyle C=\bigoplus _{x\in \mathbb {Z} }H}$

はコイン作用素と呼ばれる作用素である 。ただし、${\displaystyle H}$は${\displaystyle {\mathcal {H}}_{C}}$上のユニタリ作用素で、量子コインと呼ばれる 。また、${\displaystyle S}$はシフト作用素と呼ばれる作用素で、

${\displaystyle S|x,J\rangle ={\begin{cases}|x+1,R\rangle &:J=R\\|x-1,L\rangle &:J=L\end{cases}}}$

を満たす 。ただし、${\displaystyle |x,J\rangle$ :=|x\rangle \otimes |J\rangle \in {\mathcal {H}}_{P}\otimes {\mathcal {H}}_{C}} である 。

量子ウォークでは、初期状態${\displaystyle \Psi _{0}\in {\mathcal {H}}}$（ただし、 ${\displaystyle ||\Psi _{0}||=1}$とする）を与え、以下のように${\displaystyle {\mathcal {H}}}$上のユニタリ作用素${\displaystyle U}$を繰り返し作用させる 。

${\displaystyle \Psi _{0}{\stackrel {U}{\mapsto }}\Psi _{1}{\stackrel {U}{\mapsto }}\Psi _{2}{\stackrel {U}{\mapsto }}\cdots }$

つまり、

${\displaystyle \Psi _{n}=U^{n}\Psi _{0}\quad (n=0,1,2,\ldots )}$

によって時間発展を定義する 。ここで、${\displaystyle U}$のユニタリ性からノルムが保存され、${\displaystyle ||\Psi _{n}||^{2}=1}$が全ての時刻${\displaystyle n=0,1,2,\ldots }$で成り立つ 。時刻${\displaystyle n}$での状態${\displaystyle \Psi _{n}}$の${\displaystyle x(\in \mathbb {Z} )}$成分を${\displaystyle {\boldsymbol {\Psi }}_{n}(x)={}^{T}[\Psi _{n}^{(L)}(x),\Psi _{n}^{(R)}(x)]}$と書くことにする 。 このとき、${\displaystyle \Psi _{n}^{(J)}(x)\in \mathbb {C} }$は量子ウォークの時刻${\displaystyle n\in \mathbb {N} }$、場所${\displaystyle x\in \mathbb {Z} }$、カイラリティ${\displaystyle J\in \{L,R\}}$の確率振幅と呼ばれる 。さらに、${\displaystyle |L\rangle ,|R\rangle \in {\mathcal {H}}_{C}}$を${\displaystyle |L\rangle \cong {}^{T}[1,0]}$、${\displaystyle |R\rangle \cong {}^{T}[0,1]}$ と表現したときの、量子コイン${\displaystyle H}$の行列表現を

${\displaystyle H={\begin{bmatrix}a&b\\c&d\end{bmatrix}}}$

として、${\displaystyle H=P+Q}$となるように

${\displaystyle P={\begin{bmatrix}a&b\\0&0\end{bmatrix}},\;Q={\begin{bmatrix}0&0\\c&d\end{bmatrix}},}$

を考えると、量子ウォークの時間発展と等価な表現として、

${\displaystyle {\boldsymbol {\Psi }}_{n}(x)=Q{\boldsymbol {\Psi }}_{n-1}(x-1)+P{\boldsymbol {\Psi }}_{n-1}(x+1)}$

が得られる 。これは、量子ウォークがランダムウォークの量子的類推と考えられる理由の一つである. つまり、左に遷移する際に行列${\displaystyle P}$の重みがかかり、逆に右に遷移する際に行列${\displaystyle Q}$の重みがかかると解釈するのである 。

量子ウォークの、時刻${\displaystyle n}$における分布${\displaystyle \mu _{n}:\mathbb {Z} \to [0,1]}$は以下のように定義される 。

${\displaystyle \mu _{n}(x)=\sum _{J\in \{L,R\}}|\langle x,J|U^{n}\Psi _{0}\rangle |^{2}.}$

ここで、${\displaystyle \mu _{n}}$は、時刻${\displaystyle n\in \mathbb {Z} }$、場所${\displaystyle x\in \mathbb {R} }$で粒子が見つかる確率を表している 。最近、この${\displaystyle \mu _{n}}$が実験的に実現されたことが報告されている^[15][17][16] 。