まとめの考察
クエリモデルにおいて、グローバーのアルゴリズムは漸近的に最適です。 これが意味するのは、探索問題、あるいは特に一意探索問題に対して、最悪の場合に漸近的に より少ないクエリ数で解くクエリアルゴリズムは作れない、ということです。 このことは複数の方法で厳密に証明されています。
興味深いことに、これはグローバーのアルゴリズムが発見される以前から知られていました。グローバーのアルゴリズムは、既知の下限と一致していたのです。
グローバーのアルゴリズムがもたらす平方根の高速化はさまざまな設定で得られるという意味で、このアルゴリズムは広く応用可能でもあります。 たとえば、グローバーのアルゴリズムを別のアルゴリズムと組み合わせて改善を得ることが可能な場合があります。 また、グローバーのアルゴリズムは、速度向上を得るために他の量子アルゴリズムのサブルーティンとしてもよく使われます。
最後に、グローバーのアルゴリズムで使われる技術、すなわち2つの反射を合成して反復することで量子状態ベクトルを回転させる手法は、一般化できます。 その例として、振幅増幅と呼ばれる技術があります。これはグローバーのアルゴリズムと類似した処理を別の量子アルゴリズムに適用し、古典的な場合と比べて二次の高速化で成功確率を高めるものです。 振幅増幅は量子アルゴリズムにおいて幅広い応用があります。
したがって、グローバーのアルゴリズムは近い将来に探索において実用的な量子優位性をもたらさないかもしれませんが、本質的に重要な量子アルゴリズムであり、量子アルゴリズムで多くの応用を持つより一般的な技術の代表例です。