万物皆有裂痕，那是光照进来的地方

# 量子线路

# 单量子比特运算

• 重要的量子比特运算由$2\times 2$ 的酉矩阵给出：

  Pauli 阵：

  $$X=\sigma_1=\begin{pmatrix}0&1\\1&0\end{pmatrix}\\ Y=\sigma_2=\begin{pmatrix}0&-i\\i&0\end{pmatrix}\\ Z=\sigma_3=\begin{pmatrix}1&0\\0&-1\end{pmatrix}$$

  Hadamard 门：

  $$H=\frac{1}{\sqrt{2}}\begin{pmatrix}1&1\\1&-1\end{pmatrix}$$

  相位门：

  $$S=\begin{pmatrix}1&0\\0&i\end{pmatrix}$$

  T 门（$\pi/8$ 门）:

  $$T=\begin{pmatrix}1&0\\0&exp(i\pi/4)\end{pmatrix}$$

• 当出现在指数时，Pauli 矩阵导出三类有用的酉矩阵，称为关于$\hat{x},\hat{y},\hat{z}$ 轴旋转的旋转算子，如下定义：

  $$R_x(\theta)=e^{-i\theta X/2}=cos\frac{\theta}{2}I-isin\frac{\theta}{2}X= \begin{pmatrix}cos\frac{\theta}{2}&-isin\frac{\theta}{2}\\-isin\frac{\theta}{2}&cos\frac{\theta}{2}\end{pmatrix}\\ R_y(\theta)=e^{-i\theta Y/2}=cos\frac{\theta}{2}I-isin\frac{\theta}{2}Y= \begin{pmatrix}cos\frac{\theta}{2}&-sin\frac{\theta}{2}\\sin\frac{\theta}{2}&cos\frac{\theta}{2}\end{pmatrix}\\ R_z(\theta)=e^{-i\theta Z/2}=cos\frac{\theta}{2}I-isin\frac{\theta}{2}Z= \begin{pmatrix}e^{-i\theta/2}&0\\0&e^{i\theta/2}\end{pmatrix}\\$$

  推广地，设$(\hat{n_x},\hat{n_y},\hat{n_z})$ 是三维空间中的单位向量，则绕其旋转$\theta$ 的算子定义为：

  $$R_{\hat{n}}(\theta)=exp(-i\theta\hat{n}\cdot\overrightarrow{\sigma}/2)=cos\frac{\theta}{2}I-isin\frac{\theta}{2}(n_xX+n_yY+n_zZ)$$

• 单量子比特的酉算子都可以写成：

  $$U_{2\times 2}=e^{i\alpha}R_{\hat{n}}(\theta)$$

  其中：

  $$若U=aI+bX+cY+dZ\\ a=cos\frac{\theta}{2}e^{i\alpha}\\ b=-in_xsin\frac{\theta}{2}e^{i\alpha}\\ c=-in_ysin\frac{\theta}{2}e^{i\alpha}\\ d=-in_zsin\frac{\theta}{2}e^{i\alpha}$$

• 单量子比特上的酉算子可以写成很多形式，例如旋转的组合乘上全局相移：

  （单量子比特的$z-y$ 分解）U 是单量子比特上的任意酉算子，则存在$\alpha,\beta,\gamma,\delta$，使得

  $$U=e^{i\alpha}R_z(\beta)R_y(\gamma)R_z(\delta)$$

  证明：因为 U 是酉的，则 U 的行列均构成正交标准基，因此可以将$U=\begin{pmatrix}a&b\\c&d\end{pmatrix}$ 四个自由度写成：

  $$U=\begin{pmatrix}e^{i(\alpha-\beta/2-\delta/2)}cos\frac{\gamma}{2}&-e^{i(\alpha-\beta/2+\delta/2)}sin\frac{\gamma}{2}\\ e^{i(\alpha+\beta/2-\delta/2)}sin\frac{\gamma}{2}&e^{i(\alpha+\beta/2+\delta/2)}cos\frac{\gamma}{2} \end{pmatrix}=e^{i\alpha}R_z(\beta)R_y(\gamma)R_z(\delta)$$

  * 这其实也告诉我们酉矩阵的一般形式。

  由证明，可以看出，若$U=\begin{pmatrix}a&b\\c&d\end{pmatrix}$,

  $$\gamma=2arctan\frac{|b|}{|a|}\\ \beta是a和c的辐角差\\ \delta是c和d的辐角差\\ \alpha可以最后观察下差的相位$$

  本质在于，U 描述的是 Bloch 球面上一点怎么到另一点的。

  例如$|\psi'\rang=U|\psi\rang$，可以先绕 Z 轴将$|\psi\rang,|\psi'\rang$ 均转入$zOx$ 平面，在绕 Y 轴在$zOx$ 平面内让它们重合。所以其实就是$|\psi\rang$ 先绕 Z 轴进入$zOx$ 平面，再绕 Y 轴转至$|\psi'\rang$ 在$zOx$ 上的投影，再绕 Z 轴转到$|\psi'\rang$。

