出典検証済みレベル 3
量子ウォーク
量子ウォークは古典ランダムウォークの量子版です。歩行者は位置の重ね合わせで動き、経路間の干渉により古典（距離 ~ sqrt(t)）より二次的に速く（距離 ~ t）広がります。
どういう意味か
離散時間量子ウォーク（Aharonov, Davidovich, Zagury, 1993）では、位置レジスタとコイン量子ビットを持ちます。各ステップでコイン操作（多くはアダマール）と条件付きシフトを適用します。途中で測定しないため経路の振幅が干渉し、分布は弾道的（標準偏差がtに比例）で二峰性になります。空間探索や要素相異性などのアルゴリズムの基盤であり、適切なグラフ上では万能量子計算を実装できます。日常のたとえ
普通の歩行者はコインを投げて左か右へ一歩進みますが、量子ウォークは魔法のコインで両方向へ同時に歩きます -- 重なった道が混ざり合い、出発点からずっと遠くへ行けます。
池の波紋とさまようアリの違いのようなものです: アリ（古典）はゆっくり広がり、波紋の先端（量子）は一定速度で外へ走ります。
よくある誤解
- 量子ウォークは乱数源が量子であるランダムウォークではありません -- 干渉が全く異なる二峰性・弾道的分布を生みます。
- 毎ステップ位置を測定すると量子性が壊れ、古典ランダムウォークに戻ります。
- 二次的な広がりの利点がすべての問題で自動的に高速化になるわけではありません。
要点
- コイン操作 + 条件付きシフトを測定なしで繰り返す。
- 弾道的拡散: 標準偏差 ~ t（古典は ~ sqrt(t)）。
- 空間探索などの基盤で、適切なグラフ上で計算万能。
理解度チェック
離散時間量子ウォークの広がりはステップ数tに対してどう増えますか？
- A.古典と同じsqrt(t)に比例
- B.tに比例（弾道的）
- C.全く広がらない
- D.t^2に比例
答えを見る
答え: B. tに比例（弾道的）
理由: 干渉により標準偏差はtに比例します。
前提となる概念
一次資料: Aharonov, Davidovich, Zagury, Quantum random walks, Phys. Rev. A 48, 1687 (1993), doi:10.1103/PhysRevA.48.1687
Graded 2026-07-10 (human sign-off): established per Aharonov, Davidovich, Zagury, Phys. Rev. A 48, 1687 (1993).