不動点量子探索

林 直樹

10月27日(金) 13時30分

ランダムな$N(=2^n)$個のデータ配列からある１つのデータを探し出すことを考える. このとき，量子計算のGroverのアルゴリズムを用いて探索を行えば 計算量が$O(\sqrt{N})$で終了することがわかっている
(古典計算のアルゴリズムでは$O(N)$になるものしか見つかっていない)．
Groverのアルゴリズムはある初期状態に対してGrover作用素と呼ばれる作用素を 反復的に作用させることで量子状態を目標の状態に近づけるものであり， このとき必要となる反復の回数(正確にはクエリの数)が$O(\sqrt{N})$である． しかし，このアルゴリズムでは各反復において常に同じ演算子を作用させるため， 適切な回数で計算を止めなければ量子状態は一度目標状態に近づいた後 再び目標状態から離れ始めてしまう． 気軽に状態の観測を行えない量子計算ではこの性質は問題である．

そこで、この問題点を解決する為にGrover作用素を改良したものが 不動点量子探索[1]である． このアルゴリズムでは各反復において反復後の状態が反復前より 必ず目標状態に近づくことがわかっている．

本報告ではこのアルゴリズムについてお話しようと思っています．

[1] Lov K. Grover, “Fixed-Point Quantum Search”, Phys. Rev. Lett. 95. 150501 (2005)