量子ウォーク

量子ウォーク

執筆済 量子アルゴリズム

ランダムウォークの量子版。 グラフ上を「歩く」過程をユニタリ変換で記述する。

古典との違い#

古典ランダムウォーク 量子ウォーク
状態 確率分布 振幅の重ね合わせ
分散の広がり σ∼t σ∼t
分布の形 ガウス型（中心に集中） 両端にピーク

広がりが速いのは、振幅が干渉して 中心での打ち消し合いが起きるため。 この二次的な速さの違いが、探索アルゴリズムの加速に繋がる。

2 つの定式化#

  • 離散時間 — コイン演算子とシフト演算子を交互に適用
  • 連続時間 — グラフのラプラシアンをハミルトニアンとして e−iHt

応用#

用途 内容
空間探索 グラフ上の目標頂点を探す。Grover の一般化
要素判別 リスト中の重複を見つける（Ambainis のアルゴリズム）
万能計算 量子ウォークだけで万能量子計算ができる
グラフの区別 特定のグラフ問題で指数的加速

Childs らは、ある人工的に構成されたグラフ（glued trees）で 指数的な加速を示した。 構造を持つ問題でのみ大きな加速が得られる、という一般的な傾向の一例。

参考文献#