7、量子搜索算法与量子行走的深入解析

量子搜索算法与量子行走的深入解析

1. 含重复元素的搜索问题

1.1 Grover 算法复杂度分析

在搜索问题中，对于足够大的 $N$，不等式 $c \leq D_t$ 的证明完成。其中常数 $c$ 需满足 $0 < c < \left(\frac{p}{2} - \sqrt{\frac{q}{2} - \frac{p^2}{2}}\right)^2$。能够找到标记元素的算法必须遵循不等式 (4.34)，进而得出 $cN \leq 4t^2$，等价于 $t = \Omega(\sqrt{N})$。这表明 Grover 算法在查询次数方面的计算复杂度为 $\Theta(\sqrt{N})$。

1.2 相关练习

• 练习 4.14：若测量返回值 $x_0$ 的概率大于或等于 $p$，则常数 $c$ 需满足 $0 < c < \left(\frac{p}{2} - \sqrt{\frac{q}{2} - 2p\sqrt{p}}\right)^2$。为实现接近 1 的成功概率，算法需运行 $\frac{1}{p}$ 次，但由于 $p$ 为常数，这并不改变 $\Omega(\sqrt{N})$ 的总成本。
• 练习 4.15：假设均匀平均概率大于或等于 $\frac{1}{2}$，而非假定对于所有 $x_0$ 都有 $\left|\langle x_0 | \psi_t \rangle\right|^2 \geq \frac{1}{2}$，仍需查询预言机 $\Omega(\sqrt{N})$ 次。