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