量子ウォーク

量子ウォークはランダムウォーク量子版と考えることができる。 量子コンピュータの研究に伴い,2000年代に研究が活発になった分野である。 量子ウォークにもとづいて構成されたいくつかの量子探索アルゴリズムは,対応する古典的な確率探索アルゴリズムよりも高速な計算速度を生み出すことが証明されている。ランダムウォークやブラウン運動が,様々な分野で現象を記述して,重要な役割を担っているように,量子ウォークも同様な効果が期待されている。 なお,量子ウォークは2000年代初期には「量子ランダムウォーク」とも呼ばれていた。 現在は「量子ウォーク」が一般的な呼称である。






目次


1次元格子上の離散時間量子ウォーク



1次元格子上の離散時間量子ウォークは,確率振幅が2次の複素ベクトルで記述され,それらがユニタリ行列によって時間発展する。 量子ウォーカーを電子にたとえるならば,確率振幅の第1成分は上向きスピン,第2成分は下向きスピンの波動関数に対応する。

確率振幅


1次元格子上の離散時間量子ウォークでは,時刻t\in\left\{0,1,2,\ldots\right\}において,各場所x\in\mathbb{Z}=\left\{0,\pm 1,\pm 2,\ldots\right\}に,確率振幅\psi_t(x)を考える。確率振幅は2次の複素ベクトルで記述される。



時間発展


1次元格子上の離散時間量子ウォークの時間発展は,行列

\[  P=\left[\begin{array}{cc}		     a&b\\0&0			   \end{array}\right],\,  Q=\left[\begin{array}{cc}		      0&0\\c&d			   \end{array}\right]\]

を用いて,

\[ \psi_{t+1}(x)=P\psi_t(x+1)+Q\psi_t(x-1)\]

で定義される。但し,a,b,c,dは複素数であり,P+Q=Uはユニタリ行列である。


確率分布


量子ウォーカーが,時刻tにおいて,場所xに存在する確率\mathbb{P}(X_t=x)

\[ \mathbb{P}(X_t=x)= ||\psi_t(x)||^2\]

で定義する。ここで,X_tは時刻tにおけるウォーカーの位置を表す確率変数である。




確率振幅と確率分布の計算例(PDFファイル)

  • ランダムウォークとの比較





基本的性質


初期状態を

