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

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

離散時間量子ウォークのプライオリティーに関しては諸説あるが、少なくとも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]等を参照されたい 。

量子ウォークは、以下の全空間${\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] 。

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

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

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

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

ここで、

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

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

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

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

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

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

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

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

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

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

ただし、${\displaystyle Z}$は下記のような密度関数を持つ 。

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

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

1. ^ ^{a b} Gudder, S. P. (1988). Quantum Probability, Academic Press Inc., CA.
2. ^ Aharonov, Y., Davidovich, L., and Zagury, N. (1993). Quantum random walks, Phys. Rev. A 48, 1687-1690.
3. ^ ^{a b c} Meyer, D. A. (1996). From quantum cellular automata to quantum lattice gases, J. Statist. Phys. 85, 551-574.
4. ^ Watrous, J. (2001). Quantum simulations of classical random walks and undirected graph connectivity, Journal of Computer and System Sciences 62, 374-391.
5. ^ Severini, S. (2002). The underlying digraph of a coined quantum random walk, Erato Conference in Quantum Information Science, 2003.
6. ^ 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.
7. ^ 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.
8. ^ 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.
9. ^ ^{a b} Ambainis, A. (2004). Quantum walk algorithm for element distinctness, In Proc. of the 45th IEEE Symposium on Foundations of Computer Science (FOCS), 22-31.
10. ^ 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.
11. ^ 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.
12. ^ ^{a b c} 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.
13. ^ ^{a b} Joye, A., and Merkli, M. (2010). Dynamical localization of quantum walks in random environments, J. Stat. Phys. 140, 1-29.
14. ^ ^{a b} Ahlbecht, A., Scholz, V. B., and Werner, A. H. (2011). Disordered quantum walks in one lattice dimension, J. Math. Phys. 52, 102201
15. ^ ^{a b} Karski, M. et al. (2009). Quantum walk in position space with single optically trapped atoms, Science 325, 174.
16. ^ ^{a b} Zähringer, F. et al. (2010). Realization of a quantum walk with one and two trapped ions, Phys. Rev. Lett. 104, 100503.
17. ^ ^{a b} Schreiber, A. et al. (2010). Photons walking the line: A quantum walk with adjustable coin operations, Phys. Rev. Lett. 104, 050502.
18. ^ Schreiber, A. et al. (2012). A 2D quantum walk simulation of two-particle dynamics, Science 336, 55.
19. ^ Venegas-Andraca, S. E. (2008). Quantum Walks for Computer Scientists, Morgan and Claypool.
20. ^ Venegas-Andraca, S. E. (2012). Quantum walks: a comprehensive review, Quantum Infotmation Processing 11, 1015-1106.
21. ^ 今野紀雄 (2008). 量子ウォークの数理, 産業図書 ISBN 478280508X.
22. ^ 今野紀雄 (2014). 量子ウォーク, 森北出版 ISBN 4627061617.
23. ^ 町田拓也 (2018). 量子ウォーク －基礎と数理－, 裳華房 ISBN 978-4-7853-1576-4.
24. ^ 町田拓也 (2015). 図で解る量子ウォーク入門, 森北出版 ISBN 978-4627053816.
25. ^ Konno, N. (2002). Quantum random walks in one dimension, Quantum Information Processing 1, 245-354.
26. ^ Konno, N. (2005). A new type of limit theorems for the one-dimensional quantum random walk, J. Math. Soc. Jpn. 57, 1179-1195.
27. ^ Sunada, T., and Tate, T. (2012). Asymptotic behavior of quantum walks on the line, J. Funct. Anal. 262, 2608–2645.
28. ^ Konno, N. (2010). Localization of an inhomogeneous discrete-time quantum walk on the line, Quantum Information Processing 9, 405-418.
29. ^ 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.

表 話 編 歴 量子コンピュータ
全般	量子コンピュータ 量子力学
ハードウェア	超伝導 イオントラップ型 核磁気共鳴 光子
アルゴリズム• プログラミング言語	量子プログラミング言語 ドイッチュ・ジョサのアルゴリズム グローバーのアルゴリズム ショアのアルゴリズム（英語版）
項目	量子ビット 量子回路 量子テレポーテーション 量子暗号 量子アニーリング 量子状態 量子もつれ 量子超越性 量子ウォーク 量子情報
関連分野	量子情報科学 情報工学
メーカー	IBM D-Wave Google
実機	九章
人物	ピーター・ショア ロブ・グローバー（英語版） デイヴィッド・ドイッチュ リチャード・ジョサ（英語版）
カテゴリ

• 量子ウォーク