＼閲覧ありがとうございます！当サイトではリンク広告を利用しています／
量子コンピュータの発展が加速するにつれて、そのアルゴリズムについても注目されるようになってきた。ドイッチュ-ジョサのアルゴリズムや、ショアのアルゴリズムが有名であるが、ここでは、もう一つ有名な、グローバーのアルゴリズムについて解説する。
データベース検索について使えるというのがこのアルゴリズムの強みだが、ここでは「ダイヤルロックを探り当てる」というたとえをつかう。
ダイヤルロックがあると考える。正解0101をあてれば、ロックが開く。
普通の解除の試しかた(データベース検索も同じ)では、最悪、桁数一杯まですべて試さなければならず、桁数がふえると膨大な時間をとる。
ところが量子コンピュータでは、桁数Nとすると√N回程度で正解がわかる！
問題につかうダイヤルロック回路は量子コンピュータ(量子回路)では次のように表現できる。
ダイヤルロックの回路に対して、ある桁数(図では4桁)の問い合わせをする。このとき、入力された量子ビットの重ね合わせのなかに正解（例で0101）が含まれていれば、その番号だけ反転する。
「このような回路が与えられたときに、正解のダイヤルを速く見つけよ」、というのがグローバーのアルゴリズムで解決した問題である。このアルゴリズムでは「折り返し回路」をつかう。
グローバーのアルゴリズムに使う折り返し回路は、つぎのようなゲートの組み合わせで実現できる。
１．アダマールゲート（H）で、重ねあわせ状態を制御する。
２．「アドレスビットが｜0000>のとき位相を反転するゲート」で、確率の平均値をとり平均値を折り返しの基準として折り返す。
これをダイヤルロックの回路の前後に組み合わせて、全体をループにして何度か繰り返せば、高い確率で正解を引き当てられる。
なぜ正解のダイヤルをあてる確率が高まるのか解説する。
量子ビットが1と０の重ね合わせの確率を確率振幅という。折り返し処理をすると、正解のダイヤルのみ確率振幅が高くなり、それ以外は低くなる。
折り返しを繰り返すと、正解の確立振幅は3/√N、5/√Nというふうに大きくなっていくので、√N回で確立振幅がほぼ1になる。（すくなくとも確率50％より高くなることがわかっている。）よって何度か繰り返せば、近いうちに正解を引き当てることができる。
ロブ・グローバーによって1996年に発明された。素因数分解で有名なショアのアルゴリズムの2年後である。
1992年のドイッチュ-ジョサのアルゴリズムが、「量子コンピュータで解くことが有利な問題というのはわかるが、実際どういうところで役立つのか？」という疑問がもたれがちだったのに対して、グローバーのアルゴリズムは応用にも役立つ、とわかった初期の問題として名高い。