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

1 概要

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

2.1 全空間

2.2 時間発展

2.3 分布


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

3.1 線型的拡がり

3.2 局在化

3.2.1 一段階目

3.2.2 二段階目



4 参考文献

5 参考リンク

概要

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

離散時間量子ウォークのプライオリティーに関しては諸説あるが、少なくとも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]がある。
一次元格子上の量子ウォーク

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

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

量子ウォークは、以下の全空間 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}} が付随する[3] 。
時間発展

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

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

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

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

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

量子ウォークでは、初期状態 Ψ 0 ∈ H {\displaystyle \Psi _{0}\in {\mathcal {H}}} （但し、 。 。 Ψ 0 。