首页/术语表/Grover 算法(Grover's Algorithm)
Algorithms

Grover 算法(Grover's Algorithm)

一种量子搜索算法,在未排序列表中查找标记项的速度比任何经典算法呈二次方更快。

Grover 算法由 Lov Grover 于 1996 年发表,为无结构搜索提供了二次加速。对于一个包含 N 项的搜索空间,经典搜索需要 O(N) 次查询,而 Grover 算法只需 O(√N) 次查询。该算法的工作原理是反复施加“Grover 扩散算子”——它通过一个称为振幅放大(amplitude amplification)的过程放大目标态的振幅同时抑制其他态的振幅。经过约 π√N/4 次迭代后,测量该状态就能以高概率得到目标项。Grover 算法被证明是最优的——对于无结构搜索,没有任何量子算法能做得更好。其应用包括数据库搜索、求解 NP 难问题和量子密码分析。HLQuantum 包含内置的 Grover 实现。