• 推论：设 U 是单量子比特上的酉门，则存在单量子比特上的酉算子 A,B,C 使得 ABC=I 且$U=e^{i\alpha}AXBXC$。

  证明：仍采用$z-y$ 分解的记号，记

  $$A=R_z(\beta)R_y(\gamma/2),B=R_y(-\gamma/2)R_z(-(\delta+\beta)/2),C=R_z((\delta-\beta)/2)$$

  则有$ABC=I$（绕着绕着绕回去了）

  又因为$X^2=I$, 且$XR_y(\theta)X=R_y(-\theta)$(Ex4.7，不难证明)，所以

  $$XBX=(XR_y(-\gamma/2)X)(XR_z(-(\delta+\beta)/2)X)=R_y(\gamma/2)R_z((\delta+\beta)/2)$$

  所以

  $$AXBXC=R_z(\beta)R_y(\gamma /2)R_y(\gamma/2)R_z((\delta+\beta)/2)R_z((\delta-\beta)/2)=R_z(\beta)R_y(\gamma)R_z(\delta=U)$$

  证毕

• 量子门记号 ("-" 表示量子比特，“/" 表示量子比特束)

# 受控运算

• 受控运算的原型是受控非门（CNOT 门），它是具有分别称为控制量子比特（control qubit）和目标量子比特（target qubit）的双量子比特门。相当于$|c\rang|t\rang\rightarrow|c\rang|t\oplus c\rang$，，如果控制量子比特为$|1\rang$，则目标量子比特进行比特翻转，否则不动。

  $$U=\begin{pmatrix}1&0&0&0\\0&1&0&0\\0&0&0&1\\0&0&1&0\end{pmatrix}$$

  注意

$$(a|0\rang+b|1\rang)\otimes(\alpha|0\rang+\beta|1\rang)=a\alpha|00\rang+a\beta|01\rang+b\alpha|10\rang+b\beta|11\rang$$

在经过 CNOT 门后，进入状态:

$$|\psi'\rang=a\alpha|00\rang+a\beta|01\rang+b\alpha|11\rang+b\beta|10\rang$$

此时，$|\psi'\rang$ 将无法写成两个单量子比特状态的张量积，故它是个纠缠态。

CNOT 门常用表示。

• 推广地，有一般受控酉算子门：

  如果控制量子比特是$|1\rang$，则对目标量子比特作用酉算子 U。

• 在 Hadamard 门作用后，控制量子比特和目标量子比特的角色会互换。在 CNOT 门作用下：

  $$|++\rang\rightarrow|++\rang\\ |-+\rang\rightarrow|-+\rang\\ |--\rang\rightarrow|+-\rang\\ |+-\rang\rightarrow|--\rang$$

  即第二量子比特为$|-\rang$ 时第一量子比特$\pm$ 变换。因此：

• 下面考虑如何实现受控任意酉运算。

  首先，根据前面推论，任意单量子比特酉算子$U=e^{i\alpha}AXBXC$，其中$ABC=I$。

  所以可以先实现受控相移：

  注意到左线路之所以等价于右线路，是因为作为一个双量子比特系统，左线路和右线路都能完成：

  $$|00\rang\rightarrow|00\rang,|01\rang\rightarrow|01\rang,|10\rang\rightarrow e^{i\alpha}|10\rang,|11\rang\rightarrow e^{i\alpha}|11\rang$$

  下面注意受控 X 门就是 CNOT 门，然后加上 ABC，则有：

  ” 受控 “全部用 CNOT 门解决。因为$ABC=I$，所以若第一量子比特不为$|1\rang$，第二量子比特也只会不变。

• 多控制量子比特算子。设共有$n+k$ 个量子比特，前 n 个量子比特为控制比特，当且仅当前 n 个量子比特都为$|1\rang$ 时，将 U（一个 k 量子比特酉门）作用于后 k 个量子比特。即：

  $$C^n(U)|x_1x_2...x_n\rang|\psi\rang=|x_1x_2...x_n\rang U^{x_1x_2...x_n}|\psi\rang$$

  而 Toffoli 门（即$C^2(X)$) 就可以在 Figure4.8 中取$V=(1-i)(I+iX)/2$ 得到。即 Toffoli 门可以仅通过单、双量子比特门实现，而经典比特门做不到。

• 最终我们将证明，任意一个酉算子可以仅由 Hadamard、相位、CNOT、和 T 门组合来实现，这实现是一个很好的近似，下图展示了 Toffoli 门的一个构造，它非常有用：

