{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "da326735",
   "metadata": {},
   "source": [
    "# 6.3 量子计数"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5652bb28",
   "metadata": {},
   "source": [
    "## 练习 6.13, 6.14"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7b8f580d",
   "metadata": {},
   "source": [
    ":::{admonition} 练习 6.13\n",
    "\n",
    "考虑计数问题的一个经典算法。该算法在搜索空间中均匀独立地进行 $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)$。\n",
    "\n",
    ":::"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4e3573da",
   "metadata": {},
   "source": [
    ":::{admonition} 练习 6.14\n",
    "\n",
    "证明对任何至少以概率在 $c \\sqrt{M}$ 精度内，对所有的 $M$ 估计 $M$，必须有 $k = \\Omega(N)$。\n",
    "\n",
    ":::"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8731b088",
   "metadata": {},
   "source": [
    "我们使用概率的语言来解释标准差 $\\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$，因此\n",
    "\n",
    "$$\n",
    "p(l) = C_k^l \\left( \\frac{M}{N} \\right)^l \\left( \\frac{N-M}{N} \\right)^{k-l}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4cf9448b",
   "metadata": {},
   "source": [
    "$l$ 次采样为 1 的搜索问题解数目估计 $S(l) = N l / k$。那么，$S(l)$ 对于 $l$ 的平均值是\n",
    "\n",
    "$$\n",
    "\\langle S \\rangle = \\sum_{l=1}^k p(l) S(l) = \\sum_{l=1}^k C_k^l \\left( \\frac{M}{N} \\right)^l \\left( \\frac{N-M}{N} \\right)^{k-l} \\frac{N l}{k} = M\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d6372ba7",
   "metadata": {},
   "source": [
    "$S(l)$ 对于 $l$ 的平方平均值是\n",
    "\n",
    "$$\n",
    "\\langle S^2 \\rangle = \\sum_{l=1}^k p(l) S(l)^2 = \\sum_{l=1}^k C_k^l \\left( \\frac{M}{N} \\right)^l \\left( \\frac{N-M}{N} \\right)^{k-l} \\left(\\frac{N l}{k}\\right)^2 = \\frac{M (N + kM - M)}{k}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "13c1ff96",
   "metadata": {},
   "source": [
    "因此，标准差可以计算为\n",
    "\n",
    "$$\n",
    "\\Delta S = \\sqrt{\\langle S^2 \\rangle - \\langle S^2 \\rangle} = \\sqrt{\\frac{M (N-M)}{k}}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d9f7adaf",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2ac9d90a",
   "metadata": {},
   "source": [
    "如果我们认为标准差与精度正比挂钩，那么 $\\Delta S < c \\sqrt{M}$ 达成的条件是 $k > (N - M) / c^2$。尽管说，如果 $M$ 非常接近于 $N$，那么 $k$ 的次数不需要很多；但题目的要求是对所有的 $M$ 作估计，因此 $k$ 的复杂度应当视为与 $N$ 同等级别，即 $\\Omega(N)$。"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}