Grover 算法在 N 个项目中搜索被标记的一个,只需大约 √N 次查询。它的预言机用一个负号标记该项目。单单一个符号不会改变任何结果,所以每一轮都在预言机之后接一个*扩散*(diffusion)步骤:把每个振幅关于全部振幅的平均值作反射。 预言机之后,被标记的振幅为负,平均值略低于其他振幅。关于平均值作反射,会把被标记的振幅抬到远高于其余振幅的位置。重复大约 (π/4)√N 次后,被标记的项目会以接近 1 的概率出现。当 N = 4 时,一轮就是精确的:每次的结果都是被标记的项目。 扩散步骤是夹在两层 Hadamard 门之间、加在 |0…0⟩ 上的一个符号。Studio 的示例“Grover search, 3 qubits”在 N = 8 上运行两轮:被标记的项目以 121/128 的概率出现。 这道练习要求没有相互抵消的门:评析(critique)发现的问题模式也是检查的一部分。`wai-quantum critique` 会列出它们及其所在的行,**哪里出了问题?** 会引用它们。