グローバーのアルゴリズム

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

グローバーのアルゴリズムとは、N個の要素をもつ未整序データベースの中から、O(N1/2)のオーダーの計算量と、O(logN)のオーダー(ランダウの記号も参照)の記憶領域を消費する探索問題を解くための量子コンピュータアルゴリズムである。1996年ロブ・グローバー英語版によって開発された。

概要[編集]

典型的には、未整序データベースからの探索は、O(N)の計算時間を要する線型探索を用いなければならない。グローバーのアルゴリズムは、O(N1/2)の計算時間しか消費せず、未整序データベース探索を行う量子アルゴリズムの中で最も速い[1]。このアルゴリズムは他の量子アルゴリズムがしばしば、古典アルゴリズムと比較して指数的な速度向上をもたらすのとは異なり、二次の速度向上しかもたらさない。しかし、Nが大きければ、二次の向上でもかなりの向上となる。

他の量子アルゴリズムと同じように、グローバーのアルゴリズムは正しい確率の高い解を与える、確率的アルゴリズムである。この解が正しくない確率は、このアルゴリズムを繰り返すことによって減少させることができる(確率的アルゴリズムでない、正しい確率が1の解を与える、決定的アルゴリズムについてはドイッチュ・ジョサのアルゴリズム英語版を参照)。

応用[編集]

グローバーのアルゴリズムの目的は普通「データベース探索」とされるが、「逆関数の導出」と言うとより正確かもしれない。おおざっぱにいうと、y=f(x)という量子コンピュータで処理できる関数があったとして、このアルゴリズムを使うとあるyを与えるxの値を計算することができる。データベース探索は、データベースをインデックスxに対してデータyを与える関数と考えれば、逆関数を求めることと同値である。

グローバーのアルゴリズムは、平均中央値を推定すること、また衝突問題w:Collision problem)を解くのにも使える。また、可能性のある解を総当たりで探すことによってNP完全問題を解くことにも使える。これは、膨大な可能性を試すのに、重ね合わせを用いることで限られた計算量しか消費しないので、古典アルゴリズムに比べてかなりのスピードアップを見込めるが、多項式時間かかってしまうことは変らない。あらかじめ解が複数あることとその個数がわかっている場合、このアルゴリズムはさらに最適化することができる。

準備[編集]

N個のデータを持つデータベースを考える。このアルゴリズムはN次元の状態空間Hを必要とする。これはlog2N量子ビットあれば満される。

データベースのデータに、1,2,....,Nの様に番号をふる。また、Ωという、N個の異なる固有値が知られているH上の可観測量を選ぶ。Ωのそれぞれの固有状態は、データベース中のあるデータに、後述の様に対応する。固有状態をブラ-ケット記法を用いて下の様に表記する。

\{|1\rang, |2\rang, \cdots, |N\rang\}

また、対応する固有値を以下のように表記する。

\{\lambda_1, \lambda_2, \cdots, \lambda_{N} \}

データをある探索条件に基づいて評価するサブルーチンとして働くユニタリ演算子Uωがあるとする。このアルゴリズムはこのサブルーチンがどの様に働くかまでは指定しない。しかし、重ね合わせ状態を壊さない量子的サブルーチンでなければならない。さらに、このサブルーチンは、条件に該当するデータに対応する特定の固有状態|ω>にだけ作用するものでなくてはならない。正確に言うと、Uωは次のような効果をもたなくてはならない。

 U_\omega |\omega\rang = - |\omega\rang
 U_\omega |x\rang = |x\rang \qquad \mbox{for all}\ x \ne \omega

または

 \langle \omega| \omega\rang =1
 \langle \omega| x \rang =\langle x| \omega\rang =0
 U_\omega |\omega\rang = (I-2| \omega\rangle \langle \omega|)|\omega\rang=|\omega\rang-2| \omega\rangle \langle \omega|\omega\rang=-|\omega\rangle
 U_\omega |x\rang = (I-2| \omega\rangle \langle \omega|)|x\rang=|x\rang-2| \omega\rangle \langle \omega|x\rang=|x\rangle

このアルゴリズムの目的は、Uωが選択的に作用する固有状態|ω>、または同じことだが固有値ωを特定することである。

アルゴリズムの流れ[編集]