• 下面解决如何利用已有的量子门实现$C^n(U)$：

  上图是一个实现$C^n(U)$ 的特别简单的线路，氛围三段，由 n 个控制量子比特，n-1 个工作量子比特和一个目标量子比特构成。

  工作量子比特初始都是$|0\rang$ , 而左半边做的工作就是把控制量子比特 “与” 起来。最后一个工作量子比特就是与的结果。然后右侧再把工作量子比特还原回去。

• 当然受控门有时候也需要反过来，例如 “当控制比特为$|0\rang$ 翻转目标比特”，这也有记号和等价的控制门：

  如果控制比特数量大于 1 时，控制信息可以变成一个二进制串，例如当且仅当控制比特为$|010\rang$ 时翻转目标比特：

  同样，目标量子比特也可以有多个：

• 线路恒等式：（令 C 是第一量子比特做控制比特，第二量子比特做目标量子比特的受控非门，$X_i$ 表示作用在第 i 量子比特上的 X 门，则有：

  $$CX_1C=X_1X_2,CY_1C=Y_1X_2,CZ_1C=Z_1\\ CX_2C=X_2,CY_2C=Z_1Y_2,CZ_2C=Z_1Z_2\\ R_{z,1}(\theta)C=CR_{z,1}(\theta),R_{x,2}(\theta)C=CR_{x,2}(\theta)$$

# 测量

• 出现在量子线路最后的元素就是测量。量子线路中的测量符号都表示投影测量，因为一般测量可以通过引入酉变换和辅助量子来用投影测量表示。

• 量子测量的两大原理：

  • 推迟测量原理：总可以把测量从量子线路的中间步骤移到线路的末端。如果测量的结果被用于线路的某些阶段，则经典的条件运算可以被条件量子运算代替。例如：

    上图两个线路是等价的。图一有一个经典条件运算，即 “判断实验结果$M_1,M_2$ 是否是 1”，而这可以转换成量子的受控运算。

    其实我认为这也是因为图 1 中测量后第一、第二量子比特没有继续操作和测量了。

  • 隐含测量原理：量子电路中任何未终结的量子连线（即该连线对应的量子位在演化过程中没有被测量），最终总可以假设为该连线（对应的量子位）已经被测量，而不影响其他量子位的计算结果。

• 测量扮演着量子世界和经典世界之间的界面，被视为一个不可逆运算。

# 通用量子门

• 一组门对量子计算是通用的，如果用这组门的量子线路可以以任意精度近似任意的酉运算。现在描述量子计算的三个通用性构造步骤，这些可以层层推进，最后可以证明 Hadamard、相位、CNOT、和 T 门以任意精度近似任意酉运算。以下三个步骤分别对应要介绍的三个部分：

  • 步骤 1：任意酉算子可以精确表示为一些两级酉算子的乘积。（两级酉门是通用的）
  • 步骤 2：所有两级酉算子都可以精确地用单量子比特门和 CNOT 门表示（$U=e^{i\alpha}AXBXC$）（单量子比特门和 CNOT 门是通用的）。
  • 步骤 3：单量子比特运算可由 Hadamard、相位和 T 门以任意精度近似（通用运算的离散集合）。

• 注：两级酉算子即为一个作用在 d 维 Hilbert 空间上的酉矩阵 U，但它只作用于两个或更少的分量。也就是说，U 至少有 d-2 行为只有对角线元素为 1 的单位矩阵。例如 d=4:

  $$U=\begin{pmatrix}\frac{1}{\sqrt{2}}&\frac{1}{\sqrt{2}}&0&0\\\frac{1}{\sqrt{2}}&-\frac{1}{\sqrt{2}}&0&0\\0&0&1&0\\0&0&0&1\end{pmatrix}$$

  就是一个二级酉算子，因为其只作用四维向量的前两个分量。

# 两级酉门（two-level unitary gate）是通用的

考虑一个作用在 d 维 Hilbert 空间上的酉矩阵 U。本节将说明怎样将 U 分解成两级酉矩阵的乘积。

