量子ウォーク

量子ウォーク()は、ランダムウォークの量子版と見なされるモデルである。
概要.
量子ウォークには離散時間量子ウォークと連続時間量子ウォークがあるが、ここでは離散時間量子ウォークについて述べる 。
離散時間量子ウォークのプライオリティーに関しては諸説あるが、少なくとも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)等を参照されたい 。
量子ウォークは、以下の全空間formula_1、その空間上の時間発展作用素formula_2、これらから決まる分布列formula_3 の3つから成り立っている 。但し、formula_4は時刻を表す 。
全空間.
量子ウォークの全空間はformula_5で定義される 。但し、formula_6
である 。このことからわかるように、ランダムウォークの場合は、中心極限定理により、標準偏差がformula_7のオーダーで発散するのに対して、量子ウォークではformula_4のオーダーで発散することがわかる 。さらに、大偏差原理を含む密度関数の境界付近に関する極限定理が砂田と楯(2012)によって得られている 。
局在化.
通常、高々有限個の場所で他と異なる左右への推移確率を持つコインによって定まるランダムウォークは、全ての場所で等しい左右への推移確率を持つコインによって定まるランダムウォークと同じ拡散的な（formula_7のオーダーの）拡がりのままである 。ところが、量子ウォークでは、ただ一か所だけ他と異なった量子コインを投入する場合でも、上述の線型的（formula_4のオーダーの）拡がりだけでなく、長時間極限において出発点付近の各点の存在確率が正の値を持つ、局在化と呼ばれる性質も共存するようになる
 。より具体的には、formula_11で局在化が起こるとは、
formula_12
が成り立つことであると、ここでは定義する 。但し、他にも量子ウォークの局在化の定義が存在する 。このような場合、下記の2段階の極限定理によって、線型的拡がりと局在化の共存が特徴づけられることが、多くの量子ウォークモデルにおいて知られている。
一段階目.
時間発展のユニタリ性などにより、一般に分布が時間に関して振動するので、局在化は下記のような分布の長時間平均をとることで証明されることが多い 。
formula_13
二段階目.
長時間平均測度formula_14を用いて、formula_15とおくと、formula_16となり、確率が保存されていない場合がある 。二段階目はその残りのformula_17に対応する以下の極限定理である 。
formula_18
但し、formula_19は下記のような密度関数を持つ 。
formula_20
ここで、実数formula_21と多項式formula_22はそれぞれの量子ウォークモデルに依存して決まる 。