1996年、ベル研究所（ニュージャージー州）のコンピューター科学者ロブ・グローバー研究員は、データベースを検索するための画期的アルゴリズムを発表した。検索アルゴリズムはコンピューター科学で最も重要な研究対象といってよい。電話帳から番号を探すだけではなく、暗号データを解読するような、高度な処理でも使われる。検索アルゴリズムはコンピューター科学の基礎中の基礎として、あらゆるプログラムで使われている。
したがって、検索処理の速度向上は、プログラム全体の性能を高めることにもなり、極めて重要だ。標準的な検索方法では、検索対象の総件数におおむね比例して一定の時間がかかる。つまり最悪の場合、たったひとつの情報を見つけるために、アルゴリズムは文書全体を最初から最後まで検索することになる。
しかし、グローバーのアルゴリズムは違った。処理時間はO(N1/2)として表現でき、検索対象の総件数の平方根に比例するのだ。コンピューター科学では、わずか数%の速度向上を巡ってアルゴリズムを改善しており、指数的な速度向上は非常に有益であり、超弩級の偉業といえる。
グローバーの方法が画期的だったのは、量子力学的な、奇妙だが強力なアイデアを利用することだった。一般的なコンピューターの場合、1ビットは0か1しか表せない。しかし量子の世界では、ひとつの量子ビット（キュービット）は0と1を同時に表せる。
物理学者が「重ね合わせ状態」と呼ぶキュービットの重ね合わせが鍵だ。重ね合わせ状態では、アルゴリズムは同じ瞬間に0と1の両方を検索できる。同時にひとつ以上の要素を検索できるので、量子アルゴリズムは従来の物理学の遅いペースに制限されたアルゴリズムよりも、非常にすばやくリストを検索できるのだ。
量子アルゴリズムは量子コンピューターで実行する必要があり、グローバーが研究した1996年当時、アイデアの実現は遠い夢にすぎなかった。しかしブレイクスルーはすぐにやってきた。物理学者は1998年に史上初の原始的な量子コンピューターを発表し、同年、グローバーのアルゴリズムを量子コンピューターでどのように実行できるか示したのだ。
ただし、当時の量子コンピューターの機能は非常に制限があり、数個のキュービットで動作するが、それ以上はキュービットを増やせず、理論的にも、より大きな計算処理にスケールアップできなかった。以来、ス …