量子ウォークのソースを表示

'''量子ウォーク'''({{lang-en-short|Quantum walk}})は、[[ランダムウォーク]]の量子版と見なされるモデルである。
==概要==
量子ウォークには離散時間量子ウォークと連続時間量子ウォークがあるが、ここでは離散時間量子ウォークについて述べる 。

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

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

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

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

一般のグラフに関する情報は、例えばAmbainis (2004)<ref name="Ambainis"/>やその参考文献を辿ることで得られる 。説明の便宜上、Gudderが導入したモデルの修正版を導入するが、どれも本質的に等価である 。より詳細についてはKonno (2008)<ref name="KonnoBook"/>等を参照されたい 。
 
量子ウォークは、以下の全空間<math> \mathcal{H} </math>、その空間上の時間発展作用素<math> U </math>、これらから決まる分布列<math> \{\mu_n\}_{n=0,1,2,\ldots } </math> の3つから成り立っている 。ただし、<math> n </math>は時刻を表す 。

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

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

<math> C=\bigoplus _{x\in \mathbb{Z}}H </math>

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

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

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

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

<math> \Psi_0\stackrel{U}{\mapsto}\Psi_1 \stackrel{U}{\mapsto}\Psi_2 \stackrel{U}{\mapsto} \cdots </math>

つまり、

<math> \Psi_n=U^n\Psi_0\quad (n=0,1,2,\ldots ) </math>

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

<math> H=\begin{bmatrix} a & b \\ c & d \end{bmatrix} </math>

として、<math> H=P+Q </math>となるように

<math> P=\begin{bmatrix} a & b \\ 0 & 0 \end{bmatrix},\;Q=\begin{bmatrix} 0 & 0 \\ c & d \end{bmatrix}, </math>

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

<math> \boldsymbol{\Psi}_n(x)=Q\boldsymbol{\Psi}_{n-1}(x-1)+P\boldsymbol{\Psi}_{n-1}(x+1) </math>

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

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

<math> \mu_n(x)= \sum_{J\in\{L,R\}}|\langle x,J|U^n\Psi_0\rangle|^2. </math>

ここで、<math> \mu_n </math>は、時刻<math> n\in \mathbb{Z} </math>、場所<math> x\in \mathbb{R} </math>で粒子が見つかる確率を表している 。最近、この<math> \mu_n </math>が実験的に実現されたことが報告されている<ref name="ExperimentOpt1D"/><ref name="ExperimentPhoton1D"/><ref name="ExperimentIon1D"/> 。


==量子ウォークの重要な性質==
===線型的拡がり===
量子ウォークの分布の統計的な性質に関しては、Konno (2008)<ref name="KonnoBook"/>等でその詳細を見ることができる 。例えば、Konno (2002)<ref name="Konno"/>・Konno (2005)<ref name="KonnoFull"/>によって、<math> X_n </math>を初期状態<math> \Psi_0=|0\rangle\otimes (\alpha|L\rangle +\beta|R\rangle) </math>から始めた量子ウォーク（ただし、<math>abcd \not= 0</math>）の時刻<math> n </math>での分布<math> \mu_n(x) </math>に従う確率変数とすると、

<math>
X_n/n\Rightarrow Y,\;\;(n\to \infty)
</math>

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

<math>
\left\{1-c(a,b;\alpha,\beta)x\right\}f_K(x;|a|).
</math>

ここで、

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

<math>
f_K(x;|a|)=\frac{|c|}{\pi (1-x^2)\sqrt{|a|^2-x^2}}\mathbf{1}_{\{x<|a|\}}(x),
</math>

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


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

<math>
\limsup_{n\to \infty} \mu_{n}(x) >0
</math>

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

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

<math>
\mu_*(x)=\lim_{n\to \infty}\frac{1}{T}\sum_{n=0}^{T-1}\mu_n(x)\geq 0.
</math>

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

<math>
X_n/n \Rightarrow Z \;\;(n\to\infty).
</math>

ただし、<math> Z </math>は下記のような密度関数を持つ 。

<math>
\nu(x)=c_*\delta_0(x)+(1-c_*)w(x)f_K(x;r).
</math>

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

