出典検証済みレベル 3
グローバーのアルゴリズム
グローバーのアルゴリズムは非構造化探索に二次高速化を提供し、N項目からO(√N)クエリで検索します。
どういう意味か
約π/4 * √N回のオラクルクエリを使用。位相オラクルとグローバー拡散を繰り返し適用します。日常のたとえ
共鳴効果のようなもの。
量子エコーロケーション。
よくある誤解
- 二次高速化であり指数的ではありません。
- 反復が多すぎると成功確率が下がります。
要点
- O(√N)クエリで非構造化探索。
- 位相オラクル + 振幅増幅。
- 最適性が証明済み。
理解度チェック
グローバー探索の時間計算量は？
- A.O(N)
- B.O(log N)
- C.O(√N)
- D.O(N²)
答えを見る
答え: C. O(√N)
理由: O(√N)オラクルクエリです。
前提となる概念
一次資料: Grover, Quantum mechanics helps in searching for a needle in a haystack, Phys. Rev. Lett. 79, 325 (1997), doi:10.1103/PhysRevLett.79.325