量子ウォーク

提供: testwiki
2024年10月11日 (金) 07:04時点におけるimported>Watamochiによる版 (ウィキペディアの記事における表記方法の慣習にそぐわない部分の修正（但し→ただし）)
(差分) ← 古い版 | 最新版 (差分) | 新しい版 → (差分)
ナビゲーションに移動 検索に移動

量子ウォーク(テンプレート:Lang-en-short)は、ランダムウォークの量子版と見なされるモデルである。

概要

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

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

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

全空間

量子ウォークの全空間はℋ=ℋP⊗ℋCで定義される 。ただし、ℋP=Span{|x⟩;x∈ℤ}は粒子の場所を、ℋC=Span{|J⟩;J∈{L,R}}は粒子の自由度をそれぞれ表すヒルベルト空間である 。非自明な時間発展を与えるユニタリ作用素を定義するために、粒子の場所を記述する空間ℋPに2次の自由度を持つ空間ℋCが付随する[3] 。

時間発展

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

C=⨁x∈ℤH

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

S|x,J⟩={|x+1,R⟩:J=R|x−1,L⟩:J=L

を満たす 。ただし、|x,J⟩:=|x⟩⊗|J⟩∈ℋP⊗ℋCである 。

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

Ψ0↦UΨ1↦UΨ2↦U⋯

つまり、

Ψn=UnΨ0(n=0,1,2,…)

によって時間発展を定義する 。ここで、Uのユニタリ性からノルムが保存され、||Ψn||2=1が全ての時刻n=0,1,2,…で成り立つ 。時刻nでの状態Ψnのx(∈ℤ)成分をΨn(x)=T[Ψn(L)(x),Ψn(R)(x)]と書くことにする 。 このとき、Ψn(J)(x)∈ℂは量子ウォークの時刻n∈ℕ、場所x∈ℤ、カイラリティJ∈{L,R}の確率振幅と呼ばれる 。さらに、|L⟩,|R⟩∈ℋCを|L⟩≅T[1,0]、|R⟩≅T[0,1] と表現したときの、量子コインHの行列表現を

H=[abcd]

として、H=P+Qとなるように

P=[ab00],Q=[00cd],

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

Ψn(x)=QΨn−1(x−1)+PΨn−1(x+1)

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

分布

量子ウォークの、時刻nにおける分布μn:ℤ→[0,1]は以下のように定義される 。

μn(x)=∑J∈{L,R}|⟨x,J|UnΨ0⟩|2.

ここで、μnは、時刻n∈ℤ、場所x∈ℝで粒子が見つかる確率を表している 。最近、このμnが実験的に実現されたことが報告されている[15][17][16] 。


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

線型的拡がり

量子ウォークの分布の統計的な性質に関しては、Konno (2008)[12]等でその詳細を見ることができる 。例えば、Konno (2002)[25]・Konno (2005)[26]によって、Xnを初期状態Ψ0=|0⟩⊗(α|L⟩+β|R⟩)から始めた量子ウォーク（ただし、abcd=0）の時刻nでの分布μn(x)に従う確率変数とすると、

Xn/n⇒Y,(n→∞)

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

{1−c(a,b;α,β)x}fK(x;|a|).

ここで、

c(a,b;α,β)=|α|2−|β|2+2Re(aαbβ‾)|a|2,

fK(x;|a|)=|c|π(1−x2)|a|2−x2𝟏{x<|a|}(x),

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


局在化

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

lim supn→∞μn(x)>0

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

一段階目

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

μ*(x)=limn→∞1T∑n=0T−1μn(x)≥0.

二段階目

長時間平均測度μ*(x)を用いて、c*≡∑xμ*(x)とおくと、0≤c*<1となり、確率が保存されていない場合がある 。二段階目はその残りの1−c*に対応する以下の極限定理である 。

Xn/n⇒Z(n→∞).

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

ν(x)=c*δ0(x)+(1−c*)w(x)fK(x;r).

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

参考文献

  1. ↑ 1.0 1.1 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. ↑ 3.0 3.1 3.2 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. ↑ 9.0 9.1 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. ↑ 12.0 12.1 12.2 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. ↑ 13.0 13.1 Joye, A., and Merkli, M. (2010). Dynamical localization of quantum walks in random environments, J. Stat. Phys. 140, 1-29.
  14. ↑ 14.0 14.1 Ahlbecht, A., Scholz, V. B., and Werner, A. H. (2011). Disordered quantum walks in one lattice dimension, J. Math. Phys. 52, 102201
  15. ↑ 15.0 15.1 Karski, M. et al. (2009). Quantum walk in position space with single optically trapped atoms, Science 325, 174.
  16. ↑ 16.0 16.1 Zähringer, F. et al. (2010). Realization of a quantum walk with one and two trapped ions, Phys. Rev. Lett. 104, 100503.
  17. ↑ 17.0 17.1 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.

テンプレート:量子コンピュータ

参考リンク

「https://ja.wiki.beta.math.wmflabs.org/w/index.php?title=量子ウォーク&oldid=8408」から取得