第54話 Grover検索・量子アルゴリズム

これまでの話
第1話 量子の夜明け
...
第46話 Shorのアルゴリズムのどこが凄いのか②？
第47話 量子ビットの間違い（量子誤り）訂正の方法・前編
第48話 量子ビットの間違い（量子誤り）訂正の方法・後編
第49話 オブザーバブル（メモ）
第50話 不確定性原理の導出（メモ）
第51話 正準交換関係
第52話 大規模なデータベース中の高速検索
第53話 Groverのアルゴリズムの概要（Grover Iteration）

今回は数式だらけですが淡々と規則どおりにやっているだけです。前回のフローチャートを机上計算してみます。


以下のStep3、Step4を繰り返す。（Grover Iteration）回数は Nの平方根 程度　　　　

以下でこのStep3,4のGrover Iterationを詳しく見てみます。


と置くと、

ここで、

なので、


これが１回目のGrover Iterationの結果です。

この結果は非常に印象的です。それは元の量子状態

と対比するとよく分かります。注目すべき点は量子状態ｋの観測確率は最初、

ですがGrover Iterationの結果

となっている点です。

Grover検索アルゴリズムは、上記操作からわかるように取り出したい状態の確率振幅は大きくなり無関係なデータの確率振幅は小さくなり正解を得る確率が高くなります。ただ無関係なデータの確率振幅は小さいが一般にはゼロにはならない値として残るのでたまたまその状態を観測した場合に無関係なデータを取り出してしまう可能性もありますが確率は非常に小さくなっています。またアルゴリズムが効率的なため無関係なデータを得たとしてもやり直せば良いだけです。さらにやり直しは多くても数回で済むはずです。そのためのGrover Iterationです。