{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "0c16de92",
   "metadata": {},
   "source": [
    "# 4.5 通用量子门"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "814a55fb",
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "from functools import reduce\n",
    "np.set_printoptions(4, suppress=True, linewidth=150)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "52f32458",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Vector in computational basis\n",
    "vec0 = np.array([1, 0])\n",
    "vec1 = np.array([0, 1])\n",
    "# Matrices in computational basis\n",
    "I = np.eye(2)\n",
    "X = np.array([[0, 1], [1, 0]])\n",
    "Z = np.array([[1, 0], [0, -1]])\n",
    "H = 1/np.sqrt(2) * np.array([[1, 1], [1, -1]])\n",
    "T = np.array([[1, 0], [0, np.exp(1j*np.pi/4)]])\n",
    "S = T @ T\n",
    "P0 = np.outer(vec0, vec0)\n",
    "P1 = np.outer(vec1, vec1)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c7b22cdb",
   "metadata": {},
   "source": [
    "## 练习 4.36"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a302f692",
   "metadata": {},
   "source": [
    ":::{admonition} 练习 4.36\n",
    "\n",
    "构造一个把双比特数 $x$ 和 $y$ 进行模 4 加的量子线路，即线路可以完成 $|x, y\\rangle \\rightarrow |x, (x+y) \\text{ mod } 4\\rangle$ 的变换。\n",
    "\n",
    ":::"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f5433f84",
   "metadata": {},
   "source": [
    "我们定义下述四个单量子比特数 $a, b, c, d, e, f \\in \\{0, 1\\}$，并定义 $|x\\rangle = |ab\\rangle, |y\\rangle = |cd\\rangle$。题目所要求的线路是从 $|abcd\\rangle \\rightarrow |abef\\rangle$ 的变换。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a7371487",
   "metadata": {},
   "source": [
    "题目要求的 $ef$ 是二进制下的 $(ab+cd) \\text{ mod } 4$ (这里 $ab$ 表示的不是乘法，而是二进制数 $a \\times 2 + b$)。根据进位原则，\n",
    "\n",
    "$$\n",
    "\\begin{align*}\n",
    "f &= b \\oplus d = (b + d) \\text{ mod } 2 \\\\\n",
    "e &= a \\oplus c \\oplus (b \\times d) = (a + c + b \\times d) \\text{ mod } 2\n",
    "\\end{align*}\n",
    "$$\n",
    "\n",
    "这两步操作分别在下述线路图中用蓝色与橙色框表示。\n",
    "\n",
    "![ex-4.36.1](assets/ex-4.36.1.svg)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a14b390e",
   "metadata": {},
   "source": [
    "## 练习 4.37"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7c49c59d",
   "metadata": {},
   "source": [
    ":::{admonition} 练习 4.37\n",
    "\n",
    "求变换\n",
    "\n",
    "$$\n",
    "U = \\frac{1}{2} \\begin{bmatrix}\n",
    "1 & 1 & 1 & 1 \\\\\n",
    "1 & i & -1 & -i \\\\\n",
    "1 & -1 & 1 & -1 \\\\\n",
    "1 & -i & -1 & i\n",
    "\\end{bmatrix}\n",
    "$$\n",
    "\n",
    "的一个两级酉矩阵分解。这是量子 Fourier 变换的一个特例，下一章将作仔细研究。\n",
    "\n",
    ":::"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0f1a201c",
   "metadata": {},
   "source": [
    "**作为量子 Fourier 变换的分解**"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4f202ec1",
   "metadata": {},
   "source": [
    "我们采用图 5.1 的结论，可以立即得到待求的 $U$ 就是下述线路：\n",
    "\n",
    "![ex-4.37.1](assets/ex-4.37.1.svg)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "23fe1249",
   "metadata": {},
   "source": [
    "用数学的语言表述的话，是\n",
    "\n",
    "$$\n",
    "U = \\mathrm{SWAP} (I \\otimes H) (I \\otimes P_0 + S \\otimes P_1) (H \\otimes I)\n",
    "$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "e060d891",
   "metadata": {},
   "outputs": [],
   "source": [
    "U = 0.5 * np.array([\n",
    "    [1,   1,  1,   1],\n",
    "    [1,  1j, -1, -1j],\n",
    "    [1,  -1,  1,  -1],\n",
    "    [1, -1j, -1,  1j]\n",
    "])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "3962db6c",
   "metadata": {},
   "outputs": [],
   "source": [
    "swap = np.array([[1, 0, 0, 0], [0, 0, 1, 0], [0, 1, 0, 0], [0, 0, 0, 1]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "60b9e61e",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "np.allclose(swap @ np.kron(I, H) @ (np.kron(I, P0) + np.kron(S, P1)) @ np.kron(H, I), U)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "66943a43",
   "metadata": {},
   "source": [
    "上式中，受控 $S$ 算符和 SWAP 算符都是二级酉矩阵，但作用于单量子比特的 $H$ 算符则还需要进一步展开。因此，我们写出下述线路：\n",
    "\n",
    "![ex-4.37.2](assets/ex-4.37.2.svg)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9db65211",
   "metadata": {},
   "source": [
    "$U = U_1^\\dagger U_2^\\dagger U_3^\\dagger U_4^\\dagger U_5^\\dagger U_6^\\dagger$ 的每个矩阵可以写为\n",
    "\n",
    "$$\n",
    "\\begin{alignat*}{20}\n",
    "U_1^\\dagger &= \\begin{bmatrix}\n",
    "1 & 0 & 0 & 0 \\\\\n",
    "0 & 0 & 1 & 0 \\\\\n",
    "0 & 1 & 0 & 0 \\\\\n",
    "0 & 0 & 0 & 1\n",
    "\\end{bmatrix}, \\quad\n",
    "U_2^\\dagger &&= \\begin{bmatrix}\n",
    "1/\\sqrt{2} & 1/\\sqrt{2} & 0 & 0 \\\\\n",
    "1/\\sqrt{2} & -1/\\sqrt{2} & 0 & 0 \\\\\n",
    "0 & 0 & 1 & 0 \\\\\n",
    "0 & 0 & 0 & 1\n",
    "\\end{bmatrix}, \\quad\n",
    "U_3^\\dagger &&= \\begin{bmatrix}\n",
    "1 & 0 & 0 & 0 \\\\\n",
    "0 & 1 & 0 & 0 \\\\\n",
    "0 & 0 & 1/\\sqrt{2} & 1/\\sqrt{2} \\\\\n",
    "0 & 0 & 1/\\sqrt{2} & -1/\\sqrt{2}\n",
    "\\end{bmatrix} \\\\\n",
    "U_4^\\dagger &= \\begin{bmatrix}\n",
    "1 & 0 & 0 & 0 \\\\\n",
    "0 & 1 & 0 & 0 \\\\\n",
    "0 & 0 & 1 & 0 \\\\\n",
    "0 & 0 & 0 & i\n",
    "\\end{bmatrix}, \\quad\n",
    "U_5^\\dagger &&= \\begin{bmatrix}\n",
    "1/\\sqrt{2} & 0 & 1/\\sqrt{2} & 0 \\\\\n",
    "0 & 1 & 0 & 0 \\\\\n",
    "1/\\sqrt{2} & 0 & -1/\\sqrt{2} & 0 \\\\\n",
    "0 & 0 & 0 & 1\n",
    "\\end{bmatrix}, \\quad\n",
    "U_6^\\dagger &&= \\begin{bmatrix}\n",
    "1 & 0 & 0 & 0 \\\\\n",
    "0 & 1/\\sqrt{2} & 0 & 1/\\sqrt{2} \\\\\n",
    "0 & 0 & 1 & 0 \\\\\n",
    "0 & 1/\\sqrt{2} & 0 & -1/\\sqrt{2}\n",
    "\\end{bmatrix}\n",
    "\\end{alignat*}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "94a799d0",
   "metadata": {},
   "source": [
    "验证上述计算过程的代码如下："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "fc55ab0c",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "U_list_fourier = [\n",
    "    swap,\n",
    "    np.kron(P1, I) + np.kron(P0, H),\n",
    "    np.kron(P0, I) + np.kron(P1, H),\n",
    "    np.kron(I, P0) + np.kron(S, P1),\n",
    "    np.kron(I, P1) + np.kron(H, P0),\n",
    "    np.kron(I, P0) + np.kron(H, P1),\n",
    "]\n",
    "np.allclose(reduce(np.dot, U_list_fourier), U)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7e33fc9f",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "df2fbed7",
   "metadata": {},
   "source": [
    "**标准做法**"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "07c985f9",
   "metadata": {},
   "source": [
    "上面是从第 5 章已经知道答案的情况下，对答案进行验证的过程。但这一节所给的标准做法是不断地消去非对角元。这个过程是非常清晰的，可以通过简单的程序直接给出。需要指出，最后一个矩阵的处理方式会稍微有些特别。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "4cf2d58c",
   "metadata": {},
   "outputs": [],
   "source": [
    "def generate_two_level_unitary(M, axis1, axis2):\n",
    "    \"\"\"\n",
    "    Input unitary matrix M, and give the matrix element position\n",
    "    you want to set U.dot(M)[axis1, axis2] == 0,\n",
    "    Output the desired two-level unitary matrix U.\n",
    "    \"\"\"\n",
    "    U = np.eye(M.shape[0], dtype=M.dtype)\n",
    "    a = M[axis2, axis2]\n",
    "    b = M[axis1, axis2]\n",
    "    r = np.linalg.norm([a, b])\n",
    "    U[axis1, axis1] = - a / r\n",
    "    U[axis1, axis2] = b / r\n",
    "    U[axis2, axis1] = np.conj(b) / r\n",
    "    U[axis2, axis2] = np.conj(a) / r\n",
    "    return U"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "17eefe06",
   "metadata": {},
   "outputs": [],
   "source": [
    "def generate_two_level_decompose(M):\n",
    "    \"\"\"\n",
    "    Input unitary matrix M\n",
    "    Output two-level unitary matrix decomposition list U_list\n",
    "    \"\"\"\n",
    "    dim = M.shape[0]\n",
    "    M_proc = M\n",
    "    U_list = []\n",
    "    # first (d-2) columns: regular process\n",
    "    for j in range(dim-2):\n",
    "        for i in range(j+1, dim):\n",
    "            U = generate_two_level_unitary(M_proc, i, j)\n",
    "            U_list.append(U.conj().T)\n",
    "            M_proc = U @ M_proc\n",
    "    # last transformation: special treatment\n",
    "    U_last = np.eye(dim, dtype=M_proc.dtype)\n",
    "    U_last[-2:, -2:] = M_proc[-2:, -2:]\n",
    "    U_list.append(U_last)\n",
    "    return U_list"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "274fb49d",
   "metadata": {},
   "source": [
    "下面的程序可以给出题目所要求的二级酉矩阵。该结果比较复杂，但也是正确的。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "1fa9aad9",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "U_list = generate_two_level_decompose(U)\n",
    "np.allclose(reduce(np.dot, U_list), U)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "726fd221",
   "metadata": {},
   "source": [
    "$U = U_1^\\dagger U_2^\\dagger U_3^\\dagger U_4^\\dagger U_5^\\dagger U_6^\\dagger$ 的每个矩阵可以写为\n",
    "\n",
    "$$\n",
    "\\begin{alignat*}{20}\n",
    "U_1^\\dagger &= \\begin{bmatrix}\n",
    "\\sqrt{1/2} & \\sqrt{1/2} & 0 & 0 \\\\\n",
    "\\sqrt{1/2} & -\\sqrt{1/2} & 0 & 0 \\\\\n",
    "0 & 0 & 1 & 0 \\\\\n",
    "0 & 0 & 0 & 1\n",
    "\\end{bmatrix}, \\quad&\n",
    "U_2^\\dagger &= \\begin{bmatrix}\n",
    "\\sqrt{2/3} & 0 & \\sqrt{1/3} & 0 \\\\\n",
    "0 & 1 & 0 & 0 \\\\\n",
    "\\sqrt{1/3} & 0 & -\\sqrt{2/3} & 0 \\\\\n",
    "0 & 0 & 0 & 1\n",
    "\\end{bmatrix}, \\quad&\n",
    "U_3^\\dagger &= \\begin{bmatrix}\n",
    "\\sqrt{3/4} & 0 & 0 & 1/2 \\\\\n",
    "0 & 1 & 0 & 0 \\\\\n",
    "0 & 0 & 1 & 0 \\\\\n",
    "1/2 & 0 & 0 & -\\sqrt{3/4}\n",
    "\\end{bmatrix} \\\\\n",
    "U_4^\\dagger &= \\begin{bmatrix}\n",
    "1 & 0 & 0 & 0 \\\\\n",
    "0 & \\sqrt{3}(1-i)/4 & (3-i)/4 & 0 \\\\\n",
    "0 & (3+i)/4 & -\\sqrt{3}(1+i)/4 & 0 \\\\\n",
    "0 & 0 & 0 & 1\n",
    "\\end{bmatrix}, \\quad&\n",
    "U_5^\\dagger &= \\begin{bmatrix}\n",
    "1 & 0 & 0 & 0 \\\\\n",
    "0 & \\sqrt{2/3} & 0 & -i\\sqrt{1/3} \\\\\n",
    "0 & 0 & 1 & 0 \\\\\n",
    "0 & i\\sqrt{1/3} & 0 & -\\sqrt{2/3}\n",
    "\\end{bmatrix}, \\quad&\n",
    "U_6^\\dagger &= \\begin{bmatrix}\n",
    "1 & 0 & 0 & 0 \\\\\n",
    "0 & 1 & 0 & 0 \\\\\n",
    "0 & 0 & \\sqrt{1/2} & i \\sqrt{1/2} \\\\\n",
    "0 & 0 & -\\sqrt{1/2} & i \\sqrt{1/2}\n",
    "\\end{bmatrix}, \\quad\n",
    "\\end{alignat*}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8ae2ef2c",
   "metadata": {},
   "source": [
    "## 练习 4.38"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "61b178ba",
   "metadata": {},
   "source": [
    ":::{admonition} 练习 4.38\n",
    "\n",
    "证明存在 $d \\times d$ 酉矩阵 $U$，它不能分解为少于 $d-1$ 个两级酉矩阵的乘积。\n",
    "\n",
    ":::"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "dfa11b9a",
   "metadata": {},
   "source": [
    "**简单的 $d=3$ 的情况**"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6c993de7",
   "metadata": {},
   "source": [
    "首先我们考察容易分析的情况。对于 $d = 3$，如果一个矩阵可以由 2 个两级矩阵所表示，那么不妨令\n",
    "\n",
    "$$\n",
    "A = \\begin{bmatrix} 1 & 0 & 0 \\\\ 0 & a & b \\\\ 0 & c & d \\end{bmatrix}, \\quad\n",
    "B = \\begin{bmatrix} e & 0 & f \\\\ 0 & 1 & 0 \\\\ g & 0 & h \\end{bmatrix}\n",
    "$$\n",
    "\n",
    "那么\n",
    "\n",
    "$$\n",
    "AB = \\begin{bmatrix}\n",
    "e & 0 & f \\\\\n",
    "bg & a & bh \\\\\n",
    "dg & c & dh\n",
    "\\end{bmatrix}\n",
    "$$\n",
    "\n",
    "我们能发现，其中一个元素的值为零。事实上，不论两级矩阵的“两级”在 $3 \\times 3$ 的哪一个子矩阵中，2 个这种两级矩阵相乘总会有一个元素是零。这与矩阵是否是酉的其实没有关系。\n",
    "\n",
    "依据这个认识，我们对任何的 $d \\geqslant 3$ 作证明。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "438b94a3",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9ed49e97",
   "metadata": {},
   "source": [
    "**待证问题**"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a5c5b95d",
   "metadata": {},
   "source": [
    "对于 $d \\times d$ 的矩阵 $U$，不存在分解 $U = M^1 M^2 \\cdots M^{d-1}$，使得 $U$ 的每个元素非零。其中，$M^1, M^2, \\cdots, M^{d-1}$ 是两级矩阵。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c13d8d3c",
   "metadata": {},
   "source": [
    "**定义补充**"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "36696733",
   "metadata": {},
   "source": [
    "我们作一些符号的定义。这段证明全部采用 1-索引，即起始角标为 1。我们不考虑矩阵是否是酉的。\n",
    "\n",
    "对于 $\\mathbb{C}^{d \\times d}$ 空间，我们定义一系列两级矩阵 $M^1, M^2, \\cdots, M^n$。需要注意，这里的上标并非是幂次，而是标识矩阵的上角标；这是由于我们需要使用到下角标标识矩阵的具体元素。这个证明不需要使用矩阵幂次。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "92a2bb10",
   "metadata": {},
   "source": [
    "我们同时定义，各两级矩阵的子矩阵角标集合是 $\\sigma_1, \\sigma_2, \\cdots, \\sigma_n$。。举例而言，若 $\\sigma_1 = \\{1, 3\\}$，那么两级矩阵 $M^1$ 必然可以写为下述形式：\n",
    "\n",
    "$$\n",
    "M^1 = \\begin{bmatrix}\n",
    "a & 0 & a & 0 & \\cdots & 0 \\\\\n",
    "0 & 1 & 0 & 0 & \\cdots & 0 \\\\\n",
    "c & 0 & d & 0 & \\cdots & 0 \\\\\n",
    "0 & 0 & 0 & 1 & \\cdots & 0 \\\\\n",
    "\\vdots & \\vdots & \\vdots & \\vdots & \\ddots & \\\\\n",
    "0 & 0 & 0 & 0 && 1\n",
    "\\end{bmatrix}\n",
    "\\quad (\\text{if } \\sigma_1 = \\{1, 3\\})\n",
    "$$\n",
    "\n",
    "即元素 $M^1_{11}, M^1_{13}, M^1_{31}, M^1_{33}$ 可以是任意值；而其它情况下，只有对角线元素为 1，否则为零。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a6c42afb",
   "metadata": {},
   "source": [
    "**证明过程**"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f9df30f6",
   "metadata": {},
   "source": [
    "反证法。现在我们假设存在 $M^1, M^2, \\cdots, M^{d-1}$，使得 $U = M^1 M^2 \\cdots M^{d-1}$，且 $U$ 的每一个元素非零。因此，指标集合 $\\sigma_1, \\sigma_2, \\cdots, \\sigma_{d-1}$ 也是确定的。那么对于任意角标 $k, l \\in \\{1, 2, \\cdots, d\\}$，依据矩阵乘法定义，有\n",
    "\n",
    "$$\n",
    "U_{kl} = \\sum_{i_1 i_2 \\cdots i_{d-2}} M^1_{k i_1} M^2_{i_1 i_2} M^3_{i_2 i_3} \\cdots M^{d-1}_{i_{d-2} l}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "02c17c87",
   "metadata": {},
   "source": [
    "为了让 $U_{kl}$ 不为零，我们要保证至少存在一组 $\\{i_1, i_2, \\cdots, i_{d-2}\\}$，使得\n",
    "\n",
    "$$\n",
    "M^1_{k i_1} M^2_{i_1 i_2} M^3_{i_2 i_3} \\cdots M^{d-1}_{i_{d-2} l} \\neq 0\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a3ccce7e",
   "metadata": {},
   "source": [
    "我们令 $S_n$ 是满足上式的 $i_n$ 可能取值的集合。令记号 $\\mathscr{S}_l$ 是 $l$ 可能取值的集合。\n",
    "\n",
    "我们要稍微分析一下这个作用。先考虑 $M^1_{k i_1} M^2_{i_1 i_2}$ 如何才能是非零的。由于 $\\sigma_1, \\sigma_2, \\cdots, \\sigma_{d-1}$ 是给定的，因此我们总可以找到一个 $k$，它满足 $k \\not \\in \\sigma_1$。那么 $i_1$ 必须为 $k$ 即 $M^1_{k i_1}$ 必须是 $M^1_{kk} = 1$，否则 $M^1_{k i_1} = 0$。**我们之后一直需要使用这种 $k$**。\n",
    "\n",
    "- 若 $i_1 \\not \\in \\sigma_2$，那么 $i_2$ 必须为 $i_1$，理由同上，即否则 $M_{i_1 i_2} = 0$；但恰好，$i_1 = k$，因此要求了 $i_2 = k$；在这种情况下，$S_2 = \\{k\\}$；\n",
    "- 若 $i_1 \\in \\sigma_2$，那么 $i_2$ 可以取 $i_1$，也可以取 $\\sigma_2$ 中的另一个元素；在这种情况下，$S_2 = \\{k, i_1, i_2\\} = \\{k\\} \\cup \\sigma_2$。但我们指出，$|S_2| = 2$，因为 $k = i_1 \\in \\sigma_2$，因此 $S_2 = \\sigma_2$。\n",
    "\n",
    "这两种情况都是 $|S_2| \\leqslant 2$。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8e3c7d11",
   "metadata": {},
   "source": [
    "随后，我们考察 $M^1_{k i_1} M^2_{i_1 i_2} M^3_{i_2 i_3}$。\n",
    "\n",
    "- 若 $i_2 \\not \\in \\sigma_3$，那么 $i_3$ 必须取为 $i_2$；在这种情况下，$S_3 = S_2$；元素数 $|S_3| = |S_2|$；\n",
    "- 若 $i_2 \\in \\sigma_3$，那么 $i_3$ 可以取为 $i_2$，也可以取为 $\\sigma_3$ 的任何元素。因此 $S_3 = S_2 \\cup \\sigma_3$；但由于 $\\{i_2\\} \\subseteq \\sigma_3 \\cap S_2$，因此\n",
    "\n",
    "    $$\n",
    "    |S_3| = |S_2| + |\\sigma_3| - |S_2 \\cap \\sigma_3| \\leqslant |S_2| + 2 - 1 = |S_2| + 1\n",
    "    $$\n",
    "\n",
    "这两种情况都是 $|S_3| \\leqslant |S_2| + 1 \\leqslant 3$。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "85635265",
   "metadata": {},
   "source": [
    "以此类推，可知\n",
    "\n",
    "$$\n",
    "|S_n| \\leqslant |S_n| + 1 \\leqslant n\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ffcfa8c5",
   "metadata": {},
   "source": [
    "到 $M^1_{k i_1} M^2_{i_1 i_2} M^3_{i_2 i_3} \\cdots M^{d-1}_{i_{d-2} l}$ 时，我们知道\n",
    "\n",
    "$$\n",
    "|\\mathscr{S}_l| \\leqslant |S_{d_2}| + 1 \\leqslant d-1\n",
    "$$\n",
    "\n",
    "这就意味着 $l$ 只可能取 $d - 1$ 个值；当取到 $\\{1, 2, \\cdots, d\\} \\setminus \\mathscr{S}_l \\neq \\emptyset$ 中的元素时，$U_{kl}$ 必然为零。因此，对于任意的 $k \\not \\in \\sigma_1$，总存在 $l$，使得 $U_{kl} = 0$。证毕。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "508ca903",
   "metadata": {},
   "source": [
    "## 练习 4.39"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "916e219a",
   "metadata": {},
   "source": [
    ":::{admonition} 练习 4.39\n",
    "\n",
    "求一个用单量子比特运算和受控非门的量子线路，实现变换\n",
    "\n",
    "$$\n",
    "\\begin{bmatrix}\n",
    "1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\\\\n",
    "0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\\\\n",
    "0 & 0 & a & 0 & 0 & 0 & 0 & b \\\\\n",
    "0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\\\\n",
    "0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\\\\n",
    "0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\\\\n",
    "0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\\\\n",
    "0 & 0 & c & 0 & 0 & 0 & 0 & d\n",
    "\\end{bmatrix}\n",
    "$$\n",
    "\n",
    "其中 $\\tilde U = \\begin{bmatrix} a & c \\\\ b & d \\end{bmatrix}$ 是任意的 $2 \\times 2$ 酉矩阵。\n",
    "\n",
    ":::"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "16d94a0b",
   "metadata": {},
   "source": [
    "上述变换是从 $|010\\rangle$ 到 $|111\\rangle$ 的非平凡变换。仿照式 (4.59) 与图 4.16，我们写出连接 $|010\\rangle$ 与 $|111\\rangle$ 的 Gray 码：\n",
    "\n",
    "$$\n",
    "\\begin{matrix}\n",
    "A & B & C \\\\\n",
    "0 & 1 & 0 \\\\\n",
    "0 & 1 & 1 \\\\\n",
    "1 & 1 & 1\n",
    "\\end{matrix}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e1c14350",
   "metadata": {},
   "source": [
    "那么所构成的线路是\n",
    "\n",
    "![ex-4.39.1](assets/ex-4.39.1.svg)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "de8dd9bd",
   "metadata": {},
   "source": [
    "## 练习 4.40"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1fe127f8",
   "metadata": {},
   "source": [
    ":::{admonition} 练习 4.40\n",
    "\n",
    "对任意的 $\\alpha$ 和 $\\beta$，证明\n",
    "\n",
    "$$\n",
    "E \\big( R_{\\hat n} (\\alpha) - R_{\\hat n} (\\alpha + \\beta) \\big) = \\left\\Vert 1 - \\exp \\left( \\frac{i \\beta}{2} \\right) \\right\\Vert\n",
    "$$\n",
    "\n",
    ":::"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7836eaa0",
   "metadata": {},
   "source": [
    "依式 (4.8)，对等式左边的算符部分作如下展开：\n",
    "\n",
    "$$\n",
    "R_{\\hat n} (\\alpha) - R_{\\hat n} (\\alpha + \\beta)\n",
    "= \\left( \\cos \\frac{\\alpha}{2} - \\cos \\frac{\\alpha + \\beta}{2} \\right) I - i \\left( \\sin \\frac{\\alpha}{2} - \\sin \\frac{\\alpha + \\beta}{2} \\right) \\hat n \\cdot \\vec \\sigma\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a297b17f",
   "metadata": {},
   "source": [
    "使用和差化积，可以得到\n",
    "\n",
    "$$\n",
    "\\begin{align*}\n",
    "R_{\\hat n} (\\alpha) - R_{\\hat n} (\\alpha + \\beta) &= 2 \\sin \\frac{\\beta}{4} \\sin \\left( \\frac{\\alpha}{2} + \\frac{\\beta}{4} \\right) I + 2 i \\sin \\frac{\\beta}{4} \\cos \\left( \\frac{\\alpha}{2} + \\frac{\\beta}{4} \\right) \\hat n \\cdot \\vec \\sigma \\\\\n",
    "&= 2 \\sin \\frac{\\beta}{4} R_{\\hat n} \\left( \\frac{\\alpha}{2} + \\frac{\\beta}{4} + \\pi \\right)\n",
    "\\end{align*}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5534f201",
   "metadata": {},
   "source": [
    "因此，\n",
    "\n",
    "$$\n",
    "\\begin{align*}\n",
    "E \\big( R_{\\hat n} (\\alpha) - R_{\\hat n} (\\alpha + \\beta) \\big)\n",
    "&= \\max_{|\\psi\\rangle} \\big\\Vert R_{\\hat n} (\\alpha) - R_{\\hat n} (\\alpha + \\beta) |\\psi\\rangle \\big\\Vert \\\\\n",
    "&= \\max_{|\\psi\\rangle} \\left\\Vert 2 \\sin \\frac{\\beta}{4} R_{\\hat n} \\left( \\frac{\\alpha}{2} + \\frac{\\beta}{4} + \\pi \\right) |\\psi\\rangle \\right\\Vert \\\\\n",
    "&= \\left\\Vert 2 \\sin \\frac{\\beta}{4} \\right\\Vert \\cdot \\max_{|\\psi\\rangle} \\left\\Vert R_{\\hat n} \\left( \\frac{\\alpha}{2} + \\frac{\\beta}{4} + \\pi \\right) |\\psi\\rangle \\right\\Vert \\\\\n",
    "&= \\left\\Vert 2 \\sin \\frac{\\beta}{4} \\right\\Vert\n",
    "\\end{align*}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "02447529",
   "metadata": {},
   "source": [
    "随后我们考察到，将三角函数转换为指数后，\n",
    "\n",
    "$$\n",
    "\\sin \\frac{\\beta}{4} = \\frac{i}{2} \\left( \\exp\\left( - \\frac{i \\beta}{4} \\right) - \\exp\\left( \\frac{i \\beta}{4} \\right) \\right) = \\frac{i}{2} \\exp\\left( - \\frac{i \\beta}{4} \\right) \\left( 1 - \\exp\\left( \\frac{i \\beta}{2} \\right) \\right)\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "77bc4036",
   "metadata": {},
   "source": [
    "因此，\n",
    "\n",
    "$$\n",
    "\\begin{align*}\n",
    "E \\big( R_{\\hat n} (\\alpha) - R_{\\hat n} (\\alpha + \\beta) \\big) = \\left\\Vert i \\exp\\left( - \\frac{i \\beta}{4} \\right) \\left( 1 - \\exp\\left( \\frac{i \\beta}{2} \\right) \\right) \\right\\Vert = \\left\\Vert 1 - \\exp\\left( \\frac{i \\beta}{2} \\right) \\right\\Vert\n",
    "\\end{align*}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "16c13321",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1c0d11ba",
   "metadata": {},
   "source": [
    "题目还要求证明式 (4.76)。我们不在这里回顾上下文，只给出证明了。首先，上文曾经表明过，对于很小的 $\\forall \\delta > 0$，\n",
    "\n",
    "$$\n",
    "\\exists j, k \\in \\mathbb{N}; N > \\frac{2\\pi}{\\delta}; \\; \\text{s.t.} \\; j, k \\leqslant N; \\; \\theta_{k-j} = (k-j) \\theta \\; \\mathrm{mod} \\; 2 \\pi < \\delta\n",
    "$$\n",
    "\n",
    "这里与原书稍有不同。我们这里不妨令 $\\theta_{k-j} > 0$。那么\n",
    "\n",
    "$$\n",
    "\\exists l; M > \\frac{2 \\pi}{\\theta_{k-j}}, \\; \\mathrm{s.t.} \\; \\alpha \\in \\big[ (l-1) \\theta_{k-j} \\; \\mathrm{mod} \\; 2\\pi, l \\theta_{k-j} \\; \\mathrm{mod} \\; 2\\pi \\big)\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "be9f7f5e",
   "metadata": {},
   "source": [
    "我们令 $n = l (k - j)$。那么，$R_{\\hat n} (\\theta)^n = R_{\\hat n} (n \\theta) = R_{\\hat n} \\big( l (k-j) \\theta \\; \\mathrm{mod} \\; 2 \\pi \\big) = R_{\\hat n} \\big( l \\theta_{k-j} \\; \\mathrm{mod} \\; 2 \\pi \\big)$ 与 $R_{\\hat n} (\\alpha)$ 中，旋转角度的差具有关系 (注意 $\\hat n$ 作为旋转轴与 $n$ 作为幂次是两个完全无关的记号)\n",
    "\n",
    "$$\n",
    "\\Vert \\beta \\Vert = \\big\\Vert l (k-j) \\theta \\; \\mathrm{mod} \\; 2 \\pi - \\alpha \\big\\Vert \\leqslant \\theta_{k-j}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "20143255",
   "metadata": {},
   "source": [
    "因此，(注意到 $\\sin x < x$ 在 $x > 0$ 时恒成立)\n",
    "\n",
    "$$\n",
    "E \\big( R_{\\hat n} (\\alpha) - R_{\\hat n} (\\theta)^n \\big) = \\left\\Vert 2 \\sin \\frac{\\beta}{4} \\right\\Vert < \\frac{\\Vert\\beta\\Vert}{2} = \\frac{\\theta_{k-j}}{2}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0d45dd2d",
   "metadata": {},
   "source": [
    "题目要求对 $\\forall \\varepsilon > 0$ 成立 $E \\big( R_{\\hat n} (\\alpha) - R_{\\hat n} (\\theta)^n \\big) < \\varepsilon / 3$，那么我们令 $\\delta = \\varepsilon / 2$。依据上面和原文的推导，\n",
    "\n",
    "$$\n",
    "E \\big( R_{\\hat n} (\\alpha) - R_{\\hat n} (\\theta)^n \\big) < \\frac{\\theta_{k-j}}{2} < \\frac{\\delta}{2} = \\frac{\\varepsilon}{4} < \\frac{\\varepsilon}{3}\n",
    "$$\n",
    "\n",
    "证毕。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a10d2498",
   "metadata": {},
   "source": [
    "## 练习 4.41"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "baa9bbf0",
   "metadata": {},
   "source": [
    ":::{admonition} 练习 4.41\n",
    "\n",
    "本练习和下两个练习通过构造证明 Hadamard 门、相位门、受控非门和 Toffoli 门是通用的。证明下图所示的线路在两个测量输出都是 $|0\\rangle$ 时，把 $R_z (\\theta)$ 运算应用到第三 (目标) 量子比特，其中 $\\cos \\theta = 3/5$；否则把 $Z$ 应用到目标量子比特。证明两个测量结果都是 $|0\\rangle$ 的概率是 5/8，并说明如何反复使用该线路和 $Z = S^2$ 门，来让应用 $R_z (\\theta)$ 门的概率接近 1。\n",
    "\n",
    "![ex-4.41.1](assets/ex-4.41.1.svg)\n",
    "\n",
    ":::"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4db2b54c",
   "metadata": {},
   "source": [
    "我们不妨将测量之前的线路情况描绘一下：\n",
    "\n",
    "![ex-4.41.2](assets/ex-4.41.2.svg)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a200361d",
   "metadata": {},
   "source": [
    "$$\n",
    "\\begin{align*}\n",
    "|\\psi_1\\rangle &= \\frac{1}{2} \\big( |00\\rangle \\otimes |\\psi\\rangle + |01\\rangle \\otimes |\\psi\\rangle + |10\\rangle \\otimes |\\psi\\rangle + |11\\rangle \\otimes |\\psi\\rangle \\big) \\\\\n",
    "|\\psi_4\\rangle &= \\frac{1}{2} \\big( |00\\rangle \\otimes S |\\psi\\rangle + |01\\rangle \\otimes S |\\psi\\rangle + |10\\rangle \\otimes S |\\psi\\rangle + |11\\rangle \\otimes XSX |\\psi\\rangle \\big) \\\\\n",
    "|\\psi_5\\rangle &= \\frac{1}{4} \\big( |00\\rangle \\otimes (3S + XSX) |\\psi\\rangle + |01\\rangle \\otimes (S - XSX) |\\psi\\rangle \\\\\n",
    "&\\quad + |10\\rangle \\otimes (S - XSX) |\\psi\\rangle - |11\\rangle \\otimes (S - XSX) |\\psi\\rangle \\big)\n",
    "\\end{align*}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cdd3acba",
   "metadata": {},
   "source": [
    "我们可以通过矩阵计算，给出 $3S + XSX$ 与 $S - XSX$ 的表达式：\n",
    "\n",
    "$$\n",
    "\\begin{align*}\n",
    "3S + XSX &= \\begin{bmatrix} 3 + i & 0 \\\\ 0 & 1 + 3i \\end{bmatrix} = \\sqrt{10} e^{i \\alpha} \\begin{bmatrix} e^{-i \\beta / 2} & 0 \\\\ 0 & e^{i \\beta / 2} \\end{bmatrix} = \\sqrt{10} e^{i \\alpha} R_z (\\beta) \\\\\n",
    "S - XSX &= \\begin{bmatrix} 1 - i & 0 \\\\ 0 & -1 + i \\end{bmatrix} = \\sqrt{2} e^{i \\pi/4} Z\n",
    "\\end{align*}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bfc1dec7",
   "metadata": {},
   "source": [
    "上式的 $\\alpha, \\beta$ 是可以求出的。其中，$\\alpha = \\pi / 4$，$\\cos(\\beta/2) = 2/\\sqrt{5}$ 即 $\\beta = 2 \\arccos(2/\\sqrt{5})$。但实际上，我们利用倍角公式，容易知道\n",
    "\n",
    "$$\n",
    "\\cos \\beta = 2 \\cos^2(\\beta/2) - 1 = 3/5\n",
    "$$\n",
    "\n",
    "意味着 $\\cos \\beta = 3/5$，即 $\\beta = \\arccos (3/5)$。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "098bfa9b",
   "metadata": {},
   "source": [
    "我们回到线路图上。在测量前，线路给出的三粒子态是\n",
    "\n",
    "$$\n",
    "|\\psi_5\\rangle = \\frac{\\sqrt{10}}{4} e^{i \\pi/4} |00\\rangle \\otimes R_z (\\beta) |\\psi\\rangle + \\frac{\\sqrt{2}}{4} e^{i \\pi/4} (|01\\rangle + |10\\rangle - |11\\rangle) \\otimes Z |\\psi\\rangle\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "612d3935",
   "metadata": {},
   "source": [
    "这可以表明，在对前两个量子比特测量后，若忽略全局相位的话，\n",
    "\n",
    "- 若测量结果是 $|00\\rangle$，则第三个量子比特相当于 $|\\psi\\rangle \\rightarrow R_z(\\beta) |\\psi\\rangle$；\n",
    "- 若测量结果是其它情况，则第三个量子比特相当于 $|\\psi\\rangle \\rightarrow Z |\\psi\\rangle$。\n",
    "\n",
    "测得 $|00\\rangle$ 的概率是 $(\\sqrt{10} / 4)^2 = 5/8$。这就对原题的第一部分做了证明。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2ccdfb1d",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4bf8dae1",
   "metadata": {},
   "source": [
    "原题的第二部分是利用既定的事实 $\\beta = \\arccos(3/5)$ 是 $2 \\pi$ 的无理倍数，表明 Hadamard 门 $H$、相位门 $S$ 和 Toffoli 门可以构造任意旋转角度 $\\theta$ 的 $R_z (\\theta)$。\n",
    "\n",
    "我们回顾到教材的正文，事实上，如果对于 $\\beta = \\arccos(3/5)$ 下的 $R_z (\\beta)$ 可以稳定地构造出来，那么任意旋转角度的 $R_z (\\theta)$ 就可以通过累次操作 $R_z (\\beta)$ 以任意精度进行逼近。\n",
    "\n",
    "那么问题化为 $R_z (\\beta)$ 要如何稳定地生成。尽管很低效，但若不考虑全局相位，它可以在上述量子线路实现后测量前两个量子比特，\n",
    "\n",
    "- 若前两个量子比特是 $|00\\rangle$，那么我们就导出第三个量子比特为 $R_z (\\beta) |\\psi\\rangle$；\n",
    "- 若两个量子比特是其它情况，那么我们对第三个量子比特 $Z |\\psi\\rangle$ 再作用一次 $Z$ 门，使得其回到 $|\\psi\\rangle$；随后重置前两个量子比特为 $|00\\rangle$，重新代入线路。\n",
    "\n",
    "它不能保证一次性地将第三个量子比特变成 $R_z (\\beta) |\\psi\\rangle$，但多次迭代后，这是可以做到的。\n",
    "\n",
    "这个过程原则上没有精度损失，但对线路复杂度的讨论会稍有影响。我们说，由于前两个量子比特不为 $|00\\rangle$ 的概率是 $3/8$，因此若要通过迭代使得第三个量子比特达到 $R_z (\\beta) |\\psi\\rangle$，平均的迭代次数会是\n",
    "\n",
    "$$\n",
    "\\sum_{k=0}^\\infty (k+1) \\left( \\frac{3}{8} \\right)^k = \\frac{64}{25} = 2.56\n",
    "$$\n",
    "\n",
    "因此，它对线路复杂度的影响其实只是多乘了 2.56 的系数，并不对大 $O$ 渐进性造成影响。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "12cc0b8e",
   "metadata": {},
   "source": [
    "## 练习 4.42 ($\\theta$ 的无理性)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "87c5cd93",
   "metadata": {},
   "source": [
    ":::{admonition} 练习 4.42\n",
    "\n",
    "设 $\\cos \\theta = 3/5$，我们用反证法证明 $\\theta$ 是 $2 \\pi$ 的无理倍数。\n",
    "\n",
    "1. 利用 $e^{i \\theta} = (3+4i)/5$ 的事实，证明若 $\\theta$ 是 $2 \\pi$ 的有理倍数，则必存在一个正整数 $m$，使得 $(3 + 4i)^m = 5^m$。\n",
    "2. 证明对所有 $m > 0$，$(3 + 4i)^m = 3 + 4i \\; (\\text{mod } 5)$ (等号在模 5 余数下成立)，并得出不存在 $m$，使得 $(3 + 4i)^m = 5^m$ 的结论。\n",
    "\n",
    ":::"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "342007db",
   "metadata": {},
   "source": [
    "依据题目假设，若 $\\theta$ 是 $2 \\pi$ 的有理倍数，那么我们可以令倍数为 $t/m$，其中 $m$ 是正整数，$t$ 是整数。因此，\n",
    "\n",
    "$$\n",
    "(e^{i \\theta})^m = (e^{i 2 \\pi t / m})^m = e^{i 2 \\pi t} = 1 = \\left( \\frac{3+4i}{5} \\right)^m\n",
    "$$\n",
    "\n",
    "整理上式立即得到 $(3 + 4i)^m = 5^m$。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3a05f0f6",
   "metadata": {},
   "source": [
    "证明后一个结论是简单的数归。这里的模 5 余数是分别针对实部与虚部而言的。首先 $m = 1$ 时显然成立。那么若对于 $m=k$ 的情形成立，那么当 $m = k+1$ 时，就有下述模 5 余数的等式：\n",
    "\n",
    "$$\n",
    "(3 + 4i)^{k+1} = (3+4i) (3+4i)^k = (3+4i) (3+4i) = -7 + 12i = 3 + 4i \\; (\\text{mod } 5)\n",
    "$$\n",
    "\n",
    "因此，对于任意的 $m > 0$，$(3 + 4i)^m = 3 + 4i \\; (\\text{mod } 5)$；但又由于我们刚才得到 $(3 + 4i)^m = 5^m = 0 \\; (\\text{mod } 5)$，因此有理数的假设不成立。得证。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5a7388ce",
   "metadata": {},
   "source": [
    "## 练习 4.43"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d0a51896",
   "metadata": {},
   "source": [
    ":::{admonition} 练习 4.43\n",
    "\n",
    "利用上两个练习的结果证明，Hadamard 门、相位门、受控非门和 Toffoli 门对量子计算是通用的。\n",
    "\n",
    ":::"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "93ba9f50",
   "metadata": {},
   "source": [
    "我们回顾到教材的正文中，对 Hadamard 门、受控非门和 $\\pi/8$ 门的通用性证明过程大致分为下述步骤 (书中定义的“相位门”其实是 $S = T^2$，因此有 $\\pi/8$ 门 $T$ 就够了)：\n",
    "\n",
    "1. 对于单量子比特算符，存在一根轴 $\\hat n = (\\cos \\pi/8, \\sin \\pi/8, \\cos)$ 和一个角度 $\\theta$，使得仅通过 Hadamard 门、$\\pi/8$ 门就可以表示其旋转 $R_{\\hat n} (\\theta)$；\n",
    "2. 表明 $\\theta$ 是 $2 \\pi$ 的无理倍数，因此总有办法以任意精度近似任意旋转角度 $R_{\\hat n} (\\alpha)$；\n",
    "3. 存在第二根与 $\\hat n$ 不平行的轴 $\\hat m$，使得 $R_{\\hat m} (\\theta)$ 也可以仅通过 Hadamard 门、$\\pi/8$ 门就可以表示；因此，任意单量子比特的酉矩阵可以表示；\n",
    "4. 对于多量子比特，通过 4.5.2 节的说明，任意的二级酉矩阵可以通过受控非门 CNOT 与上面的任意单量子比特结合表示；\n",
    "5. 进而，通过 4.5.1 节的说明，任意多量子比特的酉矩阵可以通过二级酉矩阵表示。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "534e1a9d",
   "metadata": {},
   "source": [
    "换到我们当前的问题。我们还没有证明这道题的线路图可以用于表示任意单量子比特；但对于多量子比特，现成的结论都已经有了。因此，我们需要对上面步骤中的第 1、2、3 点作说明。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cb7c3e85",
   "metadata": {},
   "source": [
    "对于第 1 点，我们在练习 4.41 已经有所证明，只是 $\\hat n$ 与 $\\theta$ 在当前的问题下变为了 $z$ 轴与 $\\beta = \\arccos (3/5)$。尽管该练习的量子线路不一定一次性地给出 $R_z (\\beta)$，但通过多次迭代该线路，总是可以生成这个算符的。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "53896df9",
   "metadata": {},
   "source": [
    "对于第 2 点，已经在练习 4.42 证明。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "986adc5f",
   "metadata": {},
   "source": [
    "对于第 3 点，我们回顾到书中的式 (4.4), (4.6), (4.18)，我们有\n",
    "\n",
    "$$\n",
    "H R_z (\\theta) H = R_x (\\theta)\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "43096572",
   "metadata": {},
   "source": [
    "因此，通过 Hadamard 门与题目所给出的线路图，我们不仅可以实现 $z$ 轴的任意旋转，也可以实现 $x$ 轴的任意旋转。结合起来，就可以实现任意的 Bloch 球面旋转了，即给出任意的单量子比特酉矩阵。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cf8734d3",
   "metadata": {},
   "source": [
    "第 4、5 点都是书中已有的结论了。因此，Hadamard 门、相位门、受控非门和 Toffoli 门对多量子比特门的通用性证明完毕。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "79d8b537",
   "metadata": {},
   "source": [
    "## 练习 4.44"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3566a59f",
   "metadata": {},
   "source": [
    ":::{admonition} 练习 4.44\n",
    "\n",
    "证明只要 $\\alpha$ 是无理的，如下定义的三量子比特门对量子计算就是通用的。\n",
    "\n",
    "![ex-4.44.1](assets/ex-4.44.1.svg)\n",
    "\n",
    ":::"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f7515e1c",
   "metadata": {},
   "source": [
    ":::{danger}\n",
    "\n",
    "本题我尚不打算进行完整证明。\n",
    "\n",
    "它实际上表现的是 Deutsch 门的通用性。一些重要的参考资料可以是\n",
    "\n",
    "> http://theory.caltech.edu/~preskill/ph229/notes/chap6.pdf\n",
    ">\n",
    "> https://quantumcomputing.stackexchange.com/a/10221/14843\n",
    "\n",
    ":::"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "857ae182",
   "metadata": {},
   "source": [
    "## 练习 4.45"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cba60a46",
   "metadata": {},
   "source": [
    ":::{admonition} 练习 4.45\n",
    "\n",
    "设 $U$ 是用 $H$、$S$、受控非门和 Toffoli 门构造的一个 $n$ 量子比特线路。证明 $U$ 具有形式 $2^{-k/2} M$，其中 $k$ 是某个整数，$M$ 是只有复整数元的 $2^n \\times 2^n$ 矩阵。对以 $\\pi/8$ 门代替 Toffoli 门的情形，重复本练习。\n",
    "\n",
    ":::"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "02c83b16",
   "metadata": {},
   "source": [
    "本体不作详细说明。我们只说，$H$ 可以写为 $2^{-1/2}$ 与复整数元的矩阵乘积；$T$ 尽管也可以这么做，但需要额外乘以全局相位；这个全局相位并不重要。剩下的 $S$、CNOT 与 Toffoli 门都完全是整数矩阵。因此，它们组合起来的形式自然就是 $2^{-k/2} M$ 的样子了。"
   ]
  }
 ],
 "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
}