第53話 Groverのアルゴリズムの概要（Grover Iteration）

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

量子コンピュータ用のグローバーのアルゴリズムの核心はGrover Iteratinにあります。この操作はNの平方根のオーダー繰り返す操作になります。この繰り返しは量子オラクルと拡散変換という操作の組み合わせになります。

量子オラクルQuantum Oracleは

という変換です。これは丁度、今欲しいデータの確率振幅（波動関数の係数）が反転する事を意味します。波で言えば位相が180度変わる事になります。

量子オラクル自体は次のように書くことが出来ます。

これは次のようにして確かめられます。

拡散変換（Diffusion Transform）は次のような変換です。

と置くと、

と書くことが出来ます。この拡散変換は後日詳しく見ますが反転した確率振幅を増幅してそうでない確率振幅を低くする機能があります。量子オラクルと拡散変換まとめると

という変換Gとして定義できます。そして変換Gを繰り返す事をGrover Iterationと言います。これによって欲しい部分の確率振幅が次々と増幅され不要な確率振幅が低下していきます。この事がまさにGroverのアルゴリズムの素晴らしいアイデアです。

次回はこのGroverのアルゴリズムを各ステップ毎にもう少し詳しく見ていきたいと思います。