概要

グローバーのアルゴリズムは、いわゆる非構造化探索問題に対する量子アルゴリズムであり、古典的アルゴリズムと比較して 2次的な改善を提供する。 これは、構造化されていない探索を古典的に解くのに必要な操作回数の平方根のオーダーの操作回数をグローバー・アルゴリズムが必要とすることを意味する。つまり、構造化されていない探索のための古典的アルゴリズムは、少なくともグローバー・アルゴリズムのコストの 2乗のオーダーのコストを持たなければならないということと等価である。

Groverのアルゴリズムは、その拡張と基礎となる方法論とともに、広く適用可能であることが判明し、表面的には非構造化探索問題のようには見えないかもしれない多くの興味深い計算タスクに対して、2次的な利点をもたらす。

グロヴァーの探索技法の広範な応用可能性には説得力があるが、この技法が提供する2次関数的な利点が、古典的コンピューティングに対する量子コンピューティングの実用的な優位性にすぐにつながる可能性は低そうだということを、レッスンの最初にここで認識しておく必要がある。 そして、グローバーのアルゴリズムが提供する古典的アルゴリズムに対する2次量子的な優位性は、すぐにでも実行可能な非構造化検索問題では、現代の古典的コンピューターの驚異的なクロック速度によって洗い流されるに違いない。

しかし、量子コンピューター技術が進歩すれば、グローバーのアルゴリズムは可能性を持つだろう。 実際、高速フーリエ変換や高速ソート（例えば、クイックソートやマージソート）を含む、これまでに発見された最も重要でインパクトのある古典的アルゴリズムのいくつかは、それらが解決する問題に対する素朴なアプローチに対して2次関数以下の優位性しかない。 もちろん、ここでの重要な違いは、グルーバーのアルゴリズムを実行するためにまったく新しい技術（量子コンピューティングを意味する）が必要だということだ。 古典的なコンピューティングに比べれば、この技術はまだまだ発展途上ではあるが、技術の進歩によって、古典的なコンピューティングよりも量子コンピューティングの方が2乗的に有利になり、いつの日か目に見える実用的な利益をもたらすようになる可能性を、そう簡単に過小評価すべきではないだろう。

レッスン動画

次のビデオでは、ジョン・ワトラスがグローバーのアルゴリズムに関するこのレッスンの内容を説明します。 または、このレッスンのビデオ（ YouTube ）を別ウィンドウで開くこともできます。 このレッスンのスライドをダウンロードする