docs/source/textbook/chap3.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 第三章 量子线路 (Quantum Circuit)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1 逻辑门与电路\n",
    "\n",
    "&emsp;&emsp;量子计算通过量子电路来实现。量子电路的本质是幺正变换和测量的组合。在物理上，我们无法直接实现过分复杂的幺正变换，所以期望通过一些容易实现的幺正变化来产生更复杂的幺正变换，这些较容易实现的变换则称为量子门。这个过程就类似于通过最基本的逻辑操作（与非门）来搭建大规模的数字电路一样。在本小节，我们将学习最基本的量子门，并简单了解一下如何通过她们来搭建复杂的量子电路。\n",
    "\n",
    "### 1.1 经典逻辑门与电路\n",
    "\n",
    "&emsp;&emsp;在了解量子电路之前我们可以先看一下经典计算是如何进行的。在本节中，我们介绍一种直观的经典计算模型，即电路模型。电路模型不只是一种数学模型，它也是真实计算机的实际物理实现方式。一个电路由导线和门组成，它们分别携带信息并执行简单的计算任务。例如，下图显示了一些简单的电路，他们只包含单个逻辑门进行逻辑上的非（NOT），与(AND)，或(OR) ，异或（XOR），NAND（与非）和或非（NOR）操作，称为量子门。输入和输出都只能是0（False）或者1(True)，称为经典比特（简称比特，和量子比特进行区分）。电路可以代表比特在空间中的运动，或者经过一段时间的状态变换。\n",
    "<div align = center>\n",
    "<img src=\"./img/classical_gates.png\" width=\"350\" title=\"bloch\" />\n",
    "<figcaption align = \"center\"> 经典逻辑门 </figcaption>\n",
    "</div>\n",
    "\n",
    "</bra>\n",
    "\n",
    "> 例: 给出一个稍微复杂点的电路，由两个逻辑门组成，称为半加器（half-adder）。我们可以验证以下输入输出关系：\n",
    "\n",
    "$$\\begin{aligned}\n",
    "&x = 0, y = 0 \\rightarrow c = 0, x\\oplus y = 0\\\\\n",
    "&x = 0, y = 1 \\rightarrow c = 0, x\\oplus y = 1\\\\\n",
    "\\end{aligned}$$\n",
    "\n",
    "而这正是两个比特相加的结果（包括进位比特）。这个电路称为半加器的原因是，其输入并没有包含进位比特。\n",
    "\n",
    "<div align = center>\n",
    "<img src=\"./img/half_adder.png\" width=\"250\" title=\"bloch\" />\n",
    "<figcaption align = \"center\"> 半加器电路，其中c是进位符 </figcaption>\n",
    "</div>\n",
    "\n",
    "</bra>\n",
    "&emsp;&emsp;我们可以发现，这里的“电路”是指代数字逻辑电路，与高中所学到的电阻、电源组成的电路有一定的区别。真实的计算机（包括电脑，手机等）通过使用高级语言的编程来实现算法功能。在计算机芯片层面，这些高级语言（Java, C, Python等）写的程序最终被转换（编译）成二进制数据，驱动CPU上一个个的逻辑门，并最终完成算法运算（本质是逻辑运算）。\n",
    "\n",
    "&emsp;&emsp;更一般地，一个电路可以有很多输入和输出比特。任意一般的逻辑函数可以定义为\n",
    "\n",
    "$$f:\\{0,1\\}^n \\rightarrow \\{0,1\\}^l$$\n",
    "\n",
    "例如，半加器就是一个$\\{0,1\\}^2$到$\\{0,1\\}^2$的逻辑函数。\n",
    "\n",
    "&emsp;&emsp;这里有一个重要的结论: \n",
    "\n",
    "&emsp;&emsp;<b>(经典线路)普适性定理：任意逻辑函数 $f$ ，都可以由仅仅包含NAND门的电路来实现。我们称NAND门对经典逻辑计算是普适（universal）的。</b>\n",
    "\n",
    "&emsp;&emsp; 由于篇幅限制，我们这里不给出相关的证明，有兴趣的读者可以参考任意一本数字逻辑电路的教科书。这个定理的意义在于，我们只需要实现一种类型的逻辑门，就能实现所有的逻辑电路，这将极大地简化理论分析和工程实现。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.2 量子逻辑门与电路\n",
    "\n",
    "&emsp;&emsp;与经典计算类似，在本节中，我们提供量子电路这种语言来描述量子计算过程的离散单元（量子门）的集合。对量子信息的处理本质上是一种幺正变换（配合额外的测量）。在我们考虑量子电路时，不失一般性，总是将测量放到整个计算过程的最后。这样，我们也可以仅将整个幺正变换看成是量子电路。这样，通用的量子计算过程可以如下图所示：\n",
    "\n",
    "<div align = center>\n",
    "<img src=\"./img/quantum_circuit.png\" width=\"400\" />\n",
    "<figcaption align = \"center\"> 量子计算过程 </figcaption>\n",
    "</div>\n",
    "\n",
    "接下来，我们将具体介绍不同类型的量子门，并演示他们如何组合成一些量子电路。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2 量子比特门\n",
    "\n",
    "### 2.1 单量子比特门\n",
    "\n",
    "&emsp;&emsp;与经典逻辑门不同，量子电路对单个比特的操作要丰富得多。直觉地理解，经典比特对应 $|0\\rangle$ 和 $|1\\rangle$ 两个量子态，在Bloch球上分别是北极和南极，唯一能涉及的操作也就是在这两个点之间翻转（NOT门）。与之不同，单量子比特态却对应整个球面，我们可以通过变换连接球面上任意两个点。一些最重要的量子门包括泡利（Pauli）矩阵：\n",
    "\n",
    "$$X = \\left(\n",
    "  \\begin{array}{cc}\n",
    "    0 & 1  \\\\\n",
    "    1 & 0 \\\\\n",
    "  \\end{array}\n",
    "\\right), \\quad \n",
    "Y = \\left(\n",
    "  \\begin{array}{cc}\n",
    "    0 & -i  \\\\\n",
    "    i & 0 \\\\\n",
    "  \\end{array}\n",
    "\\right), \\quad\n",
    "Z =  \\left(\n",
    "  \\begin{array}{cc}\n",
    "    1 & 0  \\\\\n",
    "    0 & -1 \\\\\n",
    "  \\end{array}\n",
    "\\right)。\\quad$$\n",
    "\n",
    "要注意$X$，$Y$和$Z$这三个矩阵既是幺正的，又是厄米的。所以我们可以将他们看做量子门，也可以对他们进行测量。\n",
    "\n",
    "另外三个在量子计算中极为重要的量子门包括:\n",
    "\n",
    "$$H = \\frac{1}{\\sqrt{2}}\\left(\n",
    "  \\begin{array}{cc}\n",
    "    1 & 1  \\\\\n",
    "    1 & -1 \\\\\n",
    "  \\end{array}\n",
    "\\right), \\quad \n",
    "S = \\left(\n",
    "  \\begin{array}{cc}\n",
    "    1 & 0  \\\\\n",
    "    0 & i \\\\\n",
    "  \\end{array}\n",
    "\\right), \\quad\n",
    "T = \\left(\n",
    "  \\begin{array}{cc}\n",
    "    1 & 0  \\\\\n",
    "    0 & e^{i\\pi/4} \\\\\n",
    "  \\end{array}\n",
    "\\right)。\\quad$$\n",
    "\n",
    "为了更深入地理解单量子比特门，我们可以用泡利矩阵定义如下三个幺正矩阵：\n",
    "\n",
    "$$\\begin{aligned}\n",
    "R_x(\\theta) &= \\cos(\\theta/2)I - i\\sin(\\theta/2) X = \\left(\n",
    "  \\begin{array}{cc}\n",
    "    \\cos(\\theta/2) & -i\\sin(\\theta/2)  \\\\\n",
    "    -i\\sin(\\theta/2) & \\cos(\\theta/2) \\\\\n",
    "  \\end{array}\n",
    "\\right)，\\\\\n",
    "R_y(\\theta) &= \\cos(\\theta/2)I - i\\sin(\\theta/2) Y =  \\left(\n",
    "  \\begin{array}{cc}\n",
    "    \\cos(\\theta/2) & -\\sin(\\theta/2)  \\\\\n",
    "    \\sin(\\theta/2) & \\cos(\\theta/2) \\\\\n",
    "  \\end{array}\n",
    "\\right)，\\\\\n",
    "R_z(\\theta) &= \\cos(\\theta/2)I - i\\sin(\\theta/2) Z =  \\left(\n",
    "  \\begin{array}{cc}\n",
    "    e^{-i\\theta/2} & 0  \\\\\n",
    "    0 & e^{i\\theta/2} \\\\\n",
    "  \\end{array}\n",
    "\\right)。\n",
    "\\end{aligned}$$\n",
    "\n",
    "这三个矩阵分别称为绕Bloch球上的$x,y,z$轴顺时针旋转$\\theta$角。我们以$R_z$为例：\n",
    "\n",
    "$$R_z(\\alpha)(\\cos(\\theta/2)|0\\rangle + \\sin(\\theta/2)e^{i\\varphi}|1\\rangle) \\cong \\cos(\\theta/2)|0\\rangle + \\sin(\\theta/2)e^{i(\\varphi+\\theta)}|1\\rangle$$\n",
    "\n",
    "而这正是量子态在Bloch球上绕着$Z$轴顺时针旋转了$\\theta$。$R_x，R_y$的验证要复杂些，我们这边不做展开。除了$x,y,z$轴的旋转外，我们也可以找到绕任意单位向量$\\hat{n}=(n_x,n_y,n_z)$旋转的单量子比特门：\n",
    "\n",
    "$$R_{\\hat{n}}(\\theta)=\\cos(\\theta/2)I + i \\sin(\\theta/2)(n_xX + n_y Y +n_z Z)。$$\n",
    "\n",
    "事实上，任意单量子比特门都可以看成是绕某根特定轴$\\hat{n}$的旋转，满足：\n",
    "\n",
    "$$U_1 \\cong R_{\\hat{n}}(\\theta)，$$\n",
    "\n",
    "其中$\\theta$，$\\hat{n}$完全由$U_1$决定。\n",
    "\n",
    "如果我们只能进行绕固定轴的旋转，我们仍然可以实现任意单量子比特门的幺正变化。这里我们有以下非常有用的定理：\n",
    "\n",
    "&emsp;&emsp;定理：任意作用在单量子比特上的幺正操作 $U_1$ ,都可以分解为绕任意2根固定的互相垂直的轴的旋转。以$y$轴和$z$轴为例，我们有：\n",
    "\n",
    "$$U_1\\cong R_z(\\beta)R_y(\\gamma)R_z(\\delta),$$\n",
    "\n",
    "其中$\\beta,\\gamma,\\delta$由$U_1$决定。\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "X=array([[0., 1.],\n",
      "       [1., 0.]])\n",
      "\n",
      "Y=array([[ 0.+0.j, -0.-1.j],\n",
      "       [ 0.+1.j,  0.+0.j]])\n",
      "\n",
      "Z=array([[ 1.,  0.],\n",
      "       [ 0., -1.]])\n",
      "\n",
      "H=array([[ 0.70710678,  0.70710678],\n",
      "       [ 0.70710678, -0.70710678]])\n",
      "\n",
      "S=array([[1.+0.j, 0.+0.j],\n",
      "       [0.+0.j, 0.+1.j]])\n",
      "\n",
      "T=array([[1.        +0.j        , 0.        +0.j        ],\n",
      "       [0.        +0.j        , 0.70710678+0.70710678j]])\n",
      "\n",
      "rx_square=array([[ 0.49999997+0.j, -0.49999997-0.j],\n",
      "       [-0.49999997-0.j,  0.49999997+0.j]], dtype=complex64)\n",
      "\n",
      "ry_square=array([[0.49999997+0.j, 0.49999997-0.j],\n",
      "       [0.49999997+0.j, 0.49999997+0.j]], dtype=complex64)\n",
      "\n",
      "rz_square=array([[0.-0.99999994j, 0.+0.j        ],\n",
      "       [0.+0.j        , 0.+0.99999994j]], dtype=complex64)\n",
      "\n"
     ]
    }
   ],
   "source": [
    "import tensorcircuit as tc\n",
    "import tensorflow as tf\n",
    "import math\n",
    "import numpy as np\n",
    "\n",
    "tc.set_backend(\"tensorflow\")\n",
    "\n",
    "X = tc.gates._x_matrix  # same as tc.gates.xgate().tensor.numpy()\n",
    "Y = tc.gates._y_matrix  # same as tc.gates.ygate().tensor.numpy()\n",
    "Z = tc.gates._z_matrix  # same as tc.gates.zgate().tensor.numpy()\n",
    "H = tc.gates._h_matrix  # same as tc.gates.hgate().tensor.numpy()\n",
    "S = tc.gates._s_matrix\n",
    "T = tc.gates._t_matrix\n",
    "\n",
    "print(f\"{X=}\\n\")\n",
    "print(f\"{Y=}\\n\")\n",
    "print(f\"{Z=}\\n\")\n",
    "print(f\"{H=}\\n\")\n",
    "print(f\"{S=}\\n\")\n",
    "print(f\"{T=}\\n\")\n",
    "\n",
    "theta = math.pi / 2\n",
    "\n",
    "rx = tc.gates.rx_gate(theta).tensor.numpy()\n",
    "ry = tc.gates.ry_gate(theta).tensor.numpy()\n",
    "rz = tc.gates.rz_gate(theta).tensor.numpy()\n",
    "\n",
    "# print(f\"{rx=}\\n\")\n",
    "# print(f\"{ry=}\\n\")\n",
    "# print(f\"{rz=}\\n\")\n",
    "\n",
    "rx_square = rx**2\n",
    "ry_square = ry**2\n",
    "rz_square = rz**2\n",
    "\n",
    "print(f\"{rx_square=}\\n\")\n",
    "print(f\"{ry_square=}\\n\")\n",
    "print(f\"{rz_square=}\\n\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.2 两量子比特门\n",
    "\n",
    "&emsp;&emsp;如果我们只能使用单量子比特门，那么能做的事情是相当有限的，因为每个量子比特都相互独立。为了充分利用量子力学的特性，我们需要考虑作用在多个量子比特上的量子门。本节考虑作用在两个量子比特上的量子门。数学上，两量子比特门只是一个4维的幺正矩阵。这里我们着重介绍一个特别重要的两量子比特门——受控非门 (controlled NOT 或者 $\\rm CNOT$)。 \n",
    "\n",
    "* > 由于幺正变换是一个线性变换，我们只需要考察基向量在$\\rm CNOT$的变换，即可完全确定这个幺正变换。这是因为\n",
    "\n",
    "$$\\begin{aligned}\n",
    "\\rm CNOT |\\psi\\rangle &= \\rm CNOT(\\alpha|00\\rangle+\\beta|01\\rangle+\\gamma|10\\rangle+\\delta|11\\rangle)\\\\\n",
    "&=\\alpha \\rm CNOT |00\\rangle+\\beta \\rm CNOT |01\\rangle+\\gamma \\rm CNOT |10\\rangle+\\delta \\rm CNOT|11\\rangle)\n",
    "\\end{aligned}$$\n",
    "\n",
    "如果我们定义$\\rm CNOT$对基向量做了以下变换：\n",
    "\n",
    "$$\\begin{aligned}\n",
    "&|00\\rangle \\rightarrow |00\\rangle,\\\\\n",
    "&|01\\rangle \\rightarrow |01\\rangle,\\\\\n",
    "&|10\\rangle \\rightarrow |11\\rangle,\\\\\n",
    "&|11\\rangle \\rightarrow |10\\rangle，\n",
    "\\end{aligned}$$\n",
    "\n",
    "那么$\\rm CNOT |\\psi\\rangle$的状态就完全确定了。\n",
    "\n",
    "&emsp;&emsp;我们可以发现，当第一个量子比特处在 $|0\\rangle$ 时，第二个量子比特的状态不变；如果第一个量子比特处于$|1\\rangle$态时，那么第二个量子比特状态发生翻转。这就像是第一个量子比特控制了第二个量子比特，这就是“受控”一词的来源。因此，第一个量子比特也叫控制比特（Control 或者 C），第二个量子比特称为目标比特（Target或者T）。将$\\rm CNOT$写成矩阵的形式，我们就有：\n",
    "\n",
    "$${\\rm CNOT} = \\left(\n",
    "  \\begin{array}{cccc}\n",
    "    1 & 0 & 0 & 0 \\\\\n",
    "    0 & 1 & 0 & 0 \\\\\n",
    "    0 & 0 & 0 & 1 \\\\\n",
    "    0 & 0 & 1 & 0 \\\\\n",
    "  \\end{array}\n",
    "\\right)，$$\n",
    "\n",
    "其中第1-4列分别对应$|00\\rangle， |01\\rangle，|10\\rangle， |11\\rangle$。通常，我们用以下符号来表示$\\rm CNOT$：\n",
    "\n",
    "<div align = center>\n",
    "<img src=\"./img/CNOT.png\" width=\"150\" />\n",
    "<figcaption align = \"center\"> CNOT门 </figcaption>\n",
    "</div>\n",
    "\n",
    "其中，$\\bullet$ 所在的横线代表控制量子比特，$\\oplus$ 所在的横线代表目标量子比特。\n",
    "\n",
    "&emsp;&emsp;$\\rm CNOT$门一个重要的作用就是制备纠缠态。考虑三个量子比特初始制备于$|000\\rangle$态（可以通过分别对三个量子比特进行$Z$的测量来完成），那么我们就能通过下图所示的电路来制备3比特的GHZ态：\n",
    "<div align = center>\n",
    "<img src=\"./img/3GHZ.png\" width=\"200\" />\n",
    "<figcaption align = \"center\"> GHZ态的制备电路</figcaption>\n",
    "</div>\n",
    "\n",
    "* >  **GHZ态的制备：** 经过第一个H门后，量子态变为\n",
    "\n",
    "$$|\\psi\\rangle_1=1/\\sqrt{2}(|0\\rangle+|1\\rangle)|00\\rangle=1/\\sqrt{2}(|0\\rangle|00\\rangle+|1\\rangle|00\\rangle)，$$\n",
    "\n",
    "经过第一个${\\rm CNOT}$门后，量子态变成\n",
    "\n",
    "$$|\\psi\\rangle_2=1/\\sqrt{2}(|0\\rangle|00\\rangle+|1\\rangle|10\\rangle)=1/\\sqrt{2}(|00\\rangle+|11\\rangle)|0\\rangle，$$\n",
    "\n",
    "经过第二个${\\rm CNOT}$门后，量子态变成\n",
    "\n",
    "$$|\\psi\\rangle_3=1/\\sqrt{2}(|000\\rangle+|111\\rangle)。$$\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[1. 0. 0. 0.]\n",
      " [0. 1. 0. 0.]\n",
      " [0. 0. 0. 1.]\n",
      " [0. 0. 1. 0.]]\n",
      "zeros=102, ones=98\n"
     ]
    }
   ],
   "source": [
    "print(tc.gates._cnot_matrix)\n",
    "\n",
    "# GHZ 态模拟\n",
    "\n",
    "circuit = tc.Circuit(3)\n",
    "circuit.H(0)\n",
    "circuit.CNOT(0, 1)  # 第一个参数表示第一个要作用的线路，第二个参数表示第二个要作用的线路\n",
    "circuit.CNOT(0, 2)\n",
    "\n",
    "zeros, ones = 0, 0\n",
    "# 模拟100次\n",
    "for _ in range(200):\n",
    "    res = circuit.measure(0, 1, 2, with_prob=False)\n",
    "    if res[0].numpy().sum() == 0:  # |000>\n",
    "        zeros += 1\n",
    "    elif res[0].numpy().sum() == 3:  # |111>\n",
    "        ones += 1\n",
    "\n",
    "print(f\"{zeros=}, {ones=}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3 量子门的普适性（universality）\n",
    "\n",
    "&emsp;&emsp;正如经典逻辑电路都可以用NAND门来构造一样，对量子电路，我们也希望可以找到一个固定的量子门的集合，并通过这个集合中的量子门来构造所有的量子电路。但是注意，这里的挑战在于，幺正变换是连续变换，而给定的一个量子门集合，有限个量子门所能实现的幺正变换数量是有限的。\n",
    "\n",
    "&emsp;&emsp;但实际上，我们仍然可以用有限的量子门“足够好”地近似任意幺正变换。这里我们不加证明地给出以下重要定理：\n",
    "\n",
    "&emsp;&emsp;<b>量子普适性定理：任意作用在$n$个量子比特上的幺正变换$U_n$，都可以拆分成包含 $m=O(4^n)$个单量子比特门和CNOT门电路。更进一步，我们可以仅通过$H$,$S$,$T$和 $\\rm CNOT$这组有限个量子门所组成的电路$\\tilde{U}_n$来近似这$m$个量子门组成的电路$U_n$，所需要$H$,$S$,$T$和 $\\rm CNOT$量子门的总数为$O(m\\log(m/\\epsilon))$，其中$\\epsilon$为$U_n$与$\\tilde{U}_n$间的误差。{$H$,$S$,$T$和 $\\rm CNOT$}称为普适门集（universal gate set）</b>\n",
    "\n",
    "这样，我们可以通过增加少量的量子门，使量子电路产生的幺正变化和目标幺正变换之间的差距指数地减少！\n",
    "\n",
    "\n",
    "* > 例子：${\\rm Toffoli}$ 门。这种门可以看成是${\\rm CNOT}$门的一种拓展——它有两个控制量子比特和一个目标量子比特。只有当两个控制量子比特处于$|11\\rangle$态时，目标量子比特才会翻转。它的电路符号如下图所示，其矩阵表示是：\n",
    "\n",
    "$${\\rm Toffoli} = \\left(\n",
    "  \\begin{array}{cccccccc}\n",
    "    1 & 0 & 0 & 0  & 0 & 0& 0&0 \\\\\n",
    "    0 & 1 & 0 & 0 & 0 & 0& 0&0\\\\\n",
    "    0 & 0 & 1& 0 & 0 & 0& 0&0\\\\\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& 0&1\\\\\n",
    "        0 & 0 & 0 & 0  & 0 & 0& 1&0\\\\\n",
    "  \\end{array}\n",
    "\\right)$$\n",
    "\n",
    "<div align = center>\n",
    "<img src=\"./img/Toffoli_circuit.png\" width=\"150\" />\n",
    "<figcaption align = \"center\"> Toffoli门 </figcaption>\n",
    "</div>\n",
    "\n",
    "\n",
    "\n",
    "* > ${\\rm Toffoli}$ 门的分解：正如普适性定律所陈述的，我们可以通过$H$，$T$，$S$和${\\rm CNOT}$门来构造${\\rm Toffoli}$门，具体的电路图如下图所示，其中\n",
    "\n",
    "$$T^\\dagger = \\left(\n",
    "  \\begin{array}{cc}\n",
    "    1 & 0  \\\\\n",
    "    0 & e^{-i\\pi/4} \\\\\n",
    "  \\end{array}\n",
    "\\right) = S^3T。$$\n",
    "\n",
    "称为$T$的共轭。注意，这里对${\\rm Toffoli}$的构造是精确无误差的。\n",
    "<div align = center>\n",
    "<img src=\"./img/Toffoli.png\" width=\"450\" />\n",
    "<figcaption align = \"center\"> Toffoli门的分解 </figcaption>\n",
    "</div>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[1. 0. 0. 0. 0. 0. 0. 0.]\n",
      " [0. 1. 0. 0. 0. 0. 0. 0.]\n",
      " [0. 0. 1. 0. 0. 0. 0. 0.]\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. 0. 1.]\n",
      " [0. 0. 0. 0. 0. 0. 1. 0.]]\n"
     ]
    }
   ],
   "source": [
    "print(tc.gates._toffoli_matrix)  # Toffli门对应的矩阵"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "# toffoli 门分解校验\n",
    "\n",
    "c = tc.Circuit(3)\n",
    "c.H(2)\n",
    "c.CNOT(1, 2)\n",
    "c.TD(2)\n",
    "c.CNOT(0, 2)\n",
    "c.T(2)\n",
    "c.CNOT(1, 2)\n",
    "c.TD(2)\n",
    "c.CNOT(0, 2)\n",
    "c.TD(1)\n",
    "c.T(2)\n",
    "c.CNOT(0, 1)\n",
    "c.H(2)\n",
    "c.TD(1)\n",
    "c.CNOT(0, 1)\n",
    "c.T(0)\n",
    "c.S(1)\n",
    "\n",
    "np.testing.assert_allclose(c.matrix(), tc.gates._toffoli_matrix, atol=1e-6)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 4 量子线路\n",
    "\n",
    "### 4.1 经典可逆线路\n",
    "\n",
    "一般来说，大部分的经典的逻辑门是不可逆。比如**与**门（AND），当输出是0时我们无法得知输入是00、01或者10；但最简单就如**非**门就是可逆的，可以通过输出值取反得到输入值。\n",
    "\n",
    "但想要构造更复杂的电路，还是要通过结构上的构造，使用更多的门来构造出可逆的线路的，这时线路的输入输出有且仅有唯一确定的值。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.2 可逆计算 （reversible computation）\n",
    "\n",
    "&emsp;&emsp;如果一个逻辑门存在逆操作，即给定输出，我们可以确定输入状态，那我们称其为可逆的。我们可能已经发现，经典逻辑门和量子逻辑门的一个区别在于，经典逻辑门有时是不可逆的（例如AND门的输出0对应00，10，01三个输入状态，我们无法判断哪一个是真正的输入态），而量子逻辑门必须是可逆的（因为幺正变换是可逆的，且有 $U^{-1}=U^\\dagger$ ）。但是如果稍微小心一点，在有辅助比特的帮助下，我们可以将经典逻辑门转换成可逆的。通过构造可逆电路，我们就有了从经典计算到量子计算的桥梁。\n",
    "\n",
    "\n",
    "&emsp;&emsp;我们先看一个经典逻辑门，Fredkin门。这个逻辑门的真值表如下图所示。通过观察，我们可以发现，当 $c=1$ 时，Fredkin门对$a$和$b$进行了置换（SWAP）。从真值表可以看出，Fredkin门的输入和输出是一一对应的，所以它是可逆的（它的逆运算就是自己）。\n",
    "<div align = center>\n",
    "<img src=\"./img/Fredkin.png\" width=\"350\"  />\n",
    "<figcaption align = \"center\"> Fredkin 门 </figcaption>\n",
    "</div>\n",
    "\n",
    "&emsp;&emsp;对Fredkin的一个重要的应用是构造可逆电路。我们以AND， NOT和SWAP门来说明，它们都可以用可逆的Fredkin门来构造。\n",
    "\n",
    "* 当$a=0，b=y，c=x$时， 我们可以从真值表中提取：\n",
    "\n",
    "$$\\begin{aligned}\n",
    "x = 0, y = 0 \\rightarrow a'= 0, b' = 0\\\\\n",
    "x = 0, y = 1 \\rightarrow a'= 0, b' = 1 \\\\\n",
    "x = 1, y = 0 \\rightarrow a'= 0, b' = 0\\\\\n",
    "x = 1, y = 1 \\rightarrow a'= 1, b' = 0\\\\\n",
    "\\end{aligned}$$\n",
    "\n",
    "我们就能发现$a' = xy$和$b'=\\bar{x}y$($\\bar{(\\cdot)}$代表取反)。这样我们就通过一个辅助比特实现了AND门。利用类似的想法，我们也能构造NOT门和SWAP门，如下图所示。有了AND和NOT，我们就能构造NAND门。由经典普适性定理，所有的经典计算都可以是可逆的。\n",
    "\n",
    "<div align = center>\n",
    "<img src=\"./img/reversible_gates.png\" width=\"400\"  />\n",
    "<figcaption align = \"center\"> Fredkin 门构造可逆的</figcaption>\n",
    "</div>\n",
    "\n",
    "&emsp;&emsp;如果我们构造Fredkin的幺正变换，那我们就能对任意量子态做可逆的经典计算。事实上，$\\rm Toffoli$门也对任意经典计算构造可逆电路。值得注意的是，可逆计算通常需要很多辅助比特（通常正比于所考虑电路的门的数量）。这在经典计算中或许不是问题，但是对量子计算却是致命的。\n",
    "\n",
    "* > 例：假设三个量子比特初始态为$\\frac{1}{\\sqrt{2}}|0\\rangle|y\\rangle\\sum_{x\\in \\{0,1\\}}|x\\rangle$，那么经过量子Fredkin门之后，状态变为\n",
    "\n",
    "$$\\frac{1}{\\sqrt{2}}\\sum_{x\\in \\{0,1\\}}|xy\\rangle|\\bar{x}y\\rangle|x\\rangle$$\n",
    "\n",
    "如果只看量子比特1， 我们发现$y\\cdot 0$和 $y\\cdot 1$ 处于“叠加”的状态，似乎同时进行了两次AND运算。但是注意，第1个量子比特和第2，3个量子纠缠在一起的，会引起量子干涉，这时我们无法获取关于量子比特1的任何信息。\n",
    "\n",
    "&emsp;&emsp;事实上我们可以完全消除这些辅助量子比特的影响，但是这需要额外的电路设计。在此不做展开，有兴趣的读者可以参考：https://qiskit.org/textbook/ch-gates/oracles.html\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.3 量子可逆线路\n",
    "\n",
    "了解到经典计算线路都可以改造成可逆计算线路，逻辑门由矩阵表示后。结合量子线路所有的量子门都是幺正可逆的，我们就知道，量子线路能够实现的计算模型是经典计算的一个超集。\n",
    "\n",
    "\n",
    "事实上，我们相信对于量子线路多项式时间可以解决的问题 BQP 集合是严格大于经典线路多项式时间可以解决的问题 P 集合的，也即量子计算具有本质上超越经典计算的优势。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "tf.Tensor(\n",
      "[1.+0.0000000e+00j 0.+0.0000000e+00j 0.+0.0000000e+00j 0.+0.0000000e+00j\n",
      " 0.-2.1073424e-08j 0.+0.0000000e+00j 0.+0.0000000e+00j 0.+0.0000000e+00j], shape=(8,), dtype=complex64)\n"
     ]
    }
   ],
   "source": [
    "# 量子线路可逆验证\n",
    "\n",
    "c = tc.Circuit(3)\n",
    "c.H(0)\n",
    "c.cnot(0, 1)\n",
    "c.T(2)\n",
    "c.rz(1, theta=0.6)\n",
    "c.toffoli(1, 0, 2)\n",
    "s = c.state()\n",
    "\n",
    "c2 = tc.Circuit(3, inputs=s)\n",
    "c2.toffoli(1, 0, 2)\n",
    "c2.rz(1, theta=-0.6)\n",
    "c2.TD(2)\n",
    "c2.cnot(0, 1)\n",
    "c2.H(0)\n",
    "print(c2.state())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 5 总结\n",
    "\n",
    "&emsp;&emsp;本节我们学习了重要的电路概念。相对于离散的经典逻辑门，量子逻辑门是可以连续变化，且可逆的。我们发现，量子逻辑门包含经典逻辑门。在初态为直积态时，原则上量子计算可以完成所有经典计算的任务（由于可逆性的要求，效率会有所下降），毕竟世界的本质还是量子的。同时，与经典电路一样，对量子电路我们也有普适性定理，即任意幺正变换所对应量子电路都可以用普适门集合中的量子门组成的电路来很好地近似。所以在接下来的算法讨论中，我们也使用局限于普适门集合中的量子门。"
   ]
  }
 ],
 "metadata": {
  "interpreter": {
   "hash": "b9c791f3c91dc075684301e453090e0f95196003e24e6862ac64c4d890189a6a"
  },
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}