==参考文献==
<references>
<ref name="Aharonov">Aharonov, Y., Davidovich, L., and Zagury, N. (1993). Quantum random walks, Phys. Rev. A 48, 1687-1690.</ref>
<ref name="Hanover">Ahlbecht, A., Scholz, V. B., and Werner, A. H. (2011). Disordered quantum walks in one lattice dimension, J. Math. Phys. 52, 102201</ref>
<ref name="Ambainis">Ambainis, A. (2004). Quantum walk algorithm for element distinctness, In Proc. of the 45th IEEE  Symposium on Foundations of Computer Science (FOCS), 22-31.</ref>
<ref name="AmbainisEtAl">Ambainis, A., Bach, E., Nayak, A., Vishwanath, A., and Watrous, J. (2001). One-dimensional quantum walks, In Proc. of the 33rd Annual ACM Symposium on the Theory of Computing (STOC), 37-49.</ref>
<ref name="CGMV">Cantero, M. J., Grünbaum, F. A., Moral, L., and Velázquez, L. (2010). Matrix valued Szegő polynomials and quantum random walks, Commun. Pure Appl. Math. 63, 464-507.</ref>
<ref name="Ems">Emms, D., Hancock, E. R., and Severini, S. (2006). A matrix representation of graphs and its spectrum as a graph invariant, Electr. J. Conmin. 13, R34.</ref>
<ref name="Grover">Grover, L. K. (1996). A fast quantum mechanical algorithm for database search. In Proc. of the 28th Annual ACM Symposium on the Theory of Computing (STOC), 212-219.</ref>
<ref name="Gudder">Gudder, S. P. (1988). Quantum Probability, Academic Press Inc., CA.</ref>
<ref name="Joye">Joye, A., and Merkli, M. (2010). Dynamical localization of quantum walks in random environments, J. Stat. Phys. 140, 1-29.</ref>
<ref name="ExperimentOpt1D">Karski, M. et al. (2009). Quantum walk in position space with single optically trapped atoms, Science 325, 174.</ref>
<ref name="Konno">Konno, N. (2002). Quantum random walks in one dimension, Quantum Information Processing 1, 245-354.</ref>
<ref name="KonnoFull">Konno, N. (2005). A new type of limit theorems for the one-dimensional quantum random walk, J. Math. Soc. Jpn. 57, 1179-1195.</ref>
<ref name="KonnoBook">Konno, N. (2008). Quantum Walks, In Quantum Potential Theory, Franz, U., and Schürmann, M., Eds., Lecture Notes in Mathematics, 1954, 309–452, Springer-Verlag, Heidelberg.</ref>
<ref name="K">Konno, N. (2010). Localization of an inhomogeneous discrete-time quantum walk on the line, Quantum Information Processing 9, 405-418.</ref>
<ref name="KLS">Konno, N., Luczak, T., and Segawa, E. (2013). Limit measures of inhomogeneous discrete-time quantum walks in one dimension, Quantum Information Processing 12, 33-53.</ref>
<ref name="Meyer">Meyer, D. A. (1996). From quantum cellular automata to quantum lattice gases, J. Statist. Phys. 85, 551-574.</ref>
<ref name="ExperimentPhoton1D">Schreiber, A. et al. (2010). Photons walking the line: A quantum walk with adjustable coin operations, Phys. Rev. Lett. 104, 050502.</ref>
<ref name="ExperimentPhoton2D">Schreiber, A. et al. (2012). A 2D quantum walk simulation of two-particle dynamics, Science 336, 55.</ref>
<ref name="Severini">Severini, S. (2002). The underlying digraph of a coined quantum random walk, Erato Conference in Quantum Information Science, 2003.</ref>
<ref name="Shor">Shor, P. W. (1994). Algorithms for quantum computation: Discrete logarithms and factoring, In Proc. of the 35th IEEE  Symposium on Foundations of Computer Science (FOCS), 124-134.</ref>
<ref name="TateSunada">Sunada, T., and Tate, T. (2012). Asymptotic behavior of quantum walks on the line, J. Funct. Anal. 262, 2608–2645.</ref>
<ref name="Venegas01">Venegas-Andraca, S. E. (2008). Quantum Walks for Computer Scientists, Morgan and Claypool.</ref>
<ref name="Venegas02">Venegas-Andraca, S. E. (2012). Quantum walks: a comprehensive review, Quantum Infotmation Processing 11, 1015-1106.</ref>
<ref name="KonnoSangyo">[[今野紀雄]] (2008). 量子ウォークの数理, 産業図書 ISBN 478280508X.</ref>
<ref name="KonnoMorikita">[[今野紀雄]] (2014). 量子ウォーク, 森北出版 ISBN 4627061617.</ref>
<ref name="Watrous">Watrous, J. (2001). Quantum simulations of classical random walks and undirected graph connectivity, Journal of Computer and System Sciences 62, 374-391.</ref>
<ref name="ExperimentIon1D">Zähringer, F. et al. (2010). Realization of a quantum walk with one and two trapped ions, Phys. Rev. Lett. 104, 100503.</ref>
<ref name="Machida2015">町田拓也 (2015). 図で解る量子ウォーク入門, 森北出版 ISBN 978-4627053816.</ref>
<ref name="Machida2018">町田拓也 (2018). 量子ウォーク －基礎と数理－, 裳華房 ISBN 978-4-7853-1576-4.</ref>
</references>

{{量子コンピュータ}}

==参考リンク==
*[https://soulstreet.web.fc2.com/quantumwalk/ 量子ウォーク]

{{デフォルトソート:りようしうおおく}}
[[Category:量子アルゴリズム]]
[[Category:数学に関する記事]]