グローバーのアルゴリズムについてわかりやすく解説！

量子コンピュータの発展が加速するにつれて、そのアルゴリズムについても注目されるようになってきた。ドイッチュ-ジョサのアルゴリズムや、ショアのアルゴリズムが有名であるが、ここでは、もう一つ有名な、グローバーのアルゴリズムについて解説する。

グローバーのアルゴリズムのしくみ

データベース検索について使えるというのがこのアルゴリズムの強みだが、ここでは「ダイヤルロックを探り当てる」というたとえをつかう。

ダイヤルロックがあると考える。正解0101をあてれば、ロックが開く。

普通の解除の試しかた(データベース検索も同じ)では、最悪、桁数一杯まですべて試さなければならず、桁数がふえると膨大な時間をとる。

ところが量子コンピュータでは、桁数Nとすると√N回程度で正解がわかる！

問題につかうダイヤルロック回路は量子コンピュータ(量子回路)では次のように表現できる。

ダイヤルロックの回路に対して、ある桁数(図では4桁)の問い合わせをする。このとき、入力された量子ビットの重ね合わせのなかに正解（例で0101）が含まれていれば、その番号だけ反転する。

「このような回路が与えられたときに、正解のダイヤルを速く見つけよ」、というのがグローバーのアルゴリズムで解決した問題である。このアルゴリズムでは「折り返し回路」をつかう。

グローバーのアルゴリズムに使う折り返し回路は、つぎのようなゲートの組み合わせで実現できる。

１．アダマールゲート（H）で、重ねあわせ状態を制御する。

２．「アドレスビットが｜0000>のとき位相を反転するゲート」で、確率の平均値をとり平均値を折り返しの基準として折り返す。

これをダイヤルロックの回路の前後に組み合わせて、全体をループにして何度か繰り返せば、高い確率で正解を引き当てられる。

なぜ正解のダイヤルをあてる確率が高まるのか解説する。

量子ビットが1と０の重ね合わせの確率を確率振幅という。折り返し処理をすると、正解のダイヤルのみ確率振幅が高くなり、それ以外は低くなる。

折り返しを繰り返すと、正解の確立振幅は3/√N、5/√Nというふうに大きくなっていくので、√N回で確立振幅がほぼ1になる。（すくなくとも確率50％より高くなることがわかっている。）よって何度か繰り返せば、近いうちに正解を引き当てることができる。

ロブ・グローバーによって1996年に発明された。素因数分解で有名なショアのアルゴリズムの2年後である。

1992年のドイッチュ-ジョサのアルゴリズムが、「量子コンピュータで解くことが有利な問題というのはわかるが、実際どういうところで役立つのか？」という疑問がもたれがちだったのに対して、グローバーのアルゴリズムは応用にも役立つ、とわかった初期の問題として名高い。