跳到主要内容

Grover 算法

阐述​

问题​

在解空间 {0,⋯ ,N−1}\{0,\cdots,N-1\} 中寻找满足 f(x)=1f(x)=1 的解，其中 N=2nN=2^n。

算法​

O∣x⟩={−∣x⟩ if x is a solution, ∣x⟩ otherwise. O|x\rangle=\left\{\begin{aligned}-|x\rangle & \text { if } \mathrm{x} \text { is a solution, } \\|x\rangle & \text { otherwise. } \end{aligned}\right.
  1. 令起始态为∣ψ⟩=1N∑i=1N−1∣i⟩|\psi\rangle=\frac{1}{\sqrt{N}} \sum_{i=1}^{N-1}|i\rangle
  2. 进行 Grover 迭代若干次
    1. 应用黑箱
    2. 应用 H⊗nH^{\otimes n}
    3. 应用反射变换 2∣0⟩⟨0∣−I2|0\rangle\langle 0|-I
    4. 应用 H⊗nH^{\otimes n}

解释​

设我们将所有态分为非解和解两组，则有

∣ψ⟩=N−MN∣α⟩+MN∣β⟩.|\psi\rangle=\frac{\sqrt{N-M}}{\sqrt{N}}|\alpha\rangle+\frac{\sqrt{M}}{\sqrt{N}}|\beta\rangle .

则 OO 是沿非解态反射，而 2∣ψ⟩⟨ψ∣−I2|\psi\rangle\langle\psi|-I 是沿 ∣ψ⟩|\psi\rangle 反射，另设

sin⁡(θ2)=MN,\sin \left(\frac{\theta}{2}\right)=\frac{\sqrt{M}}{\sqrt{N}},

则在该平面上角度转动了 θ\theta。因此该迭代应该运行

π22MN≈π4NM\frac{\frac{\pi}{2}}{2 \frac{\sqrt{M}}{\sqrt{N}}} \approx \frac{\pi}{4} \frac{\sqrt{N}}{\sqrt{M}}

次。另外，如果不知道 NN 和 MM 的关系，只需要重复足够多的次数，测量就能得到随机的一个解。

最优性​

Grover 算法是几乎最优的，这表现为任何能完美分辨出 ∣x⟩|x\rangle 的算法都至少需要 N\sqrt N 次黑箱运算。

实例​

性质​

相关内容​

参考文献​