量子ウォーク

量子ウォーク(英: Quantum walk)は、ランダムウォークの量子版と見なされるモデルである。

概要

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

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

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

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

一次元格子上の量子ウォーク

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

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

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

全空間

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

時間発展

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

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

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

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

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

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

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

つまり、

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

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

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

として、$H=P+Q$となるように

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

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

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

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

分布

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

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

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

量子ウォークの重要な性質

線型的拡がり

量子ウォークの分布の統計的な性質に関しては、Konno (2008)等でその詳細を見ることができる 。例えば、Konno (2002)・Konno (2005)によって、$X_{n}$を初期状態$\Psi _{0}=|0\rangle \otimes (\alpha |L\rangle +\beta |R\rangle )$から始めた量子ウォーク（但し、$abcd\not =0$）の時刻$n$での分布$\mu _{n}(x)$に従う確率変数とすると、

$X_{n}/n\Rightarrow Y,\;\;(n\to \infty )$

が成立することが示されている 。 但し、$Y$は以下のような密度関数を持つ確率変数である 。

$\left\{1-c(a,b;\alpha ,\beta )x\right\}f_{K}(x;|a|).$

ここで、

$c(a,b;\alpha ,\beta )=|\alpha |^{2}-|\beta |^{2}+{\frac {2\mathrm {Re} (a\alpha {\overline {b\beta }})}{|a|^{2}}},$

$f_{K}(x;|a|)={\frac {|c|}{\pi (1-x^{2}){\sqrt {|a|^{2}-x^{2}}}}}\mathbf {1} _{\{x<|a|\}}(x),$

である 。このことからわかるように、ランダムウォークの場合は、中心極限定理により、標準偏差が${\sqrt {n}}$のオーダーで発散するのに対して、量子ウォークでは$n$のオーダーで発散することがわかる 。さらに、大偏差原理を含む密度関数の境界付近に関する極限定理が砂田と楯(2012)によって得られている 。

局在化

通常、高々有限個の場所で他と異なる左右への推移確率を持つコインによって定まるランダムウォークは、全ての場所で等しい左右への推移確率を持つコインによって定まるランダムウォークと同じ拡散的な（${\sqrt {n}}$のオーダーの）拡がりのままである 。ところが、量子ウォークでは、ただ一か所だけ他と異なった量子コインを投入する場合でも、上述の線型的（$n$のオーダーの）拡がりだけでなく、長時間極限において出発点付近の各点の存在確率が正の値を持つ、局在化と呼ばれる性質も共存するようになる 。より具体的には、$x\in \mathbb {Z}$で局在化が起こるとは、

$\limsup _{n\to \infty }\mu _{n}(x)>0$

が成り立つことであると、ここでは定義する 。但し、他にも量子ウォークの局在化の定義が存在する 。このような場合、下記の2段階の極限定理によって、線型的拡がりと局在化の共存が特徴づけられることが、多くの量子ウォークモデルにおいて知られている。

一段階目

時間発展のユニタリ性などにより、一般に分布が時間に関して振動するので、局在化は下記のような分布の長時間平均をとることで証明されることが多い 。

$\mu _{*}(x)=\lim _{n\to \infty }{\frac {1}{T}}\sum _{n=0}^{T-1}\mu _{n}(x)\geq 0.$

二段階目

長時間平均測度$\mu _{*}(x)$を用いて、$c_{*}\equiv \sum _{x}\mu _{*}(x)$とおくと、$0\leq c_{*}<1$となり、確率が保存されていない場合がある 。二段階目はその残りの$1-c_{*}$に対応する以下の極限定理である 。

$X_{n}/n\Rightarrow Z\;\;(n\to \infty ).$

但し、$Z$は下記のような密度関数を持つ 。

$\nu (x)=c_{*}\delta _{0}(x)+(1-c_{*})w(x)f_{K}(x;r).$

ここで、実数$0<r<1$と多項式$w(x)$はそれぞれの量子ウォークモデルに依存して決まる 。

参考リンク

• 量子ウォーク