量子ウォーク

量子ウォーク()は、ランダムウォークの量子版と見なされるモデルである。
概要
量子ウォークには離散時間量子ウォークと連続時間量子ウォークがあるが、ここでは離散時間量子ウォークについて述べる 。

離散時間量子ウォークのプライオリティーに関しては諸説あるが、少なくとも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)、プログラミングのための本として町田(2025)がある。

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

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

量子ウォークは、以下の全空間、その空間上の時間発展作用素、これらから決まる分布列 の3つから成り立っている 。ただし、は時刻を表す 。

全空間
量子ウォークの全空間はで定義される 。ただし、は粒子の場所を、は粒子の自由度をそれぞれ表すヒルベルト空間である 。非自明な時間発展を与えるユニタリ作用素を定義するために、粒子の場所を記述する空間に2次の自由度を持つ空間が付随する 。

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

はコイン作用素と呼ばれる作用素である 。ただし、は上のユニタリ作用素で、量子コインと呼ばれる 。また、はシフト作用素と呼ばれる作用素で、

を満たす 。ただし、である 。

量子ウォークでは、初期状態（ただし、 とする）を与え、以下のように上のユニタリ作用素を繰り返し作用させる 。

つまり、

によって時間発展を定義する 。ここで、のユニタリ性からノルムが保存され、が全ての時刻で成り立つ 。時刻での状態の成分をと書くことにする 。
このとき、は量子ウォークの時刻、場所、カイラリティの確率振幅と呼ばれる 。さらに、を、 と表現したときの、量子コインの行列表現を

として、となるように

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

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

分布
量子ウォークの、時刻における分布は以下のように定義される 。

ここで、は、時刻、場所で粒子が見つかる確率を表している 。最近、このが実験的に実現されたことが報告されている 。

量子ウォークの重要な性質
線型的拡がり
量子ウォークの分布の統計的な性質に関しては、Konno (2008)等でその詳細を見ることができる 。例えば、Konno (2002)・Konno (2005)によって、を初期状態から始めた量子ウォーク（ただし、）の時刻での分布に従う確率変数とすると、

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

ここで、

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

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

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

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

二段階目
長時間平均測度を用いて、とおくと、となり、確率が保存されていない場合がある 。二段階目はその残りのに対応する以下の極限定理である 。

ただし、は下記のような密度関数を持つ 。

ここで、実数と多項式はそれぞれの量子ウォークモデルに依存して決まる 。

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

参考リンク
量子ウォーク

Category:量子アルゴリズム
Category:数学に関する記事