6.3 量子计数¶
练习 6.13, 6.14¶
练习 6.13
考虑计数问题的一个经典算法。该算法在搜索空间中均匀独立地进行 \(k\) 次采样，令 \(X_1, X_2, \cdots, X_k\) 为 orcale 调用的结果，即当第 \(j\) 个调用显示为问题的一个解时，\(X_j = 1\)；而第 \(j\) 个调用没有显示为问题的一个解时，\(X_j = 0\)。这个算法给出搜索问题解的数目的估计 \(S \equiv N \times \sum_j X_j / k\)。证明 \(S\) 的标准差为 \(\Delta S = \sqrt{M (N-M) / k}\)。证明为以至少 3/4 概率，以精度 \(\sqrt{M}\) 对所有 \(M\) 估计 \(M\)，必须有 \(k = \Omega(N)\)。
练习 6.14
证明对任何至少以概率在 \(c \sqrt{M}\) 精度内，对所有的 \(M\) 估计 \(M\)，必须有 \(k = \Omega(N)\)。
我们使用概率的语言来解释标准差 \(\Delta S\) 的求取结果。考虑 \(p(\sum_j X_j = l)\) 或简记为 \(p(l)\) 即调用了 \(k\) 次 orcale，返回了 \(l\) 次结果 1。需要注意，题目中要求是均匀独立地进行 \(k\) 次采样，因此每次采样返回结果 1 的概率总是 \(\frac{M}{N}\)；因此 \(l\) 次采样为 1 的概率就是 \((\frac{M}{N})^l (\frac{N-M}{N})^{k-l}\)；同时，\(k\) 次采样中取出 \(l\) 次采样的数量是 \(C_k^l\)，因此
\(l\) 次采样为 1 的搜索问题解数目估计 \(S(l) = N l / k\)。那么，\(S(l)\) 对于 \(l\) 的平均值是
\(S(l)\) 对于 \(l\) 的平方平均值是
因此，标准差可以计算为
如果我们认为标准差与精度正比挂钩，那么 \(\Delta S < c \sqrt{M}\) 达成的条件是 \(k > (N - M) / c^2\)。尽管说，如果 \(M\) 非常接近于 \(N\)，那么 \(k\) 的次数不需要很多；但题目的要求是对所有的 \(M\) 作估计，因此 \(k\) 的复杂度应当视为与 \(N\) 同等级别，即 \(\Omega(N)\)。