• 先考虑三阶矩阵的情况。设$U=\begin{pmatrix}a&d&g\\b&e&h\\c&f&i\end{pmatrix}$，我们要找出两级酉矩阵$U_1,U_2,U_3$ 使得$U_3U_2U_1U=I$

  则$U=U_1^\intercal U_2^\intercal U_3^\intercal$ 即为一个两级酉门分解。

  • 先构造$U_1$：

    若 b=0，则$U_1=I$，否则

    $$U_1=\begin{pmatrix}\frac{a^*}{\sqrt{|a|^2+|b|^2}}&\frac{b^*}{\sqrt{|a|^2+|b|^2}}&0\\ \frac{b}{\sqrt{|a|^2+|b|^2}}&\frac{-a}{\sqrt{|a|^2+|b|^2}}&0\\ 0&0&1 \end{pmatrix}$$

    此时，U_1U=\begin{pmatrix}a'&d'&g'\\0&e'&h'\\c'&f'&i'\end

    其中，重点在于把第二行第一列变成 0. 而且$U_1U$ 仍为酉矩阵。

  • 再构造$U_2$，我们希望在这个基础上使得$U_2U_1U$ 的第三行第一列也变成 0。

    若$c'=0$，则$U_2=\begin{pmatrix}a'^*&0&0\\0&1&0\\0&0&1\end{pmatrix}$，否则：

    $$U_2=\begin{pmatrix}\frac{a'^*}{\sqrt{|a'|^2+|c'|^2}}&0&\frac{c'^*}{\sqrt{|a'|^2+|c'|^2}}\\ 0&1&0\\ \frac{c'}{\sqrt{|a'|^2+|c'|^2}}&0&\frac{-a'}{\sqrt{|a'|^2+|c'|^2}} \end{pmatrix}$$

    此时，U_2U_1U=\begin{pmatrix}a''&d''&g''\\0&e''&h''\\0&f''&i''\end

    由于$U_2U_1U$ 仍是酉的，可以导出$a''=1,d''=g''=0$。

  • 最后，构造

    $$U_3=(U_2U_1U)^\intercal=\begin{pmatrix}1&0&0\\0&e''^*&f''^*\\0&h''^*&i''^*\end{pmatrix}$$

    则有$U_3U_2U_1U=I$。结束。

  此时，$U=U_1^\intercal U_2^\intercal U_3^\intercal$ 即为一个 U 的两级酉门分解。

• 再考虑一般情况，例如一个 d 维的矩阵，则先可以找到两级酉矩阵$V_1,V_2,...,V_{d-1}$，使得$V_{d-1}...V_1V$ 的第一列第一行除了第一个元素都是 0，第一个元素为 1。再重复这个过程，寻找$V_1',V_2',...,V_{d-2}'$ 使得第二行第二列也变成只有第二个元素为 1 的单位向量，以此类推。

  最后，有$V_{k}...V_1U=I,U=V_1^\intercal...V_k^\intercal$。其中，$k\leq(d-1)+(d-2)+...+1=d(d-1)/2$

  则 n 个量子比特系统上的酉门可以写成至多$2^{n}(2^{n}-1)/2$ 个两级酉矩阵之积。

  但存在$d\times d$ 的酉矩阵$U$，它不能分解为少于$d-1$ 个两级酉矩阵的积。

# 单量子比特门和受控非门是通用的

• 证明了 d 维 Hilbert 空间上的任意酉矩阵可以写成两级酉矩阵的乘积形式，现在证明单量子比特门和受控非门可以实现 n 量子比特空间上的任意二级酉运算。这两个结论结合起来可以看到单量子比特门和受控非门可以实现 n 量子比特上的任意酉运算，于是它们对于量子计算来说是通用的。

• 设 U 是一个 n 量子比特计算机上的两级酉矩阵。设 U 在状态$|s\rang,|t\rang$ 张成的状态空间上的作用是不平凡的，其中$s=s_1..s_n,t=t_1...t_n$ 是状态的二进制展开。令$\tilde{U}$ 是$U$ 的一个$2\times 2$ 的不平凡子酉阵，则$\tilde{U}$ 可以看作是作用在单量子比特上的酉算子。

  现在的目标是基于单量子比特门和受控非门，构造一个实现$U$ 的线路。为此，我们需要使用 Gray 码。

  * 连接 s 和 t 的 Gray 码：以 s 开头 t 结尾的一组二进制数，使得相邻两个二进制数恰有一位不同。* 例:

  $$s=(101001)_2,t=(110011)_2\\ Gray=\{\\ (101001)_2\\ (101011)_2\\ (100011)_2\\ (110011)_2\\ \}$$

  令$g_1$ 到$g_m$ 是连接 s 和 t 的 gray 码，其中$g_1=s,g_m=t$。则$m\leq n+1$，因为 s 和 t 最多有 n 位不同。

