量子ウォーク

拡散を「確率」ではなく「振幅」で回す

量子ウォーク（Quantum Walk）は、古典のランダムウォークを量子力学の枠組みで置き換えた計算モデルです。古典ランダムウォークは、各ステップでコインを投げて左右どちらへ進むかを確率的に決め、多数の経路にわたる確率の和で位置分布を得ます。量子ウォークはこの確率を確率振幅（複素数の重み）に置き換え、すべての経路を重ね合わせたまま進めます。分布は経路ごとの振幅を足し合わせてから2乗して得るため、経路どうしが干渉（強め合い・打ち消し合い）します。

この一点が古典との決定的な違いを生みます。古典ランダムウォークで原点からの広がり（標準偏差）はステップ数 t に対し √t でしか伸びません（拡散的）。量子ウォークでは干渉により広がりが t に比例して伸びます（弾道的拡散）。同じ歩数で到達距離が二乗のオーダーで違う——これが後述する二次高速化と探索応用の源泉です。

離散時間量子ウォーク（DTQW）：コイン＋シフト

離散時間量子ウォーク（Discrete-Time Quantum Walk, DTQW）は、状態を位置レジスタとコインレジスタの2つで表します。1次元の直線上なら、状態は |位置 x> ⊗ |コイン c> の重ね合わせで、コインは c ∈ {0(左), 1(右)} の2値です。

1ステップは2つのユニタリ演算子の合成です。前提として量子ウォークの各操作は必ずユニタリ（可逆）でなければなりません。

1ステップ = S · (C ⊗ I_position)

  ① C（コイン演算子）: コインレジスタだけに作用し、進行方向を重ね合わせる
  ② S（シフト演算子）: コインの値に応じて位置を ±1 動かす（コインと位置を絡める）

コイン演算子には、コイン状態を等重ね合わせにするアダマール演算子 H がよく使われます（アダマールウォーク）。シフト S は「コインが左なら位置を1減らし、右なら1増やす」条件付き移動です。

アダマールコイン H の作用（1コインビット）:
  |0>  ->  (|0> + |1>)/√2
  |1>  ->  (|0> − |1>)/√2

条件付きシフト S:
  S |x>|0>  =  |x−1>|0>      （左向きコインなら左へ）
  S |x>|1>  =  |x+1>|1>      （右向きコインなら右へ）

C で各位置のコインを左右へ分岐させ、S でその分岐を実際の移動に変換する——これを交互に繰り返します。各位置には複数の経路の振幅が合流し、そこで干渉が起きます。

連続時間量子ウォーク（CTQW）：コインを持たない時間発展

連続時間量子ウォーク（Continuous-Time Quantum Walk, CTQW）は、離散ステップとコインをどちらも捨て、グラフ上の連続的な時間発展として定義します。頂点集合が計算基底 |v> に対応し、状態はその重ね合わせです。時間発展は、グラフ構造を符号化したハミルトニアン H（多くは隣接行列 A かグラフラプラシアン L = D − A、D は次数対角行列）による、シュレディンガー方程式の解で与えられます。

時間 t の状態:  |ψ(t)> = U(t) |ψ(0)>,   U(t) = exp(−i·H·t)

  H : グラフを符号化した時間非依存ハミルトニアン
      よく使うのは 隣接行列 A、またはラプラシアン L = D − A
  γ : ホッピングレート（H = γ·A のように結合の強さを表す係数）

CTQW の要点は、コインという補助レジスタが不要なことです。隣接行列の非対角成分（頂点 u と v が辺で結ばれていれば非ゼロ）が「隣へ確率振幅を漏らす」役割を果たし、時間とともに振幅がグラフ上を波として伝播します。古典の連続時間ランダムウォークが同じ L を生成子とする熱拡散方程式（d p/dt = −L p）に従うのに対し、CTQW は虚数単位 i が入るぶんだけ拡散が振動的・波動的になり、ここでも弾道的な広がりが現れます。

二次高速化はどこから来るのか

古典と量子の広がり方を並べると、速度差の正体がはっきりします。

広がりが √t から t へ上がることは、「ある距離 d に到達するのに必要な歩数」が古典の d² オーダーから量子の d オーダーへ減ることを意味します。これがヒッティングタイム（特定頂点に初めて到達するまでの期待歩数）や混合時間の二次的短縮につながり、探索アルゴリズムの高速化の土台になります。

探索アルゴリズムへの応用

量子ウォークの最大の実用は探索です。基本アイデアは、通常の歩みに「マーク済み頂点（探したい解）でだけ位相を反転するオラクル」を差し込むことです。解の頂点で符号を反転し続けると、干渉のパターンが崩れ、振幅が解へ集中するよう歩みが歪みます。

量子ウォーク探索の骨格（1ステップ内）:

  ① 通常のウォーク演算子 W を適用（コイン＋シフト、または exp(−iHt)）
  ② マークオラクル: 解の頂点の振幅だけ符号を反転（位相キック）
  → ①②の反復で、解を測る確率が O(1) まで増幅される

  必要反復数はグラフ依存だが、多くの場合 古典ヒッティングタイムの平方根オーダー

この枠組みはグローバー探索を特別な場合として含みます。グローバー探索は「完全グラフ（全頂点が相互に隣接）上の量子ウォーク探索」とみなせ、非構造の N 件探索を O(√N) に落とす二次高速化はここでも成立します。逆に、格子や特定の疎グラフでは、グローバー法をそのまま当てはめるより量子ウォーク探索のほうがオラクル呼び出しやコヒーレンス要件で有利になる場合があります。より抽象的には、ウォーク演算子とオラクルの2つの反射（鏡映）の合成として探索を記述する振幅増幅の一般論に接続し、要素判別（element distinctness）や三角形検出など、単純なグローバー法では書きにくい問題に二次高速化を与えます。

まとめ

• 量子ウォークは古典ランダムウォークの各経路を確率振幅で重ね合わせ、干渉で分布を決めるモデル。広がりが古典の √t（拡散的）から量子の t（弾道的）へ上がり、これが二次高速化の源泉になる。
• **離散時間版（DTQW）**は位置レジスタとコインレジスタを持ち、コイン演算子（例：アダマール）と条件付きシフトを交互に適用する。コインの初期位相が分布の対称性を左右する。
• **連続時間版（CTQW）**はコインを持たず、グラフの隣接行列／ラプラシアンをハミルトニアン H とし exp(−iHt) で時間発展させる。ゲート回路には DTQW、ハミルトニアンシミュレーションには CTQW が馴染む。
• 応用の中心は探索。マーク頂点で位相反転するオラクルを歩みに組み込むと多くのグラフでヒッティングタイムが二次的に短縮し、グローバー探索を完全グラフ上の特殊例として包含する振幅増幅の一般枠組みになる。ただし高速化はグラフ構造に依存し、指数加速は特殊なグラフに限られる。