はじめに

グローバーのアルゴリズムは、いわゆる非構造化探索問題に対する量子アルゴリズムであり、古典的なアルゴリズムに対して二次の改善をもたらします。 これが意味するのは、グローバーのアルゴリズムが非構造化探索を古典的に解くために必要な演算数の平方根オーダーの演算回数で済むということです。言い換えれば、非構造化探索の古典アルゴリズムのコストは、グローバーのアルゴリズムのコストの少なくとも二乗オーダーでなければならないということです。

グローバーのアルゴリズムは、その拡張と基礎となる手法とともに、幅広く応用可能であることが明らかになっており、表面上は非構造化探索問題に見えない多くの興味深い計算タスクに対しても二次的な優位性をもたらします。

グローバーの探索手法の広い適用可能性は説得力がありますが、このレッスンの冒頭で認めておく必要があるのは、それが提供する二次的な優位性が、量子コンピューティングが古典コンピューティングに対して実用的な優位性をもたらすことに近い将来つながる可能性は低いと思われるということです。 古典コンピューティングのハードウェアは量子コンピューティングのハードウェアよりもはるかに進んでおり、グローバーのアルゴリズムが提供する量子対古典の二次的な優位性は、近い将来に実行可能な任意の非構造化探索問題において、現代の古典コンピュータの驚異的なクロック速度によって打ち消されることは確実です。

しかし、量子コンピューティング技術が進歩するにつれ、グローバーのアルゴリズムは可能性を持つかもしれません。 実際、高速フーリエ変換や高速ソート（例えば、クイックソートやマージソート）を含む、これまでに発見された最も重要で影響力のある古典アルゴリズムのいくつかは、それらが解く問題への素朴なアプローチに対してわずかに二次未満の優位性を提供しています。 ここでの重要な違いは、もちろん、グローバーのアルゴリズムを実行するためにはまったく新しい技術（つまり量子コンピューティング）が必要だということです。 この技術は古典コンピューティングと比べてまだ非常に初期段階にありますが、量子対古典コンピューティングの二次的な優位性がいつか具体的な実用的利益をもたらす可能性のある技術的進歩の可能性を過小評価すべきではありません。

レッスン動画

次の動画では、John Watrous がグローバーのアルゴリズムに関するこのレッスンの内容を順を追って説明します。別のウィンドウでこのレッスンの YouTube 動画を開くこともできます。このレッスンのスライドをダウンロードすることもできます。