grovers-algorithm

グローバーのアルゴリズム (grovers-algorithm)

グローバーのアルゴリズムは、未整理な候補の中から条件を満たすものを探す探索問題に対して、量子計算で高速化を与えるアルゴリズム。動画では、古典計算ならオーダーNが必要な探索をオーダー√Nに改善する例として紹介される。

この改善は「一瞬で答えが出る」ことを意味しない。量子アルゴリズムが正解に対応する状態の確率を高め、観測時に正解を得やすくすることで、必要な試行回数を減らすという位置づけになる。