量子ランダムウォーク

古典 vs 量子：同じ歩行、全く異なる広がり—干渉がすべてを変える

計算例 — 量子ランダムウォーク

量子/古典比	2.0775×
量子ピーク	0.2816
分布	\|0⟩から20ステップ後のアダマールコインウォーク。パリティが合わない位置の確率はゼロです。

ページを開いたときに計算機が表示する値です。上の入力を変えると再計算されます。

インタラクティブシミュレーションを読み込んでいます...

ランダムウォークから量子検索へ 🖖

量子ウォークの二次的な速度向上は、確率ではなく干渉から生まれます。各ステップでアダマールゲートがコインを重ね合わせ状態にするため、シフト演算子は振幅を左右同時に動かします。多くのステップを経ると、中心付近の振幅は打ち消し合います—左向きと右向きの寄与が逆位相で到達するためです—一方、±N/√2付近の振幅は建設的に強め合います。そのため分布は中央ではなく端にピークを持ちます。同じ仕組みがグローバーの検索(超立方体上のウォーク)や、チャイルズによる指数関数的高速化のグラフ探索を支えています。量子ウォークは、どんな拡散過程よりもはるかに速く遠いノードに到達できるのです。

拡散と弾道的スプリントの違い 🖖

ランダムウォークとは、コインを繰り返し投げるだけの動きです。表なら右へ一歩、裏なら左へ一歩。古典的にはその歩みが釣鐘型分布へとぼやけ、100回投げても出発点から10マス程度しか離れないことが多い。広がりが √N でしか増えないためです。ところがコインを量子コインに替えると、もう平均化されません。歩行者は外側へ突き進み、同じ100歩で ~70マスにまで達します。物理ではこれを弾道的拡散と呼び、N の平方根ではなく N に比例して線形に広がります。

量子ウォークは決して忘れない 🖖

古典的なランダムウォークはマルコフ過程です。出発点の記憶を少しずつ失い、最終的な分布だけからは始点を復元できません。一方、量子ウォークはユニタリなので、各ステップは完全に可逆です。アダマール変換とシフトの正確な手順を逆向きに実行すると、散らばった振幅はふたたび原点の一本の鋭いピークへ収束します。情報は一切失われず、緩和して落ち着く平衡分布も存在しません。拡散は履歴を消し去りますが、量子ウォークはそれをただ隠しているだけなのです。

全プロセスの詳細解説

10ステップにおける2つのウォーカーの広がり 9 ステップ
10ステップ、2つのウォーカー。一方は各ステップで公平なコインを投げて±1移動する。他方はコイン状態 |0⟩ から出発し、毎回の移動の前にコインにアダマールゲートを適用する。両者の広がりを正確に算出し、古典ウォーカーが同じ広がりをカバーするのに必要なステップ数を求めよ。
1. 古典的なステップは独立であり、各ステップが正確に 1 の分散に寄与するため、分散は足し合わされる。この一行が古典解のすべてであり、上のパネルがシミュレーションではなく平方根を表示する理由でもある。
  
  $σ_{c}^{2} = 10 1 + 1 + \dots + 1 = 10 ⟹ σ_{c} = 10 = 3.1623$
2. 量子ウォーカーは分岐を選択することはない。各サイトでコインの値ごとに1つずつ、計 2 つの振幅を保持する。アダマールゲートはそれらを和と差で置き換え、|0⟩ の成分は左へ、|1⟩ の成分は右へ移動する。サイトは両隣から受信し得るため、振幅は足し合わされ、差が 0 になることもある。
  
  $(a_{0}, a_{1})_{x} ⟶ \frac{a _{0} + a _{1}}{2} (1, 0)_{x - 1} + \frac{a _{0} - a _{1}}{2} (0, 1)_{x + 1}$
3. 原点で (1, 0) から開始し、2 ステップ進める。各ステップから因子 1/√2 を外に括り出すと振幅は整数のまま保たれるため、ステップ n の後、以下のペアはすべて 2^n/2 で除される。
  
  $n = 1 : (1, 0)_{- 1}, (0, 1)_{+ 1} n = 2 : (1, 0)_{- 2}, (1, 1)_{0}, (0, - 1)_{+ 2}$