\[  \psi_0(x)=\left\{\begin{array}{ll}		     {}^T[\alpha,\beta]&(x=0),\\			    {}^T[0,0]&(x\neq 0)			   \end{array}\right.\]

とする。但し,複素数\alpha,\beta|\alpha|^2+|\beta|^2=1を満たす。また,Tは転置作用素を意味する。

このとき,時間発展作用素であるユニタリ行列Uの成分がabcd\neq 0を満たす量子ウォークに対し,以下の分布収束定理が成立する。

\[ \lim_{t\to\infty} \mathbb{P}\left(\frac{X_t}{t} \leq x\right)=\int_{-\infty}^{x} f(y)\,I_{(-|a|,|a|)}(y)\,dy.\]

但し,

\[ f(x)=\frac{\sqrt{1-|a|^2}}{\pi(1-x^2)\sqrt{|a|^2-x^2}}\left\{1-\left(|\alpha|^2-|\beta|^2+\frac{a\alpha\overline{b\beta}+\overline{a\alpha}b\beta}{|a|^2}\right)x\right\},\]


\[  I_{A}(x)=\left\{\begin{array}{cl}		     1&(x\in A), \\			    0& (x\notin A)			   \end{array}\right.\]

この分布収束定理は中心極限定理に対応するものである。 また,この定理より離散時間量子ウォークの極限分布の密度関数f(x)は,有限な台(コンパクト・サポート)をもつことが分かる。


なお,原点から出発する単純ランダムウォークの場合は,中心極限定理より

\[ \lim_{t\to\infty} \mathbb{P}\left(\frac{X_t}{\sqrt{t}} \leq x\right)=\int_{-\infty}^{x} f(y)\,dy\]

となる。 但し,

\[ f(x)=\frac{1}{\sqrt{2\pi}}\,e^{-x^2/2}.\]

上記のように,単純ランダムウォークの場合,極限分布は平均0,標準偏差1の正規分布(ガウス分布)N(0,1)で与えられ,その密度関数f(x)は有限な台をもたない。また,空間スケーリングも\sqrt{t}(つまり,X_t/\sqrt{t})であり,量子ウォークのスケーリングt(つまり,X_t/t)とは異なる。 これらのスケーリングは,時間に対する確率分布の標準偏差の増大オーダーを表しており,ランダムウォークではO(\sqrt{t}),量子ウォークではO(t)であることを意味している。 ランダムウォークと量子ウォークの違いは,このような極限定理でみることもできる。 古典系と量子系の違いを明らかにするための1つの手段として,長時間極限定理は重要な役割を果たしている。

1次元格子上の連続時間量子ウォーク



1次元格子上の連続時間量子ウォークでは,確率振幅が複素数で記述され,それらがシュレディンガー方程式に従って時間発展する。 離散時間モデルのように,スピンの概念はなく,そのような意味では非相対論的なモデルといえる。

確率振幅


1次元格子上の連続時間量子ウォークでは,時刻t\,\geq 0において,各場所x\in\mathbb{Z}=\left\{0,\pm 1,\pm 2,\ldots\right\}に,確率振幅\Psi_t(x)を考える。確率振幅は複素数で記述される。



時間発展


1次元格子上の連続時間量子ウォークの時間発展は,以下の空間離散版のシュレディンガー方程式で定義される。

\[  i\frac{d\Psi_t(x)}{dt}=-\nu\left\{\Psi_t(x-1)-2\Psi_t(x)+\Psi_t(x+1)\right\} \]

ここで,i=\sqrt{-1}\nuは正の定数である。


確率分布


量子ウォーカーが,時刻tにおいて,場所xに存在する確率\mathbb{P}(X_t=x)

\[ \mathbb{P}(X_t=x)= |\Psi_t(x)|^2\]

で定義する。



基本的性質


初期状態を

\[  \psi_0(x)=\left\{\begin{array}{ll}		     1&(x=0),\\			    0&(x\neq 0)			   \end{array}\right.\]

とする。

このとき,以下の分布収束定理が成立する。

\[  \lim_{t\rightarrow\infty}\mathbb{P}\left(\frac{X_t}{t}\leq x\right)=\int_{-\infty}^x f(y) \,I_{(-2\nu,2\nu)}(y)\,dy\]

但し,

\[ f(x)=\frac{1}{\pi\sqrt{(2\nu)^2-x^2}},\]


\[ I_{A}(x)=\left\{\begin{array}{cl}		     1&(x\in A), \\			    0& (x\notin A)			   \end{array}\right.\]

離散時間モデル同様,連続時間モデルの極限分布の密度関数f(x)も有限な台(コンパクト・サポート)をもつことがわかる。



古典系との違い



通常の1次元系モデルに関連する古典系との違いを挙げておく。

  • 時刻tに対する確率分布の標準偏差の増大オーダー
    • ランダムウォーク:O(\sqrt{t})
    • 量子ウォーク:O(t)
      (これらの性質は,確率分布の広がり方や基本的性質で紹介した分布収束定理に反映されている。)
  • t\to\inftyにおける極限定理
    • ランダムウォーク:X_t/\sqrt{t}は正規分布(ガウス分布)に分布収束する。
    • 量子ウォーク:X_t/t有限な台(コンパクト・サポート)をもつある確率密度関数f(x)に分布収束する。
  • 量子ウォークでは,モデルによっては確率分布に局在化が生じ得る。



応用



現在,量子ウォークは主に量子コンピュータの基礎理論構築に応用されており,量子ウォークにもとづいて構築されたいくつかの量子探索アルゴリズムでは,平均計算回数のオーダーが,入力数nに対しO(\sqrt{n})であることが証明されている。なお,対応する古典的な探索アルゴリズムの平均計算回数のオーダーはO(n)である。



関連項目




参考図書


参考文献


  • Julia Kempe (2003). Quantum random walks – an introductory overview. Contemporary Physics 44 (4): 307–327. DOI:10.1080/00107151031000110776.
  • Viv Kendon (2007). Decoherence in quantum walks – a review. Mathematical Structures in Computer Science 17 (6): 1169–1220. DOI:10.1017/S0960129507006354.
  • Norio Konno (2008). Quantum Walks. Volume 1954 of Lecture Notes in Mathematics. Springer-Verlag, (Heidelberg) pp. 309–452. DOI:10.1007/978-3-540-69365-9.
  • Salvador Elías Venegas-Andraca (2008). Quantum Walks for Computer Scientists. Morgan & Claypool Publishers. DOI:10.2200/S00144ED1V01Y200808QMC001.
  • Salvador Elías Venegas-Andraca (2012). Quantum walks: a comprehensive review. Quantum Information Processing 11 (5): 1015–1106. DOI:10.1007/s11128-012-0432-5.

参考リンク