量子ランダムウォーク

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

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

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