4. ステップ 3 で対称性が崩れる。原点のサイトは (1, 1) を保持しており、左方向に 1 + 1 = 2 を、右方向に 1 − 1 = 0 を送り出す。アダマール行列の最下行にあるマイナス符号が、そのサイトの右方向への寄与を完全に打ち消し、x = −1 は x = +1 の 5 倍の確率を持つようになる。
  
  $n = 3 : (1, 0)_{- 3}, (2, 1)_{- 1}, (- 1, 0)_{+ 1}, (0, 1)_{+ 3} ⟹ p (- 1) = \frac{5}{8}, p (+ 1) = \frac{1}{8}$
5. ステップ 10 まで計算を進める。振幅は依然として 2⁵ を分母とする整数であるため、すべての確率は 1024 を分母とする整数となる。以下の 11 個の分子は厳密な値であり、それらの和は 1024 になる。
  
  $n = 10 : 1024 p (x) = 1, 82, 449, 64, 100, 72, 52, 64, 89, 50, 1 (x = - 10, - 8, \dots, + 10)$
6. リストから最も大きい分子を直接読み取る。それは 449 であり、原点からも遠い端からも十分離れた x = −6 に位置している。
  
  $x max p_{q} (x) = p_{q} (- 6) = \frac{449}{1024} = 0.4385$
7. 平均は 0 ではない。|0⟩ は左に移動する側のコイン状態であり、ステップ 3 ですでにそれが大きな割合を占めることが示されているため、分布全体がそちらに偏る。
  
  $μ = x \sum x p (x) = - \frac{2512}{1024} = - 2.4531$
8. 分散は 2 乗平均から平均の 2 乗を引いたものであり、どちらの総和も同じ 11 個の分子から得られるため、新たな情報は必要ない。
  
  $σ_{q}^{2} = x \sum x^{2} p (x) - μ^{2} = \frac{30672}{1024} - 6.0177 = 23.935 ⟹ σ_{q} = 4.8924$
9. ステップ 1 で求めた古典的な広がりで割る。
  
  $\frac{σ _{q}}{σ _{c}} = \frac{4.8924}{3.1623} = 1.5471$
解答

σ_q = 4.8924（σ_c = 3.1623 に対し比率 1.5471）、量子ピークは p_q(−6) = 0.4385。ここで、その分散をステップ数として解釈する。古典ウォーカーの広がりは √M であるため、4.8924 に到達するには M = σ_q² = 23.9、すなわち 24 ステップを要する。これは 10 ステップ後の同じ到達範囲に対して 2.4 倍の試行回数に相当する。古典的なステップ数は広がりの比の 2 乗であり、ここが記憶に留めるべき重要な点である。広がりにおける 2 倍のアドバンテージは、ステップ数における 4 倍のアドバンテージを意味する。

$M = σ_{q}^{2} = 23.9 \approx 24, \frac{M}{N} = (\frac{σ _{q}}{σ _{c}})^{2} = 1.547 1^{2} = 2.394$

参考文献 (2)

Insight block 1 — the coined walk this tool steps through: Y. Aharonov, L. Davidovich and N. Zagury, "Quantum random walks." Physical Review A 48(2), 1687–1690, 1993.
And the exponential separation block 1 names: A. M. Childs, R. Cleve, E. Deotto, E. Farhi, S. Gutmann and D. A. Spielman, "Exponential algorithmic speedup by a quantum walk." Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 59–68, 2003.

42Math チーム · 更新 2026-05-22

公表された資料と照合しています。訂正のご指摘を歓迎します。編集方針 · 訂正

コンピューティングのレッスン一覧 →

例題

10ステップ - 10ステップ — 非対称な二つのピークがすでに現れている
30ステップ - 30ステップ — 量子的な広がりが古典的な場合より劇的に広い
50ステップ - 50ステップ — 量子はO(N)の広がり、古典はO(√N)
バランスコイン - 20ステップ、バランスの取れたコイン — 左右対称な二峰分布