グローバーのアルゴリズム - Wikipedia

グローバーのアルゴリズムとは、N個の要素をもつ未整序データベースの中から指定された値を検索する探索問題を解くための量子コンピュータのアルゴリズムであり、O(N1/2)のオーダーの計算量と、O(logN)のオーダー（ランダウの記号も参照）の記憶領域を消費する。1996年にロブ・グローバー（英語版）によって開発された。 典型的には、未整序データベースからの探索は、O(N)の計算時間を要する線型探索を用いなければならない。グローバーのアルゴリズムは、O(N1/2)の計算時間しか消費せず、未整序データベース探索を行う量子アルゴリズムの中で最も速い[1]。 このアルゴリズムは他の量子アルゴリズムがしばしば、古典アルゴリズムと比較して指数的な速度向上をもたらすのとは異なり、二次の速度向上しかもたらさない。しかし、Nが大きければ、二次の向上でもかなりの向上となる。たとえば、グローバーのアルゴリズムを共通

[Untouchable]

“このアルゴリズムは他の量子アルゴリズムがしばしば、古典アルゴリズムと比較して指数的な速度向上をもたらすのとは異なり、二次の速度向上しかもたらさない。”

[letsspeak]

なるほど、わからん。　グローバーのアルゴリズム