量子ウォーク
量子ウォークはランダムウォークの量子版と考えることができる。 量子コンピュータの研究に伴い，2000年代に研究が活発になった分野である。 量子ウォークにもとづいて構成されたいくつかの量子探索アルゴリズムは，対応する古典的な確率探索アルゴリズムよりも高速な計算速度を生み出すことが証明されている。ランダムウォークやブラウン運動が，様々な分野で現象を記述して，重要な役割を担っているように，量子ウォークも同様な効果が期待されている。 なお，量子ウォークは2000年代初期には「量子ランダムウォーク」とも呼ばれていた。 現在は「量子ウォーク」が一般的な呼称である。
目次
1次元格子上の離散時間量子ウォーク †
1次元格子上の離散時間量子ウォークは，確率振幅が2次の複素ベクトルで記述され，それらがユニタリ行列によって時間発展する。 量子ウォーカーを電子にたとえるならば，確率振幅の第1成分は上向きスピン，第2成分は下向きスピンの波動関数に対応する。
確率振幅 †
1次元格子上の離散時間量子ウォークでは，時刻
において，各場所
に，確率振幅
を考える。確率振幅は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]\]](image/equation/40466fc661902eb92c1d1c9307ed92a43b05b2f18ce46f0ada0bd65ba151.png "\[ 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)\]](image/equation/344c17b23b05cf84a40f3804118c46a33b05b2f18ce46f0ada0bd65ba151.png "\[ \psi_{t+1}(x)=P\psi_t(x+1)+Q\psi_t(x-1)\]")
で定義される。但し，
は複素数であり，
はユニタリ行列である。
確率分布 †
量子ウォーカーが，時刻
において，場所
に存在する確率
を
![\[ \mathbb{P}(X_t=x)= ||\psi_t(x)||^2\]](image/equation/1a6782fb55ccbcbfc80458460a305da73b05b2f18ce46f0ada0bd65ba151.png "\[ \mathbb{P}(X_t=x)= ||\psi_t(x)||^2\]")
で定義する。ここで，
は時刻におけるウォーカーの位置を表す確率変数である。
- 例
- ランダムウォークとの比較
基本的性質 †
初期状態を
![\[ \psi_0(x)=\left\{\begin{array}{ll} {}^T[\alpha,\beta]&(x=0),\\ {}^T[0,0]&(x\neq 0) \end{array}\right.\]](image/equation/a56216f490c276001775c144b1f26d483b05b2f18ce46f0ada0bd65ba151.png "\[ \psi_0(x)=\left\{\begin{array}{ll} {}^T[\alpha,\beta]&(x=0),\\ {}^T[0,0]&(x\neq 0) \end{array}\right.\]")
とする。但し，複素数
は
を満たす。また，
は転置作用素を意味する。
このとき，時間発展作用素であるユニタリ行列
の成分が
を満たす量子ウォークに対し，以下の分布収束定理が成立する。
![\[ \lim_{t\to\infty} \mathbb{P}\left(\frac{X_t}{t} \leq x\right)=\int_{-\infty}^{x} f(y)\,I_{(-|a|,|a|)}(y)\,dy.\]](image/equation/e499b7f32635cbd5336fffbac90fa51d3b05b2f18ce46f0ada0bd65ba151.png "\[ \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\},\]](image/equation/2042de8a478c46e344743ab6baa8ee6a3b05b2f18ce46f0ada0bd65ba151.png "\[ 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.\]](image/equation/310e40c9b2d3faa5902ebcbcc6190e9a3b05b2f18ce46f0ada0bd65ba151.png "\[ I_{A}(x)=\left\{\begin{array}{cl} 1&(x\in A), \\ 0& (x\notin A) \end{array}\right.\]")
この分布収束定理は中心極限定理に対応するものである。
また，この定理より離散時間量子ウォークの極限分布の密度関数
は，有限な台（コンパクト・サポート）をもつことが分かる。
- 例
なお，原点から出発する単純ランダムウォークの場合は，中心極限定理より
![\[ \lim_{t\to\infty} \mathbb{P}\left(\frac{X_t}{\sqrt{t}} \leq x\right)=\int_{-\infty}^{x} f(y)\,dy\]](image/equation/d093b73fafc199f6cf880e3d708ca2873b05b2f18ce46f0ada0bd65ba151.png "\[ \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}.\]](image/equation/13c8a3d720d45659f2635ab75d7ec8fc3b05b2f18ce46f0ada0bd65ba151.png "\[ f(x)=\frac{1}{\sqrt{2\pi}}\,e^{-x^2/2}.\]")
上記のように，単純ランダムウォークの場合，極限分布は平均0，標準偏差1の正規分布（ガウス分布）
で与えられ，その密度関数は有限な台をもたない。また，空間スケーリングも
（つまり，
）であり，量子ウォークのスケーリング（つまり，
）とは異なる。
これらのスケーリングは，時間に対する確率分布の標準偏差の増大オーダーを表しており，ランダムウォークでは
，量子ウォークでは
であることを意味している。
ランダムウォークと量子ウォークの違いは，このような極限定理でみることもできる。
古典系と量子系の違いを明らかにするための1つの手段として，長時間極限定理は重要な役割を果たしている。
1次元格子上の連続時間量子ウォーク †
1次元格子上の連続時間量子ウォークでは，確率振幅が複素数で記述され，それらがシュレディンガー方程式に従って時間発展する。 離散時間モデルのように，スピンの概念はなく，そのような意味では非相対論的なモデルといえる。
確率振幅 †
1次元格子上の連続時間量子ウォークでは，時刻
において，各場所に，確率振幅
を考える。確率振幅は複素数で記述される。
時間発展 †
1次元格子上の連続時間量子ウォークの時間発展は，以下の空間離散版のシュレディンガー方程式で定義される。
![\[ i\frac{d\Psi_t(x)}{dt}=-\nu\left\{\Psi_t(x-1)-2\Psi_t(x)+\Psi_t(x+1)\right\} \]](image/equation/fe0a13ae0819e5f9aaea077e9b1abe1f3b05b2f18ce46f0ada0bd65ba151.png "\[ i\frac{d\Psi_t(x)}{dt}=-\nu\left\{\Psi_t(x-1)-2\Psi_t(x)+\Psi_t(x+1)\right\} \]")
ここで，
，
は正の定数である。
確率分布 †
量子ウォーカーが，時刻において，場所に存在する確率を
![\[ \mathbb{P}(X_t=x)= |\Psi_t(x)|^2\]](image/equation/e12a906f160b4ae21fc68524995fabeb3b05b2f18ce46f0ada0bd65ba151.png "\[ \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.\]](image/equation/2299c036ab4604bec7342d9f0d9952063b05b2f18ce46f0ada0bd65ba151.png "\[ \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\]](image/equation/82e6b57934e7f3c5df3d1f929b860c763b05b2f18ce46f0ada0bd65ba151.png "\[ \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}},\]](image/equation/4b488a1e83f753063a4784eac056e38c3b05b2f18ce46f0ada0bd65ba151.png "\[ f(x)=\frac{1}{\pi\sqrt{(2\nu)^2-x^2}},\]")
離散時間モデル同様，連続時間モデルの極限分布の密度関数も有限な台（コンパクト・サポート）をもつことがわかる。
- 例
古典系との違い †
通常の1次元系モデルに関連する古典系との違いを挙げておく。
における極限定理
- ランダムウォーク：は正規分布（ガウス分布）に分布収束する。
- 量子ウォーク：は有限な台（コンパクト・サポート）をもつある確率密度関数に分布収束する。
- ランダムウォーク：
- 量子ウォークでは，モデルによっては確率分布に局在化が生じ得る。
応用 †
現在，量子ウォークは主に量子コンピュータの基礎理論構築に応用されており，量子ウォークにもとづいて構築されたいくつかの量子探索アルゴリズムでは，平均計算回数のオーダーが，入力数
に対し
であることが証明されている。なお，対応する古典的な探索アルゴリズムの平均計算回数のオーダーは
である。
関連項目 †
参考図書 †
- 量子ウォークの数理 -- 今野紀雄，産業図書，2008年2月，ISBN : 978-4782805084
- 量子ウォーク -- 今野紀雄，森北出版，2014年9月，ISBN : 978-4627061613
- 図で解る量子ウォーク入門 -- 町田拓也，森北出版，2015年5月，ISBN : 978-4627053816
- 量子ウォーク −基礎と数理− -- 町田拓也，裳華房，2018年6月，ISBN : 978-4-7853-1576-4
参考文献 †
- 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.
