出处已验证第 3 级
Grover算法
Grover算法为非结构化搜索提供二次加速，在N项中用O(√N)次查询找到目标。
这是什么意思
使用约π/4 * √N次预言查询。反复应用相位预言和Grover扩散算子。生活类比
像共振效应。
像量子回声定位。
常见误解
- 是二次加速不是指数加速。
- 迭代过多会降低成功概率。
要点总结
- O(√N)查询搜索 -- 二次加速。
- 相位预言 + 振幅放大。
- 非结构化搜索证明最优。
检验你的理解
Grover搜索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