{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "c71f3f8d",
   "metadata": {},
   "source": [
    "# 5.1 量子 Fourier 变换"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c06c5c94",
   "metadata": {},
   "source": [
    "## 练习 5.1"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "508a48ad",
   "metadata": {},
   "source": [
    ":::{admonition} 练习 5.1\n",
    "\n",
    "给出式 (5.2) 定义的线性变换是酉变换的直接证明。\n",
    "\n",
    "$$\n",
    "|j\\rangle \\rightarrow \\frac{1}{\\sqrt{N}} \\sum_{k=0}^{N-1} e^{2 i \\pi j k / N} |k\\rangle\n",
    "\\tag{5.2}\n",
    "$$\n",
    "\n",
    ":::"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bd0ace42",
   "metadata": {},
   "source": [
    "首先，依据该式，可以给出 Fourier 变换的矩阵元 $F_{jk}$ 可以写为\n",
    "\n",
    "$$\n",
    "F_{jk} = \\frac{1}{\\sqrt{N}} e^{2 i \\pi j k / N}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fd551f31",
   "metadata": {},
   "source": [
    "为了证明该变换是酉变换，我们尝试求取其自伴矩阵 $F^\\dagger$ 与 $F$ 之间的乘积，以验证是否 $F^\\dagger F = I$。回顾到自伴矩阵 $F^\\dagger$ 是 $F$ 的共轭转置。我们对矩阵元 $jk$ 作考察："
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ffbf35f1",
   "metadata": {},
   "source": [
    "$$\n",
    "\\begin{align*}\n",
    "(F^\\dagger F)_{jk} &= \\sum_{l=0}^{N-1} (F^\\dagger)_{jl} F_{lk} = \\sum_{l=0}^{N-1} F_{lj}^* F_{lk} \\\\\n",
    "&= \\frac{1}{N} \\sum_{l=0}^{N-1} e^{- 2 i \\pi lj / N} e^{2 i \\pi lk / N} = \\frac{1}{N} \\sum_{l=0}^{N-1} e^{2 i \\pi (k-j) l / N}\n",
    "\\end{align*}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f25db100",
   "metadata": {},
   "source": [
    "下面要分两种情况考虑。若 $k = j$，则上式化为\n",
    "\n",
    "$$\n",
    "(F^\\dagger F)_{jj} = \\frac{1}{N} \\sum_{l=0}^{N-1} e^{0 \\times 2 i l / N} = \\frac{1}{N} \\sum_{l=0}^{N-1} 1 = 1\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "911f77c8",
   "metadata": {},
   "source": [
    "若 $k \\neq j$，那么若将 $e^{2 i \\pi (k-j) l / N}$ 看作关于自然数 $l$ 的数列，那么它是等比数列，且比例 $\\omega$ 是 $\\omega = e^{2 i \\pi (k-j) / N}$。又由于 $0 \\leqslant j, k \\leqslant N-1$，因此易推知 $0 < |k-j| < N$，即 $\\omega = e^{2 i \\pi (k-j) / N} \\neq e^{2 \\pi i} = 1$。因此，该等比数列的求和可以套用公式\n",
    "\n",
    "$$\n",
    "(F^\\dagger F)_{jk} = \\frac{1}{N} \\sum_{l=0}^{N-1} \\omega^l = \\frac{1}{N} \\frac{1 - \\omega^N}{1 - \\omega}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "58585012",
   "metadata": {},
   "source": [
    "但由于 $k-j$ 是整数，因此 $\\omega^N = e^{2 i \\pi (k-j)} = 1$。因此，当 $j \\neq k$ 时，$(F^\\dagger F)_{jk} = 0$。综上，\n",
    "\n",
    "$$\n",
    "(F^\\dagger F)_{jk} = \\delta_{jk} \\quad \\text{i.e.} \\quad F^\\dagger F = I\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d9815c9b",
   "metadata": {},
   "source": [
    "## 练习 5.2"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0df2f913",
   "metadata": {},
   "source": [
    ":::{admonition} 练习 5.2\n",
    "\n",
    "具体计算 $n$ 量子比特状态 $|00\\cdots0\\rangle$ 的 Fourier 变换。\n",
    "\n",
    ":::"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "efe8e44e",
   "metadata": {},
   "source": [
    "直接套用式 (5.2)，代入 $j = 0$，得到\n",
    "\n",
    "$$\n",
    "|00\\cdots0\\rangle \\rightarrow \\frac{1}{\\sqrt{N}} \\sum_{k=0}^{N-1} |k\\rangle = \\frac{1}{\\sqrt{2^n}} \\sum_{k=0}^{2^n-1} |k\\rangle\n",
    "$$\n",
    "\n",
    "但这里需要说明，首先作为 $n$ 量子比特状态，因此 $|k\\rangle$ 有 $2^n$ 种可能构造，因此 $N = 2^n$。其次，在原先的式 (5.2) 中，$|k\\rangle$ 代表的是态，而 $e^{2 i \\pi jk / N}$ 中的 $k$ 是该态对应的、可以用于运算的二进制数。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d4416537",
   "metadata": {},
   "source": [
    "但这里需要说明，首先作为 $n$ 量子比特状态，因此 $|k\\rangle$ 有 $2^n$ 种可能构造，因此 $N = 2^n$。其次，在原先的式 (5.2) 中，$|k\\rangle$ 代表的是态，而 $e^{2 i \\pi jk / N}$ 中的 $k$ 是该态对应的、可以用于运算的二进制数。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f7364067",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "df8579ab",
   "metadata": {},
   "source": [
    "我们换一个更具体、且与原题不同的例子。对于 $|j\\rangle = |01\\rangle$ 时，其量子比特数 $n = 2$，其态对应的数值是 $j = 1$，其 Fourier 变换则会是\n",
    "\n",
    "$$\n",
    "|01\\rangle \\rightarrow \\frac{1}{\\sqrt{2^2}} \\sum_{k=0}^{2^2 - 1} e^{2 i \\pi \\times 1 \\times k / N} |k\\rangle = \\frac{1}{2} \\big( |00\\rangle + e^{\\frac{1}{4} 2 i \\pi} |01\\rangle + e^{\\frac{2}{4} 2 i \\pi} |10\\rangle + e^{\\frac{3}{4} 2 i \\pi} |11\\rangle \\big)\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "83111e1c",
   "metadata": {},
   "source": [
    "有时为了方便和简洁起见，会用 $\\omega = e^{\\frac{1}{4} 2 i \\pi}$ 对上式作记号简化，即 Fourier 变换是\n",
    "\n",
    "$$\n",
    "|01\\rangle \\rightarrow \\frac{1}{2} \\big( |00\\rangle + \\omega |01\\rangle + \\omega^2 |10\\rangle + \\omega^3 |11\\rangle \\big)\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5233034e",
   "metadata": {},
   "source": [
    "## 练习 5.3 (经典快速 Fourier 变换)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "311f2544",
   "metadata": {},
   "source": [
    ":::{admonition} 练习 5.3\n",
    "\n",
    "在一个经典计算机上进行一个包含 $2^n$ 个复数向量的 Fourier 变换，验证基于式 (5.1) 的直接方法进行 Fourier 变换，需要 $\\Theta (2^{2n})$ 个基本算术运算。验证基于式 (5.4) 的运算方法，算术运算数量降低到 $\\Theta (n 2^n)$ 个。\n",
    "\n",
    ":::"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b68db02f",
   "metadata": {},
   "source": [
    "我们不严格分析 $\\Theta$ 与 $\\text{big-}O$ 的区别，只是大致作讨论。\n",
    "\n",
    "对于 $n$ 比特的运算 (即 $N = 2^n$ 的离散向量 Fourier 变换)\n",
    "\n",
    "$$\n",
    "y_k = \\frac{1}{\\sqrt{N}} \\sum_{j=0}^{N-1} x_j e^{2 i \\pi j k / N}\n",
    "\\tag{5.1}\n",
    "$$\n",
    "\n",
    "我们若认为 $j \\times k$ 的乘法运算是 $O(1)$ 的，那么\n",
    "\n",
    "- $e^{2 i \\pi j k / N}$ 的运算是 $O(1)$ 的；\n",
    "- 求和操作 $\\sum_{j=0}^{N-1}$ 需要 $N=2^n$ 次运算；\n",
    "- 我们需要求得 $y_1, y_2, \\cdots, y_N$，因此一共要求取 $N=2^n$ 个值。\n",
    "\n",
    "综上，运算数是 $2^n \\times 2^n \\times O(1) = O(2^{2n})$。但需要指出，若 $n$ 比特乘法 $j \\times k$ 的运算被认为是 $O(n)$ 的 (因为我们需要处理类似于 $j \\times k, j \\times (k+1)$ 等连续乘法，因此乘法完全可以当作加法来处理；否则不使用加法的话，应该至少是 $O(n \\log n \\log \\log n)$)，那么运算数应该是 $O(n 2^{2n})$。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b158dc1f",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c56db232",
   "metadata": {},
   "source": [
    "若使用下式，\n",
    "\n",
    "$$\n",
    "|j_1j_2 \\cdots j_n \\rangle \\rightarrow \\frac{1}{2^{n/2}} \\big( |0\\rangle + e^{2 i \\pi \\times 0.j_n} |1\\rangle \\big) \\big( |0\\rangle + e^{2 i \\pi \\times 0.j_{n-1} j_n} |1\\rangle \\big) \\cdots \\big( |0\\rangle + e^{2 i \\pi \\times 0.j_1j_2 \\cdots j_n} |1\\rangle \\big)\n",
    "\\tag{5.4}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "57437f13",
   "metadata": {},
   "source": [
    "- 构造 $|0\\rangle + e^{2 i \\pi \\times 0.j_lj_{l+1}\\cdots j_n} |1\\rangle$ 的时间至多是 $O(n)$，且相比后续计算，可以忽略；\n",
    "- 乘法表达式还不是 $N = 2^n$ 个向量分量的线性组合，我们最后还要求线性组合的系数 (相当于式 (5.1) 中的 $y_k$)；\n",
    "- 对于线性组合系数，我们需要进行至多 $n$ 次或平均 $n/2$ 次乘法求出，即 $\\Theta (n)$ 次乘法。\n",
    "\n",
    "因此，运算数是 $O(n) + 2^n \\Theta (n) = \\Theta (n 2^n)$。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "132992df",
   "metadata": {},
   "source": [
    "## 练习 5.4"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1c092455",
   "metadata": {},
   "source": [
    ":::{admonition} 练习 5.4\n",
    "\n",
    "给出受控 $R_k$ 门到单量子比特门和受控非门的一个分解。\n",
    "\n",
    ":::"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c0e21850",
   "metadata": {},
   "source": [
    "为了解该题，我们要回顾图 4.6。我们需要找到三个算符 $A, B, C$ 与相位因子 $\\alpha$，使得 $R_k = e^{- i \\alpha} AXBXC$，且 $ABC = I$。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "58abe34f",
   "metadata": {},
   "source": [
    "我们回顾到 $R_k$ 的表达式\n",
    "\n",
    "$$\n",
    "R_k = \\begin{bmatrix} 1 & 0 \\\\ 0 & e^{2 \\pi i / 2^k} \\end{bmatrix} = e^{\\pi i / 2^k} \\begin{bmatrix} e^{- \\pi i / 2^k} & 0 \\\\ 0 & e^{\\pi i / 2^k} \\end{bmatrix} = e^{\\pi i / 2^k} R_z \\left( \\frac{\\pi}{2^{k-1}} \\right)\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5657bcff",
   "metadata": {},
   "source": [
    "我们回顾到 $X R_z(\\theta) X = R_z (- \\theta)$ (可以参考练习 4.7 的证明)，那么\n",
    "\n",
    "$$\n",
    "R_k = e^{\\pi i / 2^k} R_z \\left( \\frac{\\pi}{2^{k-1}} \\right) = e^{\\pi i / 2^k} R_z \\left( \\frac{\\pi}{2^{k}} \\right) R_z \\left( \\frac{\\pi}{2^{k}} \\right) = e^{\\pi i / 2^k} X R_z \\left( - \\frac{\\pi}{2^{k}} \\right) X R_z \\left( \\frac{\\pi}{2^{k}} \\right)\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "13034edc",
   "metadata": {},
   "source": [
    "因此，我们可以令\n",
    "\n",
    "$$\n",
    "\\alpha = \\pi/2^k, \\; A = I, \\; B = R_z (- \\pi/2^k), \\; C = R_z (\\pi/2^k)\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "63c3be1a",
   "metadata": {},
   "source": [
    "我们若令 $P_{\\alpha}$ 是下述门路：\n",
    "\n",
    "$$\n",
    "P_\\alpha = \\begin{bmatrix} 1 & 0 \\\\ 0 & e^{i \\alpha} \\end{bmatrix} = e^{- i \\alpha/2} R_z (\\alpha) \n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8930d59e",
   "metadata": {},
   "source": [
    "那么其对应的线路图，依据书中的图 4.6，可以绘制为\n",
    "\n",
    "![ex-5.4.1](assets/ex-5.4.1.svg)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "97a4155c",
   "metadata": {},
   "source": [
    "## 练习 5.5"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e391456c",
   "metadata": {},
   "source": [
    ":::{admonition} 练习 5.5\n",
    "\n",
    "给出进行逆量子 Fourier 变换的一个量子线路。\n",
    "\n",
    ":::"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "467e2212",
   "metadata": {},
   "source": [
    "对比式 (5.1)，逆 Fourier 变换可以如下定义：\n",
    "\n",
    "$$\n",
    "x_j = \\frac{1}{\\sqrt{N}} \\sum_{k=0}^{N-1} y_k e^{- 2 i \\pi jk / N}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bad80ee2",
   "metadata": {},
   "source": [
    "这实际上就是与 Fourier 变换的所有相位取负而已。因此，将图 5.1 Fourier 变换的量子线路的所有 $R_k$ 替换为 $R_k^\\dagger$ 即得到逆 Fourier 变换的线路了。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d93091ce",
   "metadata": {},
   "source": [
    "另一种做法如书中后文所述，将线路对调也可以实现。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0fd5c362",
   "metadata": {},
   "source": [
    "## 练习 5.6 (量子 Fourier 变换的近似)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9d25d771",
   "metadata": {},
   "source": [
    ":::{admonition} 练习 5.6\n",
    "\n",
    "量子 Fourier 变换的量子线路结构，表面上需要用到的门路个数为量子比特数目的指数量级；然而，多项式规模的量子线路永远不需要这样的精度。例如，令 $U$ 是 $n$ 量子比特上的理想 Fourier 变换，而 $V$ 是以精度 $\\Delta = 1 / p(n)$ 完成受控 $R_k$ 门得到的结果，其中 $p(n)$ 是某个多项式。证明误差\n",
    "\n",
    "$$\n",
    "E(U, V) = \\max_{|\\psi\\rangle} \\Vert (U-V) |\\psi\\rangle \\Vert = \\Theta (n^2 / p(n))\n",
    "$$\n",
    "\n",
    "因此每个门的多项式精度对保证输出状态的多项式精度就够了。\n",
    "\n",
    ":::"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7ed7b489",
   "metadata": {},
   "source": [
    "首先，回顾盒子 4.1 的式 (4.69) 结论，若量子 Fourier 变换使用图 5.1 实现，且我们假设 Hadamard 门与 swap 门可以精确实现，那么 $E(U, V)$ 的误差可以拆分为各 $R_k$ 门路误差的和。由于对于 $n$ 量子比特，Fourier 变换线路需要 $n(n-1)/2$ 个 $R_k$ 门 (书中所说的 $n(n+1)/2$ 个门路包含了 $n$ 个 Hadamard 门，在误差分析中要剔除这些门路的误差贡献)，因此\n",
    "\n",
    "$$\n",
    "E(U, V) = \\frac{n(n-1)}{2} \\Delta = \\Theta (n^2 / p(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
}