6.6 搜索算法的最优性¶
练习 6.15¶
练习 6.15
利用 Cauchy-Schwarz 不等式，证明对任何归一化状态的向量 \(|\psi\rangle\) 和一组有 \(N\) 个向量的标准正交基向量 \(|x\rangle\)，有
首先我们将求和式的模平方作展开 (其中 \(\mathfrak{R}\) 是取实部的意思)：
因此，注意到 \(x\) 可以是 \(N\) 个正交基向量，因此不等式右的求和总数是 \(N\) 个：
我们定义该正交基的平均加和态为 \(|\chi\rangle = \frac{1}{\sqrt{N}} \sum_x |x\rangle\)，那么
显然对于两个归一的态，\(\mathfrak{R} (\langle \psi | \chi \rangle) \leqslant 1\)；因此
等号只有在 \(\langle \psi | \chi \rangle = 1\) 时取到，即 \(|\psi\rangle = |\chi\rangle = \frac{1}{\sqrt{N}} \sum_x |x\rangle\) 时取到。这个等号取到条件还蛮苛刻的，因为它不仅要求 \(|\psi\rangle\) 在构成上等同于 \(|\chi\rangle\)，而且相位上也要等同。但通过这种方式证明似乎不需要使用到 Cauchy-Schwarz 不等式。
练习 6.16¶
练习 6.16
设对所有可能值 \(x\) 的均匀平均而不是对 \(x\) 的所有值，要求差错的概率小于 \(1/2\)，证明 \(O(\sqrt{N})\) 次 orcale 调用对解搜索问题仍然是必需的。
这个条件意味着原先的对所有 \(x\) 满足 \(|\langle x | \psi_k^x \rangle| \geqslant 1/2\) 变更为了对于 \(x\) 的均匀平均的
回到书中的证明过程，由于 \(F_k\) 不涉及 \(\psi_k^x\)，因此我们只要考察 \(E_k = \sum_x \Vert \psi_k^x - x \Vert^2\) 即可。
这里需要利用模的值不大于 1，因此模本身比模平方要大的性质：
我们可以得到
上述不等号的取得条件极其苛刻，等号成立所有 \(x\) 下是 \(\langle \psi_k^x | x \rangle\) 为 1 或 0。
因此，将上述结果代入书中的式 (6.51)，可得
如果令 \(c\) 是任何小于 \((\sqrt{2} - 1)^2 \simeq 0.17\) 的常数，那么原先的 \(k \geqslant \sqrt{c N / 4}\) 即 \(k = \Omega(\sqrt{N})\) 仍然成立。因此，orcale 调用次数仍然需要 \(O(\sqrt{N})\) 数量级。
练习 6.17 (对多重解的最优性)¶
练习 6.17
假设搜索问题有 \(M\) 个解，证明为找到一个解需要 \(O(\sqrt{N/M})\) 次 orcale 调用。
危险
该练习不打算作证明。详细的证明恐怕需要将整个 6.6 节重新叙述一遍。
我想就如同之前一样，将单个解的 \(|x\rangle\) 的空间转换到多个解的空间就可以了。但为此，许多归一化的过程要引入 \(M\)，这会比较复杂。