{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "4a3e650f",
   "metadata": {},
   "source": [
    "# 6.1 量子搜索算法"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "22bca3b6",
   "metadata": {},
   "source": [
    "## 练习 6.1"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b7f2bbbe",
   "metadata": {},
   "source": [
    ":::{admonition} 练习 6.1\n",
    "\n",
    "证明对应于 Grover 迭代中，相移的酉算符是 $2 |0\\rangle \\langle0| - I$。\n",
    "\n",
    ":::"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1d5f7c32",
   "metadata": {},
   "source": [
    "这是比较显然的。一种理解方式是矩阵表示。另一种则是将该相移算符作用于具体的态 (下式的 $x > 0$)：\n",
    "\n",
    "$$\n",
    "\\begin{align*}\n",
    "(2 |0\\rangle \\langle0| - I) |0\\rangle &= 2 |0\\rangle \\langle0|0\\rangle - |0\\rangle = |0\\rangle \\\\\n",
    "(2 |0\\rangle \\langle0| - I) |x\\rangle &= 2 |0\\rangle \\langle0|x\\rangle - |x\\rangle = - |x\\rangle\n",
    "\\end{align*}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bde3b782",
   "metadata": {},
   "source": [
    "## 练习 6.2"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cceb476b",
   "metadata": {},
   "source": [
    ":::{admonition} 练习 6.2\n",
    "\n",
    "证明应用运算 $(2 |\\psi\\rangle\\langle\\psi| - I)$ 到一般状态 $\\sum_k \\alpha_k |k\\rangle$ 产生\n",
    "\n",
    "$$\n",
    "\\sum_k \\big( - \\alpha_k + 2 \\langle \\alpha \\rangle \\big) |k\\rangle\n",
    "$$\n",
    "\n",
    "其中 $\\langle \\alpha \\rangle = \\sum_k \\alpha_k / N$ 是 $\\alpha_k$ 的均值，因此，$(2 |\\psi\\rangle\\langle\\psi| - I)$ 有时称为关于均值的反演 (inversion about mean) 运算。\n",
    "\n",
    ":::"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b84302c0",
   "metadata": {},
   "source": [
    "首先我们回顾到均衡叠加态的定义\n",
    "\n",
    "$$\n",
    "|\\psi\\rangle = \\frac{1}{\\sqrt{N}} \\sum_{x=0}^{N-1} |x\\rangle\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "abc9ed5d",
   "metadata": {},
   "source": [
    "因此，其外积为\n",
    "\n",
    "$$\n",
    "|\\psi\\rangle\\langle\\psi| = \\frac{1}{N} \\sum_{x=0}^{N-1} \\sum_{y=0}^{N-1} | x \\rangle \\langle y |\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "26974fb1",
   "metadata": {},
   "source": [
    "随后，我们指出题目中的 $\\sum_k \\alpha_k |k\\rangle$ 严格来说是 $\\sum_{k=0}^{N-1} \\alpha_k |k\\rangle$，即 $k$ 并非任意角标。因此，\n",
    "\n",
    "$$\n",
    "\\begin{align*}\n",
    "|\\psi\\rangle\\langle\\psi| \\sum_{k=0}^{N-1} \\alpha_k |k\\rangle &= \\frac{1}{N} \\sum_{x=0}^{N-1} \\sum_{y=0}^{N-1} \\sum_{k=0}^{N-1} \\alpha_k | x \\rangle \\langle y | k\\rangle \\\\\n",
    "&= \\frac{1}{N} \\sum_{x=0}^{N-1} \\sum_{y=0}^{N-1} \\sum_{k=0}^{N-1} \\alpha_k | x \\rangle \\delta_{yk} = \\frac{1}{N} \\sum_{x=0}^{N-1} \\sum_{k=0}^{N-1} \\alpha_k | x \\rangle \\\\\n",
    "&= \\frac{\\sum_{k=0}^{N-1} \\alpha_k}{N} \\sum_{x=0}^{N-1} | x \\rangle = \\langle \\alpha \\rangle \\sum_{x=0}^{N-1} | x \\rangle = \\langle \\alpha \\rangle \\sum_{k=0}^{N-1} | k \\rangle\n",
    "\\end{align*}\n",
    "$$\n",
    "\n",
    "最后一个等号仅仅是角标的替换而已。随即，\n",
    "\n",
    "$$\n",
    "\\big( 2 |\\psi\\rangle\\langle\\psi| - I \\big) = 2 \\langle \\alpha \\rangle \\sum_{k=0}^{N-1} | k \\rangle - \\sum_{k=0}^{N-1} | k \\rangle\n",
    "= \\sum_{k=0}^{N-1} \\big( - \\alpha_k + 2 \\langle \\alpha \\rangle \\big) |k\\rangle\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ccf5e800",
   "metadata": {},
   "source": [
    "## 练习 6.3"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "47edcd85",
   "metadata": {},
   "source": [
    ":::{admonition} 练习 6.3\n",
    "\n",
    "证明 $|\\alpha\\rangle, |\\beta\\rangle$ 基中，可以把 Grover 迭代写成\n",
    "\n",
    "$$\n",
    "G = \\begin{bmatrix} \\cos\\theta & -\\sin\\theta \\\\ \\sin\\theta & \\cos\\theta \\end{bmatrix}\n",
    "$$\n",
    "\n",
    "其中 $\\theta$ 是一个 $0$ 到 $2 \\pi$ 之间的实数 (为简单起见，假定 $M \\leqslant N/2$，这个限制很快会取消)，它满足\n",
    "\n",
    "$$\n",
    "\\sin\\theta = \\frac{2 \\sqrt{M (N-M)}}{N}\n",
    "$$\n",
    "\n",
    ":::"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6a111221",
   "metadata": {},
   "source": [
    "首先，我们很容易表明题目中所给的 $\\theta$ 与正文的定义相同。我们回顾到正文中定义\n",
    "\n",
    "$$\n",
    "|\\psi\\rangle = \\sqrt{\\frac{N-M}{N}} |\\alpha\\rangle + \\sqrt{\\frac{M}{N}} |\\beta\\rangle = \\cos \\frac{\\theta}{2} |\\alpha\\rangle + \\sin \\frac{\\theta}{2} |\\beta\\rangle\n",
    "$$\n",
    "\n",
    "因此，\n",
    "\n",
    "$$\n",
    "\\sin \\theta = 2 \\cos \\frac{\\theta}{2} \\sin \\frac{\\theta}{2} = 2 \\sqrt{\\frac{N-M}{N}} \\sqrt{\\frac{M}{N}} = \\frac{2 \\sqrt{M (N-M)}}{N}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "272394f8",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "adea12bb",
   "metadata": {},
   "source": [
    "随后我们利用矩阵下的表示来作说明。首先，$|\\psi\\rangle$ 在基 $\\{ |\\alpha\\rangle, |\\beta\\rangle \\}$ 下的表示向量是\n",
    "\n",
    "$$\n",
    "|\\psi\\rangle = \\begin{bmatrix} \\cos \\frac{\\theta}{2} \\\\ \\sin \\frac{\\theta}{2} \\end{bmatrix}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d53d7edc",
   "metadata": {},
   "source": [
    "那么其外积是\n",
    "\n",
    "$$\n",
    "|\\psi\\rangle \\langle\\psi|\n",
    "= \\begin{bmatrix} \\cos^2 \\frac{\\theta}{2} & \\sin \\frac{\\theta}{2} \\cos \\frac{\\theta}{2} \\\\ \\sin \\frac{\\theta}{2} \\cos \\frac{\\theta}{2} & \\sin^2 \\frac{\\theta}{2} \\end{bmatrix}\n",
    "= \\frac{1}{2} \\begin{bmatrix} \\cos \\theta + 1 & \\sin \\theta \\\\ \\sin \\theta & 1 - \\cos \\theta \\end{bmatrix}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9087fb16",
   "metadata": {},
   "source": [
    "而依据运算 $O$ 的定义\n",
    "\n",
    "$$\n",
    "O(a |\\alpha\\rangle + b |\\beta\\rangle) = a |\\alpha\\rangle - b |\\beta\\rangle\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e0662129",
   "metadata": {},
   "source": [
    "我们知道其矩阵表示类似于 $Z$ 算符：\n",
    "\n",
    "$$\n",
    "O = \\begin{bmatrix} 1 & 0 \\\\ 0 & -1 \\end{bmatrix}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4c926e85",
   "metadata": {},
   "source": [
    "因此，\n",
    "\n",
    "$$\n",
    "G = (2 |\\psi\\rangle \\langle\\psi| - I) O = \\begin{bmatrix} \\cos \\theta & \\sin \\theta \\\\ \\sin \\theta & - \\cos \\theta \\end{bmatrix} \\begin{bmatrix} 1 & 0 \\\\ 0 & -1 \\end{bmatrix} = \\begin{bmatrix} \\cos \\theta & - \\sin \\theta \\\\ \\sin \\theta & \\cos \\theta \\end{bmatrix}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "162326db",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b7a6261a",
   "metadata": {},
   "source": [
    "这道题的直观思路显然是书中的图 6.3。它将 $|\\psi\\rangle$ 逆时针旋转了 $\\theta$ 角度。这种旋转效应确实可以写为待证的 $\\begin{bmatrix} \\cos \\theta & - \\sin \\theta \\\\ \\sin \\theta & \\cos \\theta \\end{bmatrix}$ 矩阵。但需要指出，这道题的证明应当对任何向量都要有效，而不只是均衡叠加态 $|\\psi\\rangle$ 有效。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9d0bbe8c",
   "metadata": {},
   "source": [
    "## 练习 6.4"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3296edc4",
   "metadata": {},
   "source": [
    ":::{admonition} 练习 6.4\n",
    "\n",
    "像上面那样，对多解情况 ($1 < M < N/2$)，给出量子搜索算法的具体步骤。\n",
    "\n",
    ":::"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "78374100",
   "metadata": {},
   "source": [
    "我认为唯一的区别在于应用 Grover 迭代的次数 $R$。这在式 (6.17) 中有阐述：\n",
    "\n",
    "$$\n",
    "R \\leqslant \\left\\lceil \\frac{\\pi}{4} \\sqrt{\\frac{N}{M}} \\right\\rceil\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "df52add9",
   "metadata": {},
   "source": [
    "## 练习 6.5"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1eb3d54e",
   "metadata": {},
   "source": [
    ":::{admonition} 练习 6.5\n",
    "\n",
    "证明用一次 $O$ 调用，基本量子门和附加的量子比特 $|q\\rangle$ 可以构造增广的 oracle $O'$。\n",
    "\n",
    ":::"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "edd52b39",
   "metadata": {},
   "source": [
    "该问题的解答参考下述网页：\n",
    "\n",
    "> https://serab.net/docs/qcqi/chapter6/"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b371c501",
   "metadata": {},
   "source": [
    "构造下述量子线路：\n",
    "\n",
    "![ex-6.5.1](assets/ex-6.5.1.svg)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d0d35276",
   "metadata": {},
   "source": [
    "首先，如果 $|q\\rangle$ 是 $|0\\rangle$，那么总的量子线路的作用相当于\n",
    "\n",
    "$$\n",
    "|0\\rangle |x\\rangle \\frac{|0\\rangle - |1\\rangle}{\\sqrt{2}} \\xrightarrow{\\text{orcale}} |0\\rangle (-1)^{f(x)} |x\\rangle \\frac{|0\\rangle - |1\\rangle}{\\sqrt{2}} = (-1)^{f(x)} |0\\rangle |x\\rangle \\frac{|0\\rangle - |1\\rangle}{\\sqrt{2}}\n",
    "$$\n",
    "\n",
    "因此，对于 $|q\\rangle$ 为 $|0\\rangle$ 的情况，$|x\\rangle$ 是否是解可以从相位是否翻转看出。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "12f466f9",
   "metadata": {},
   "source": [
    "但若 $|q\\rangle$ 是 $|1\\rangle$，那么在进入未增广的 orcale 门 $O$ 之前，最后的工作量子比特变成了 $(|0\\rangle + |1\\rangle) / \\sqrt{2}$。因此，\n",
    "\n",
    "$$\n",
    "|1\\rangle |x\\rangle \\frac{|0\\rangle - |1\\rangle}{\\sqrt{2}} \\xrightarrow{Z\\text{ gate}} |1\\rangle |x\\rangle \\frac{|0\\rangle + |1\\rangle}{\\sqrt{2}} \\xrightarrow{\\text{orcale}} 1^{f(x)} |1\\rangle |x\\rangle \\frac{|0\\rangle + |1\\rangle}{\\sqrt{2}} \\xrightarrow{Z\\text{ gate}} |1\\rangle |x\\rangle \\frac{|0\\rangle - |1\\rangle}{\\sqrt{2}}\n",
    "$$\n",
    "\n",
    "这意味着，对于 $|q\\rangle$ 为 $|1\\rangle$ 的情况，经过增广的 orcale $O'$ 之后，相位并未发生变化，即没有标识为解。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3bca90f2",
   "metadata": {},
   "source": [
    "## 练习 6.6"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8e201c86",
   "metadata": {},
   "source": [
    ":::{admonition} 练习 6.6\n",
    "\n",
    "验证除了一个无关紧要的全局相位因子 $\\alpha$，盒子 6.1 第二个图中带点的框中的门完成相移运算 $2 |00\\rangle \\langle00| - I$。\n",
    "\n",
    "![ex-6.6.1](assets/ex-6.6.1.svg)\n",
    "\n",
    ":::"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e0a6ede9",
   "metadata": {},
   "source": [
    "首先，对于第一个量子比特，在控制点两边各有 $X$ 门相当于以 $|0\\rangle$ 为控制；而对于第二个量子比特，由于 $XHXHX = XZX = -Z$、以及 $XHHX = I$，因此总地来说该门路等价于以第一个量子比特 $|0\\rangle$ 为控制的受控 $-Z$ 门：\n",
    "\n",
    "![ex-6.6.2](assets/ex-6.6.2.svg)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6bcc8c3b",
   "metadata": {},
   "source": [
    "随后就分别使用 $|00\\rangle, |01\\rangle, |10\\rangle, |11\\rangle$ 代入门路，可以得到输出结果是 $- |00\\rangle, |01\\rangle, |10\\rangle, |11\\rangle$。因此，该门路其实是\n",
    "\n",
    "$$\n",
    "- 2 |00\\rangle \\langle00| + I = e^{i \\pi} (2 |00\\rangle \\langle00| - I)\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
}