Groverアルゴリズムの水平化

林 直樹

6月30日(金) 13時30分

量子探索を行う際に困難となる点の１つに非常に多くのパラメータを扱わねばならな いということがある．本報告ではその改善を目的として、[1]に従ってGroverアルゴ リズムの改良を考える．

具体的には，状態Φ=[φ_1,…,φ_m]に対し，Groverのアルゴリズムでは1回の反復に つm個の作用素a_1,…,a_m (∈U(2^n))を用意し，[(a_1)Φ_1,…,(a_m)Φ_m]という状 態に遷移させることを反復的に行う．これはm個の(2^n)-qubitsのレジスタをそれぞ れ独立に操作することと同じであり，このとき(4^n)×m個のパラメータを扱う事が必 要となる． そこで，U(2^n)による左作用L_a(Φ)=[aφ_1,…,aφ_m]を考える．これはm個のレジ スタ全てに対し同一のオペレータaを作用させることにあたる．このときに必要とな るパラメータは4^n個である．探索のある目標状態をW_dとし、左作用L_aによるW_dの 軌道を‘目標軌道’と呼ぶ．任意の目標状態は目標軌道上にあることがわかってお り、目標軌道上で目標状態への遷移を行うために扱う必要のあるパラメータは4^n個 で済む．このことを利用してアルゴリズムの改良を行う．

改善されたアルゴリズムは次の２段階のステップを踏むものである．

1.初期状態を目標軌道上にある状態A'に移す．A'は初期状態から最短距離にある点で ある．
2.目標軌道上でA'からW_dへの探索を行う．

ステップ1において必要となる計算時間はたかだかO(m)であり、ステップ2で制御が必 要となるパラメータは4^n個であることが示される。

[1] 溝部公威，“「水平な」グローバー探索アルゴリズム”，京都大学大学院情報学 研究科数理工学専攻 2006年修士論文．