グローバーのアルゴリズム
整理されていない集合の探索を、要素数の半分ではなく平方根のステップで済ませる。高速化は指数的ではなく二次的である。
1996年にロブ・グローバーが発表した。構造を利用できない100万件の中から目的の一つを古典的に探すと、平均で50万回の試行が要る。グローバーのアルゴリズムなら約1000回で済む。手法は振幅増幅と呼ばれ、正解の振幅を一歩ずつ持ち上げ、それ以外を押し下げていくと、およそ√N回の反復で正解が支配的になる。
得られる効果は確かだが、ショアのアルゴリズムと比べれば控えめだ。暗号への実際の影響は、共通鍵の鍵長が実質的に半分になることである。AES-128は64ビット相当の余裕に下がるが、AES-256なら十分である。公開鍵暗号と違って、共通鍵暗号が量子コンピュータに備えて置き換えを迫られないのはそのためだ。