グローバーのアルゴリズムの流れは以下の通りである。

  1. 初期状態を以下の様に用意する。
    • |s\rang = \frac{1}{\sqrt{N}} \sum_{x=1}^{N} |x\rang
  2. 次にしめす"Grover iteration"をr(N)回繰替えす。関数r(N)については後述する。
    1. 演算子U_\omega=I-2| \omega\rangle \langle \omega|を適用する。
    2. 演算子U_s = 2 \left|s\right\rangle \left\langle s\right| - Iを適用する。
  3. 状態Ωを観測する。観測の結果は、繰替しの回数が十分に大きければ、1に近い確率でλωとなる。つまり、状態ωが得られる。

|s>と|ω>で張られる平面を考える。ω>は基底ベクトルであるから、|ω>と|s>の重なりは次のようになる。

 \lang\omega|s\rang =\lang s|\omega\rang = \frac{1}{\sqrt{N}}

幾何学的に言えば、|ω>と|s>のなす角度(π/2 - θ/2)は次の関係を満す。

 \cos \left(\frac{\pi}{2} - \frac{\theta}{2} \right) = \frac{1}{\sqrt{N}}
 \sin \frac{\theta}{2} = \frac{1}{\sqrt{N}}

演算子Uωは、|ω>と垂直超平面を対称面とする反転に相当する。|s>と|ω>で張られる空間上のベクトルに対しては、その平面上で|ω>と垂直な直線を対称軸とする反転として働く。演算子Usは、|s>を対称軸とする反転である。よって、UsUωは、|s>と|ω>によって張られる平面上にあるベクトルをその平面上に移す。また、Grover iterationUsUωの各ステップは、|ω>に向かう角度θ>の回転であることはすぐに示せる。

状態ベクトルが|ω>に近付いたなら、繰返しを止めなければならない。繰返しを重ねすぎると、状態ベクトルは|ω>から離れていってしまい、正しい解を与える確率を下げてしまう。この繰返し回数は次のrで与えられる。

r \rightarrow \frac{\pi \sqrt{N}}{4}

また、間違った解を与える確率はO(1/N)のオーダーで、これはNが増大するにつれて0に近づく。

正しい解が観測される確率はのように与えられる。

 \sin^2\left( \frac{2r+1}{2} \theta\right)

ここでrはGrover iterationの繰返し回数であり、θは次に示す角度である。

 \theta = 2\arccos\left( \sqrt{1-\frac{1}{N}} \right)=2\arcsin \frac{1}{\sqrt{2^n}}

発展形[編集]

もし、探索条件にあうデータが1個だけでなく、k個存在するならば、同じアルゴリズムを適用できるが、繰返し回数はπN1/2/4の代わりにπ(N/k)1/2/4としなければならない。 kが未知の場合を取り扱う方法は幾つかある。例として、繰返し回数を以下のようにしてグローバーのアルゴリズムを何回か走らせる方法がある。

 \pi \frac{N^{1/2}}{4}, \pi \frac{(N/2)^{1/2}}{4}, 
\pi \frac{(N/4)^{1/2}}{4}, \ldots

kがどのような値でも、上のような繰替し回数で行えば正しい解を高い確率で得られる。繰返しの総回数は多くとも次のようであり、O(N1/2)のオーダーにとどまる。

 \pi \frac{N^{1/2}}{4} \left( 1+ \frac{1}{\sqrt{2}}+\frac{1}{2}+\cdots\right)

このアルゴリズムは改良の余地がある。kが未知であるとして、O(\frac{N}{k})^{1/2}のオーダーで解を見付けることができる。このことから、このアルゴリズムは衝突問題を解く目的で使用できる。

最適性[編集]

グローバーのアルゴリズムは最適であることが知られている。つまり、データベースにUωのみを用いてアクセスするようなどんなアルゴリズムも、グローバーのアルゴリズムと同じかそれ以上の回数だけUωを作用させなければならない。[1]この結果は量子計算の限界を理解する上で重要である。 もし、グローバーの探索問題がlogcNUω適用することで解くことができるとすれば、NP問題をグローバーの探索問題に帰着させることで、NPがBQPに含まれることが示される。グローバーのアルゴリズムが最適であることは、NPはBQPに含まれないことを示唆している(ただし証明しているわけではない)。

k個の条件に該当するデータがある場合、π(N/k)1/2/4も最適である。


関連項目[編集]

参考文献[編集]

脚注[編集]

  1. ^ a b Bennett C.H., Bernstein E., Brassard G., Vazirani U., The strengths and weaknesses of quantum computation. w:SIAM Journal on Computing 26(5): 1510-1523 (1997). Shows the optimality of Grover's algorithm.