• 实现 U 的基本想法是通过一系列门（比特翻转）实现变换$|g_1\rang\rightarrow|g_2\rang\rightarrow...\rightarrow|g_{m-1}\rang$ 然后进行受控$\tilde{U}$ 运算，目标量子比特是$g_{m-1}$ 和$t$ 不同的那位，控制量子比特要求剩下相同的$n-1$ 位和 t 一样。然后再通过一系列门还原回原本状态。例如酉矩阵：

  $$U=\begin{pmatrix}a&&&&&&&c\\&1&&&&&&\\&&1&&&&&\\&&&1&&&&\\&&&&1&&&\\&&&&&1&&\\&&&&&&1&\\b&&&&&&&d\end{pmatrix}$$

  a,b,c,d 是使得$\tilde{U}=\begin{pmatrix}a&c\\b&d\end{pmatrix}$ 为酉矩阵的任意数。注意到此时$U$ 只有作用在$|000\rang$ 和$|111\rang$ 上是不平凡的。写出连接 000 和 111 的 Gray 码:$(000)_2,(001)_2,(011)_2,(111)_2$ 设计出如下线路：

  考虑下这样做为什么是对的。因为 a,b,c,d 行列是 0 和 7，转为二进制即为$(000)_2,(111)_2$ 即它只作用于这两个状态时是非平凡的。然后将$(000)_2$ 到$(111)_2$ 的比特翻转实际上是把这两位通过交换移到某一个量子比特对应的两位上，最后再交换回去。

• 回到一般情形，实现 n 个量子比特上的任意酉运算需要$O(n^24^n)$ 个单量子比特门和受控非门的线路来实现。事实上，酉运算必须用指数数目的门来实现。为了寻找快速量子算法，必须采取和通用性结构不同的方法。

# 通用运算的一个离散集合

# 酉算子的近似

• 首先，一个离散的门的集合不可能精确实现所有酉运算，因为酉矩阵是连续的。然而，一个离散的门的集合却可以去近似酉运算。

• 设 U 和 V 是同一状态空间上的酉算子，U 是希望实现的酉算子，V 是实际实现的酉算子。定义用 V 实现 U 的误差为：

  $$E(U,V)\equiv max_{|\psi\rang}||(U-V)|\psi\rang||$$

  其中 max 要取遍状态空间中所有的归一化状态$|\psi\rang$。

• 近似量子线路：

  设一个量子系统初态是$|\psi\rang$，并设我要进行酉运算 U 和 V。令 M 是任一个与测量相联系的 POVM 元。则

  $$p_U=\lang\psi|U^\intercal MU|\psi\rang,p_V=\lang\psi|V^\intercal MV|\psi\rang\\ |p_U-p_V|=|\lang\psi|U^\intercal MU|\psi\rang-\lang\psi|V^\intercal MV|\psi\rang|$$

  令$|\Delta\rang=(U-V)|\psi\rang$，利用代数运算和 Cauchy-Schwarz 不等式：

  $$|p_U-p_V|=|\lang\psi|U^\intercal M|\Delta\rang+\lang\Delta|MV|\psi\rang|\\ \leq|\lang\psi|U^\intercal M|\Delta\rang|+|\lang\Delta|MV|\psi\rang|\\ 而\lang\psi|U^\intercal M|\Delta\rang^2\leq\lang\psi |U^\intercal MM^\intercal U|\psi\rang\lang\Delta|\Delta\rang\leq1\cdot\lang\Delta|\Delta\rang\\ 所以|p_U-p_V|\leq|||\Delta\rang||+|||\Delta\rang||=2E(U,V)$$

  这个式子定量地表示了，若$E(U,V)$ 足够小，则测量结果误差也会很小。事实上，有式子：

  $$E(U_mU_{m-1}...U_1,V_mV_{m-1}...V_1)\leq\sum_{i=1}^m E(U_i,V_i)$$

  因为利用三角不等式，有$E(U_2U_1,V_2V_2)\leq E(U_2,V_2)+E(U_1,V_1)$ 然后归纳即可。

• 再精确地描述$|p_U-p_V|\leq 2E(U,V)$ 的含义：对任意初态$|\psi\rang$，在状态$V|\psi\rang$ 上进行测量将给出对$U|\psi\rang$ 的测量的近似的测量统计值。

  假设希望完成一个包含 m 个酉门$U_1,...,U_m$ 的量子线路，不幸的是，只能用门$V_j$ 去近似门$U_j$。为了使实际近似结果和正确结果在一个容许量$\Delta$ 内，只要保证$E(U_i,V_i)\leq\Delta/(2m)$ 就行了。

# Hadamard 门 + 相位门 + 受控非门 +$\pi/8$ 门的通用性

