量子ウォーク
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2024/10/11 06:04 UTC 版)
量子ウォーク(英: 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]等を参照されたい 。
量子ウォークは、以下の全空間
カテゴリ
参考リンク
量子ウォーク
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/05/19 00:40 UTC 版)
詳細は「量子ウォーク」を参照 ランダムウォークを量子コンピュータ上で実行する。いくつかのアルゴリズムがこれを利用して作られている。
※この「量子ウォーク」の解説は、「量子コンピュータ」の解説の一部です。
「量子ウォーク」を含む「量子コンピュータ」の記事については、「量子コンピュータ」の概要を参照ください。
- 量子ウォークのページへのリンク
