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