• 首先证明 Hadamard 门和$\pi/8$ 门可以用来以任意精度近似任意单量子比特的酉运算。

  • 考虑 T 门和 HTH 门。T 门除了一个不要紧的全局相位，相当于将一个状态对应 Bloch 球面上的点绕$\hat{z}$ 轴旋转$\pi/4$。而$HTH=e^{i\pi/8}Rx(\frac{\pi}{4})$，即 HTH 门是绕$\hat{x}$ 轴旋转$\pi/4$。这两个门组合起来：

  $$THTH=e^{i\pi/4}R_z(\frac{\pi}{4})R_x(\frac{\pi}{4})=e^{i\pi/4}\{cos^2\frac{\pi}{8}I-i[cos\frac{\pi}{8}(X+Z)+sin\frac{\pi}{8}Y]sin\frac{\pi}{8}\}\\ =e^{i\pi/4}[cos^2\frac{\pi}{8}-i\frac{cos\frac{\pi}{8}(X+Z)+sin\frac{\pi}{8}Y}{\sqrt{1+cos^2\frac{\pi}{8}}}\cdot\sqrt{1+cos^2\frac{\pi}{8}}sin\frac{\pi}{8}]\\ =R_{\hat{n}}(\alpha)$$

  ​ 其中

  $$\hat{n}=\frac{(cos\frac{\pi}{8},sin\frac{\pi}{8},cos\frac{\pi}{8})}{\sqrt{1+cos^2\frac{\pi}{8}}},cos\frac{\alpha}{2}=cos^2\frac{\pi}{8},sin\frac{\alpha}{2}=\sqrt{1+cos^2\frac{\pi}{8}}sin\frac{\pi}{8}$$

  ​ 即仅用 Hadamard 门和 T 门就可以实现$R_{\hat{n}}(\alpha)$，且可以证明这个$\alpha$ 是$2\pi$ 的无理数倍。

  • 下面证明用$R_{\hat{n}}(\alpha)$ 反复迭代就可以以任意精度近似$R_{\hat{n}}(\theta)$。令$\delta>0$ 为希望的精度，且 N 为一个大于$2\pi/\delta$ 的整数。

    定义$\alpha_i=(i\alpha)\quad mod\quad 2\pi,\alpha_i\geq 0$。由抽屉原理，在$1,...,N$ 范围内一定存在$j\neq k$ 使得$|\alpha_j-\alpha_k|\leq 2\pi/N<\delta$。不失一般性设$j>k$。则在$2\pi$ 剩余系里有$\alpha_{j-k}<\delta$。因为$\alpha_{j-k}$ 一定是$2\pi$ 的无理数倍，则有$\alpha_{j-k}\neq 0$。因此可知$\{a_i\}$ 的子序列$\{a_l\}=l\alpha_{j-k}\quad mod\quad 2\pi=\alpha_{l(j-k)}$ 可以填满整个$[0,2\pi)$ 区间，使得子序列中相邻的数距离不超过$\delta$。

    又因为对于任意$\alpha,\beta$，$E(R_{\hat{n}}(\alpha),R_{\hat{n}}(\alpha+\beta))=|1-e^{i\beta/2}|$

    所以对于任意$\epsilon>0$，存在$n$ 使得

    $$E(R_{\hat{n}}(\theta),R_{\hat{n}}(\alpha)^n)=|1-e^{i(n\alpha-\theta)/2}|<\epsilon$$

    因为对于任意$\theta,\delta$ 存在 n，使得$|n\alpha-\theta|<\delta$ 。加上$\lim_{x\rightarrow 0}|1-e^{ix/2}|=0$, 所以其实总能找到$\delta,n$ 使得$E<\epsilon$.

  • 又因为$HR_{\hat{n}(\theta)}H=R_{\hat{m}}(\theta)$, 其中，$\hat{m}=\frac{(cos\frac{\pi}{8},-sin\frac{\pi}{8},cos\frac{\pi}{8})}{\sqrt{1+cos^2\frac{\pi}{8}}}$

    所以$E(R_{\hat{m}}(\theta),R_{\hat{m}}(\alpha)^n)=|H|\psi\rang|^2E(R_{\hat{n}}(\theta),R_{\hat{m}}(\alpha)^n)<\epsilon$。

    又因为 Ex4.11 证明，对于不平行的$\hat{n},\hat{m}$，任意酉算子都可以表示为$U=e^{i\alpha}R_{\hat{n}}(\theta_1)R_{\hat{m}}(\theta_2)...R_{\hat{n}}(\theta_{c-1})R_{\hat{m}}(\theta_{c})$(共 c 项，c 为一个有限数)。

    所以

    $$记U'=R_{\hat{n}}(\theta)^{n_1}[HR_{\hat{n}}(\theta)H]^{n_2}...R_{\hat{n}}(\theta)^{n_{c-1}}[HR_{\hat{n}}(\theta)H]^{n_{c}}\\ 则E(U,U')=\sum_{i=1}^c E(R_{\hat{n}}(\theta_i),R_{\hat{n}}(\theta)^{n_i})或 E(R_{\hat{m}}(\theta_i),R_{\hat{m}}(\theta)^{n_i})<c\epsilon$$

  即任给一个酉算子 U，可以只用 Hadamard 门和$\pi/8$ 门在$\epsilon$ 范围下近似。

  所以说，给定一个包含 m 个受控或单量子比特酉门的量子线路，可以用 Hadamard 门、受控非门和$\pi/8$ 门以任意精度 ($m\epsilon$) 近似这个线路。(复杂度分析书上看不懂，自己写的) 近似一个包含 m 个门的量子线路，若包含很多受控门时，此时效率较低，复杂度下限在 *“单量子比特门和 CNOT 门是通用的” 一节介绍的 “将二级酉门分解成单量子比特门和 CNOT 门”*，这是个指数级别的。但当线路中单量子比特门较多时或全是单量子比特门时，复杂度急剧减小到以$\varTheta(1/\epsilon)$ 的效率近似一个单量子比特门（因为式子$E(R_{\hat{n}}(\theta),R_{\hat{n}}(\alpha)^n)<\epsilon$ 中 n 一定是$<2\pi/\epsilon$ 的），所以近似整个线路复杂度为$\varTheta(m*m/\epsilon)$。这里之所以又乘了个 m，是因为在前面推导中有$E(U,U')<c\epsilon$，如果整条线路想精确到$\epsilon$，就需要把每个门近似所需门数乘个 m 使得每个近似都近似到$\epsilon/m$，这样总近似才能是$m*\epsilon/m$。

• 事实上，由 Solovay-Kitaev 定理，任意单量子比特门可以用离散集合中的$O(log^c(1/\epsilon))$ 个门近似到$\epsilon$ 精度，其中 c 是一个很接近 2 的常数。因此事实上要在$\epsilon$ 精度内要近似一个包含 m 个受控非门和单量子比特酉门的线路，需要离散的$O(mlog^c(m/\epsilon))$ 个门。

# 近似任意酉门一般是难的

• 给定 n 量子比特上的酉变换 U，是否存在 n 多项式规模的线路来近似 U？答案是否定的（一定是指数级别）。

  事实上，需要多少门来产生 n 量子比特的任意状态？是指数的。为了验证这一点，设有 g 类不同的门，每个门至多有 f 个输入量子比特。f 和 g 是由计算硬件所决定的，可视为常数。设有一个包含 m 个门的 n 个量子比特的量子线路，初态为计算基态$|0\rang^{\otimes n}$。（日常看不懂书上复杂度分析自己想的尽量贴合书本：）对于线路中某一个门，假设其有一个输入状态，考虑这个门作用于哪些量子比特，共有$\begin{pmatrix}n\\f\end{pmatrix}$ 种取法，也就是$O(n^f)$（事实上，我认为这里默认 f 很小，大概就是 1~4 差不多）。然后对于每一种取法，可以把 g 种不同的门都上一遍，故一共有$O(n^{fg})$ 种可能的产出的状态。实际上这里默认了很多东西，例如什么叫 “同一类门”，我的理解是以之前两级酉门为例，n 个量子比特上的两级酉门 U 有很多，但是对应的子酉矩阵$\tilde{U}$ 若是一样的则称 U 是同类的（详见单量子比特门与受控非门是通用的）。因此同类的门可以因为作用的量子比特不同而不同。此外为什么说 “最多有 f 个输入量子比特” 结果结果就是$O(n^f)$ 个取法，因为我认为这里默认 f 很小，然后大 O 表示法求得是一个上限。（$C_n^1=O(n),C_n^2=O(n^2)...$）。

  因此，m 个门对于一个输入状态$|0\rang^{\otimes n}$ 的可能输出为$O(n^{fgm})$ 种状态。

# 物理仿真

• 之前在量子系统里我们关心的是薛定谔方程$i\hbar\frac{d|\psi\rang}{dt}=H|\psi\rang$，之前讨论过对于定时的 H，薛定谔方程的解需要计算$e^H$，浙江非常难求。所以好的出发点是考虑一阶：

  $$|\psi(t+\Delta t)\rang\approx(I-iH\Delta t)|\psi(t)\rang$$

  （$\hbar$ 放到 H 里）的解。这是可解的，因为对许多 Hamilton 量 H 可以直接利用量子们来有效近似$I-iH\Delta t$。不过这样的解并不充分。

  近似到高阶的解对许多类 Hamilton 量是可能的。例如在大多数物理系统种，Hamilton 量可以写作局部作用和的形式：

  $$H=\sum_{k=1}^L H_k$$

  其中，$H_k$ 最多作用在常数 c 数目的子系统上，而 L 是 n 的一个多项式。

• （Trotter 公式）令 A 和 B 是 Hermite 算子，则对任意实数 t，有：

  $$\lim_{n\rightarrow\infin}(e^{iAt/n}e^{iBt/n})^n=e^{i(A+B)t}$$

  证明：由泰勒展开

  $$e^{iAt/n}e^{iBt/n}=I+\frac{1}{n}i(A+B)t+O(\frac{1}{n^2})\\ \Rightarrow (e^{iAt/n}e^{iBt/n})^n=I+\sum_{k=1}^n\begin{pmatrix}n\\k\end{pmatrix}\frac{1}{n^k}[i(A+B)t]^k+O(1/n)\\ \begin{pmatrix}n\\k\end{pmatrix}\frac{1}{n^k}=(1+O(\frac{1}{n}))/k!\\ \lim_{n\rightarrow\infin}(e^{iAt/n}e^{iBt/n})^n=\lim_{n\rightarrow\infin}\sum_{k=0}^n\frac{(i(A+B)t)^k}{k!}(1+O(\frac{1}{n}))+O(\frac{1}{n})=e^{i(A+B)t}$$

  与上面类似的证明，可以得到

  $$e^{iA\Delta t}e^{iB\Delta t}+O(\Delta t^2)=e^{i(A+B)t}\\ e^{iA\Delta t/2}e^{iB\Delta t}e^{iA\Delta t/2}+O(\Delta t^3)=e^{i(A+B)t}$$

# 算法：量子仿真

• 输入：

  • 作用在 N 维系统上的 Hamilton 量$H=\sum H_k$，其中每个$H_k$ 作用在规模独立于$N$ 的小的子系统上。
  • 系统在$t=0$ 时刻的初态$|\psi_0\rang$
  • 正的精度$\delta$
  • 期望获得状态对应的时刻$t_f$

• 输出：

• 状态$|\tilde{\psi}(t_f)\rang$，使得$(|\tilde{\psi}(t_f)\rang,e^{-iHt}|\psi_0\rang)^2=\lang\tilde{\psi}(t_f)|e^{-iHt}|\psi_0\rang^2\geq 1-\delta$

• 运行时间：

• $O(poly(1/\delta))$

• 过程

  • 选择一个表示使得$n=poly(logN)$ 个量子比特的状态$|\tilde{\psi}\rang$ 能近似系统状态。并且选择一个近似方法和$\Delta t$ 使得期望误差是可以接受的，并且对某个整数 j，$j\Delta t=t_f$。为迭代构造一个相应的量子线路$U_{\Delta t}$，执行：

    (1) $|\tilde{\psi_0}\rang\leftarrow|\psi_i\rang;j\leftarrow 0$ 状态初始化

    (2) $|\tilde{\psi}_{j+1}\rang\leftarrow U_{\Delta t}|\tilde{\psi}_j\rang$ 迭代

    (3) $j=j+1$，重复 (2) 直到$j\Delta t=t_f$

    (4) $|\tilde{\psi}(t_f)\rang=|\tilde{\psi}_j\rang$

# 例 1：薛定谔方程的量子仿真

• 考虑在一根直线上的运动的具有一维势能$V(x)$ 的一个单粒子，其 Hamilton 量为

  $$H=\frac{P^2}{2m}+V(X)$$

  其中，X 是动量算子（$P|\psi\rang=-i\hbar\frac{\partial}{\partial x}|\psi\rang$），X 是位置算子$X|\psi\rang=x|\psi\rang$。其中 X 的特征值（坐标$X|x\rang=x|x\rang$）是连续的。

  而系统状态$|\psi\rang$ 处于无穷维 Hilbert 空间，在基$|x\rang$ 下，可写成：

  $$|\psi\rang=\int_{-\infin}^{\infin}|x\rang\lang x|\psi\rang dx$$

  实践中，我们只对某个有限趋于$-d\leq x\leq d$ 感兴趣。各异选择离散步长（与系统最短波长相比足够小），使得:

  $$|\tilde{\psi}\rang=\sum_{k=-d/\Delta x}^{d/\Delta x}a_k|k\Delta x\rang$$

  成为$|\psi\rang$ 的一个好的物理近似。这个状态可以用$n=log(2d/\Delta x+1)$（上取整）个量子比特表示。

  剩下的看不懂，寄！

# 例 2

• 设我们有作用在 n 个量子比特上的 Hamilton 量：

  $$H=Z_1\otimes Z_2\otimes ...\otimes Z_n$$

  其中$Z_i$ 为作用在第 i 个量子比特上的 Z 门。事实上，H 就作用了一件事情，即若状态$|s_1...s_n\rang$ 种 s 有偶数个 1，就作用相移算子$e^{iZ\Delta t}$；若有基数个 1，则作用相移算子$e^{-iZ\Delta t}$ 到系统状态上。

  上图就通过引入一个辅助量子比特就精确完成了这个工作。最后得到结果后需要抹除和初态一样的辅助量子比特。

事实上任意 Hamilton 量若具有$H=\otimes_{k=1}^n\sigma_{c(k)}$ 都可以类似以上线路完成，其中$\sigma$ 是 Pauli 阵。因为 X，Y 都可以用单量子比特门转换为 Z 门。