{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "ffab4c42",
   "metadata": {},
   "source": [
    "# 5.2 相位估计"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "966de2f9",
   "metadata": {},
   "source": [
    "## 练习 5.7"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ac74138b",
   "metadata": {},
   "source": [
    ":::{admonition} 练习 5.7\n",
    "\n",
    "通过证明图 5.2 中那样的受控 $U$ 运算会将状态 $|j\\rangle |u\\rangle$ 转换为 $|j\\rangle U^j |u\\rangle$，从而对图 5.2 线路可以有更为深刻的认识。现在就证明这一点 (注意这并不依赖于 $|u\\rangle$ 是 $U$ 的本征态)。\n",
    "\n",
    ":::"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f62e011e",
   "metadata": {},
   "source": [
    "这里需要补充的是，这里的 $|j\\rangle$ 必须是可以由二进制数储存的态，或者说是 $n$ 量子比特计算基的其中一个态；即 $|j_1 j_2 \\cdots j_n\\rangle$，其中 $j_1, j_2, \\cdots, j_n \\in \\{0, 1\\}$。同时，我们不考察图 5.2 中的 Hadamard 门：\n",
    "\n",
    "![ex-5.7.1](assets/ex-5.7.1.svg)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7244968e",
   "metadata": {},
   "source": [
    "首先，由于 $|j\\rangle$ 是计算基的态，因此经过控制节点后，仍然保持其结果而不更改相位。\n",
    "\n",
    "对于 $|u\\rangle$ 线路上的作用，以 $|j_1\\rangle$ 为例，若 $|j_1\\rangle = |1\\rangle$，则作用 $U^{2^n} = U^{j_1 2^n}$；若 $|j_1\\rangle = |0\\rangle$，则作用 $I = U^{j_1 2^n}$。因此，无论如何都可以表示为 $U^{j_1 2^n}$ 的作用。其它控制门路同理，因此我们得到\n",
    "\n",
    "$$\n",
    "\\begin{align*}\n",
    "|u\\rangle &\\rightarrow U^{j_1 2^n} U^{j_2 2^{n-1}} \\cdots U^{j_{n-1} 2^1} U^{j_n 2^0} |u\\rangle \\\\\n",
    "&= U^{j_1 2^n + j_2 2^{n-1} + j_{n-1} 2^1 + j_n 2^0} |u\\rangle = U^j |u\\rangle\n",
    "\\end{align*}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2d30b85f",
   "metadata": {},
   "source": [
    "## 练习 5.8"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "572bdcb2",
   "metadata": {},
   "source": [
    ":::{admonition} 练习 5.8\n",
    "\n",
    "设相位估计算法把状态 $|0\\rangle |u\\rangle$ 变为状态 $|\\tilde \\varphi_u\\rangle |u\\rangle$，那么若给定输入 $|0\\rangle \\left( \\sum_u c_u |u\\rangle \\right)$ 时，算法的输出为 $\\sum_u c_u |\\tilde \\varphi_u\\rangle |u\\rangle$。证明如果 $t$ 按照式 (5.35) 选择，则在相位估计算法后精确到 $n$ 比特测量 $\\varphi_u$ 的概率，至少是 $|c_u|^2 (1-\\varepsilon)$。\n",
    "\n",
    ":::"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4f3fed59",
   "metadata": {},
   "source": [
    "这个问题看上去很显然；由于测得 $\\varphi_u$ 意味着对应到本征态 $|u\\rangle$，而这个本征态的出现概率就是 $|c_u|^2$；因此与测量概率准度 $(1-\\varepsilon)$ 相乘，立即得到了 $|c_u|^2 (1-\\varepsilon)$。当然，这个概率显然还是得要比 $|c_u|^2$ 要小的。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "44c704b3",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3f63e606",
   "metadata": {},
   "source": [
    "书上说要有“严格化”(rigorous) 的论证；但我确实觉得，有这样一个直觉已经很充分了。\n",
    "\n",
    "只是题目假定了相位估计过程，包括第一阶段的本征相位寄存、第二阶段的逆向 Fourier 过程，都是是线性的；但这个结论不一定很显然。我们在此作简要的证明。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "180bf70f",
   "metadata": {},
   "source": [
    "**补充约定**"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6d3bed7d",
   "metadata": {},
   "source": [
    "题目中的 $|0\\rangle |u\\rangle$ 记号是容易产生误导的。由于我们关心的是算符 $U$ 的本征态，因此这里的 $|u\\rangle$ 需要在维度上与 $U$ 所作用的空间相同。$|0\\rangle$ 其实是 $t$ 个第一寄存器的控制比特态 $|00\\cdots0\\rangle$，只是用以表征二进制数值 $0\\times 2^0 + 0 \\times 2^1 + \\cdots + 0 \\times 2^t = 0$ 而已。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ff47cf31",
   "metadata": {},
   "source": [
    "我们同时约定，以后记号中出现的 $|u\\rangle$ 是任意的 $U$ 本征态，$|\\mathscr{u}\\rangle$ 是其中我们关心的本征态。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3101ef2b",
   "metadata": {},
   "source": [
    "**线性叠加态的相位估计第一阶段**"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d1158d60",
   "metadata": {},
   "source": [
    "首先我们考察相位估计第一阶段。回顾到对于单一的本征态 $|u\\rangle$ 而言，其本征值是 $e^{2 \\pi i \\varphi_u}$，那么该过程下，第一寄存器的 $t$ 个量子比特状态为\n",
    "\n",
    "$$\n",
    "|00\\cdots0\\rangle |u\\rangle \\rightarrow \\frac{1}{2^{t/2}} \\bigotimes_{j=1}^t \\big( |0\\rangle + e^{2 \\pi i 2^{t-j} \\varphi_u} |1\\rangle \\big) |u\\rangle = \\frac{1}{2^{t/2}} \\sum_{k=0}^{2^t-1} e^{2 \\pi i \\varphi_u k} |k\\rangle |u\\rangle\n",
    "\\tag{5.20}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "775f1631",
   "metadata": {},
   "source": [
    "现在我们考察第二寄存器代入的是线性组合态 $\\sum_{u} c_u |u\\rangle$。首先引入一个引理。这里需要假设 $U$ 是线性算符 (量子门路一般都有该要求)；并且利用到本征态 $|u\\rangle$ 和本征值 $e^{2 \\pi i \\varphi_u}$ 因此，\n",
    "\n",
    "$$\n",
    "\\begin{align*}\n",
    "U^{m} \\sum_u c_u |u\\rangle\n",
    "&= U^{m-1} \\sum_u c_u U |u\\rangle = U^{m-1} \\sum_u c_u e^{2 \\pi i \\varphi_u} |u\\rangle \\\\\n",
    "&= U^{m-2} \\sum_u c_u e^{2 \\pi i \\varphi_u} U |u\\rangle = U^{m-1} \\sum_u c_u e^{2 \\pi i \\varphi_u \\times 2} |u\\rangle \\\\\n",
    "&= \\cdots = \\sum_u c_u e^{2 \\pi i \\varphi_u m} |u\\rangle\n",
    "\\end{align*}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5dc5b651",
   "metadata": {},
   "source": [
    "现在我们考虑第一次控制过程，即在第 $t$ 个量子比特 $|0\\rangle$ 上引入 Hadamard 门后施加 $\\text{ctrl-}U$ 门：\n",
    "\n",
    "$$\n",
    "\\begin{alignat*}{10}\n",
    "\\underbrace{|00\\cdots0\\rangle}_{t-1} |0\\rangle \\sum_u c_u |u\\rangle \\;\n",
    "&& \\xrightarrow{H \\text{ Gate at Qubit } t} \\; &\n",
    "\\frac{1}{\\sqrt{2}} \\underbrace{|00\\cdots0\\rangle}_{t-1} \\left( |0\\rangle \\sum_u c_u |u\\rangle + |1\\rangle \\sum_u c_u |u\\rangle \\right) \\\\\n",
    "&& \\xrightarrow{\\text{Qubit } t \\text{ ctrl-}U} \\; &\n",
    "\\frac{1}{\\sqrt{2}} \\underbrace{|00\\cdots0\\rangle}_{t-1} \\left( |0\\rangle \\sum_u c_u |u\\rangle + |1\\rangle U \\sum_u c_u |u\\rangle \\right) \\\\\n",
    "&& =\\; &\n",
    "\\frac{1}{\\sqrt{2}} \\underbrace{|00\\cdots0\\rangle}_{t-1} \\left( |0\\rangle \\sum_u c_u |u\\rangle + |1\\rangle \\sum_u c_u e^{2 \\pi i \\varphi_u 2^0} |u\\rangle \\right) \\\\\n",
    "&& =\\; &\n",
    "\\frac{1}{\\sqrt{2}} \\underbrace{|00\\cdots0\\rangle}_{t-1} \\sum_u c_u \\left( |0\\rangle + e^{2 \\pi i \\varphi_u 2^0} |1\\rangle \\right) |u\\rangle\n",
    "\\end{alignat*}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8ef45fdd",
   "metadata": {},
   "source": [
    "沿用上面的结果，再考虑第二次控制过程，即在第 $t-1$ 个量子比特 $|0\\rangle$ 上引入 Hadamard 门后施加 $\\text{ctrl-}U^2$ 门：\n",
    "\n",
    "$$\n",
    "\\begin{alignat*}{10}\n",
    "&& \\xrightarrow{H \\text{ Gate at Qubit } t-1} \\; &\n",
    "\\frac{1}{\\left(\\sqrt{2}\\right)^2} \\underbrace{|00\\cdots0\\rangle}_{t-2} \\big( |0\\rangle + |1\\rangle \\big) \\sum_u c_u \\left( |0\\rangle + e^{2 \\pi i \\varphi_u 2^0} |1\\rangle \\right) |u\\rangle \\\\\n",
    "&& \\xrightarrow{\\text{Qubit } t \\text{ ctrl-}U^2} \\; &\n",
    "\\frac{1}{\\left(\\sqrt{2}\\right)^2} \\underbrace{|00\\cdots0\\rangle}_{t-2} \\left( |0\\rangle \\sum_u c_u \\left( |0\\rangle + e^{2 \\pi i \\varphi_u 2^0} |1\\rangle \\right) |u\\rangle + |1\\rangle \\sum_u c_u \\left( |0\\rangle + e^{2 \\pi i \\varphi_u 2^0} |1\\rangle \\right) U^2 |u\\rangle \\right) \\\\\n",
    "&& =\\; &\n",
    "\\frac{1}{\\left(\\sqrt{2}\\right)^2} \\underbrace{|00\\cdots0\\rangle}_{t-2} \\sum_u c_u \\left( |0\\rangle + e^{2 \\pi i \\varphi_u 2^1} |1\\rangle \\right) \\left( |0\\rangle + e^{2 \\pi i \\varphi_u 2^0} |1\\rangle \\right) |u\\rangle\n",
    "\\end{alignat*}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e1bfa113",
   "metadata": {},
   "source": [
    "如此往复，可以得到第一阶段后，状态会成为\n",
    "\n",
    "$$\n",
    "\\underbrace{|00\\cdots0\\rangle}_{t} \\sum_u c_u |u\\rangle \\xrightarrow{\\text{First Stage}} \\frac{1}{2^{t/2}} \\sum_u c_u \\bigotimes_{j=1}^t \\left( |0\\rangle + e^{2 \\pi i 2^{t-j} \\varphi_u} |1\\rangle \\right) |u\\rangle\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "675713ae",
   "metadata": {},
   "source": [
    "因此，可以表明相位估计的第一阶段操作是线性的。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2cc24331",
   "metadata": {},
   "source": [
    "**线性叠加态的相位估计第二阶段**"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "11ff4ad3",
   "metadata": {},
   "source": [
    "第二阶段是逆 Fourier 变换；它与 Fourier 变换相似，都是线性操作。这里不再证明了。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bc5ca7d6",
   "metadata": {},
   "source": [
    "**关于测量**"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bcf45d48",
   "metadata": {},
   "source": [
    "我认为，对于混合态的测量，不应该会发生“跨态”测量。这是能保证测量 $t$ 量子比特态 $\\sum_u c_u |\\tilde \\varphi_u \\rangle |u\\rangle$ 的全部第一寄存器比特时，它必然坍缩到其中一个 $|\\tilde \\varphi_\\mathscr{u} \\rangle$ 上；而非可能测得一部分在 $|\\tilde \\varphi_\\mathscr{u} \\rangle$，另一部分在 $|\\tilde \\varphi_u \\rangle \\neq |\\tilde \\varphi_\\mathscr{u} \\rangle$ 上。因此，测量得到态 $|\\tilde \\varphi_\\mathscr{u} \\rangle$ 所给出的概率确实就会是其线性组合系数的模 $|c_\\mathscr{u}|^2$。当然这要基于 $U$ 的本征态非简并的前提。\n",
    "\n",
    "举例而言，在测量 Bell 态 $\\frac{1}{\\sqrt{2}} (|00\\rangle + |11\\rangle)$ 的两个量子比特时，不可能测得第一个比特为 $|0\\rangle$，而第二个比特为 $|1\\rangle$。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e324ad36",
   "metadata": {},
   "source": [
    "## 练习 5.9"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "df1997f2",
   "metadata": {},
   "source": [
    ":::{admonition} 练习 5.9\n",
    "\n",
    "令 $U$ 是一个特征值为 $\\pm 1$ 的酉变换，作用在一个状态 $|\\psi\\rangle$ 上。利用相位估计过程，构造一个量子线路，使得 $|\\psi\\rangle$ 坍缩到 $U$ 的两个本征态之一，并给出最终状态在哪个空间的一个经典指示器。与练习 4.34 的结果进行比较。\n",
    "\n",
    ":::"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "feffdf38",
   "metadata": {},
   "source": [
    "实际上练习 4.34 的线路就是我们所需要的线路。\n",
    "\n",
    "![ex-4.34.1](../chap_04/assets/ex-4.34.1.svg)\n",
    "\n",
    "相位估计过程等价于练习 4.34 的结果：\n",
    "\n",
    "- 第一阶段使用 Hadamard 门与受控 $U$ 门，这与练习 4.34 完全一致；\n",
    "- 第二阶段是逆向 Fourier 变换；对于单比特的 Fourier 变换，其需要的门路是 $H$，那么逆向 Fourier 的门路是 $H^\\dagger = H$，恰好与练习 4.34 一致。"
   ]
  }
 ],
 "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
}