零、碎碎念 本文是之前上量子信息物理导论的小组期末报告中我负责的一部分，略作一些修改发在这里（实际是各种地方...）。 本文对于量子算法和量子门之间的联系作了一个简要的阐述，并介绍了一些基本的量子门电路的实现。当然，要体会量子算法为什么有潜力多快好省，需要去了解现有的那些量子算法的细节，而不是更底层的量子门电路。但这一块是小组其他组员所讲的内容。 本文假定读者对这些概念有所掌握：希尔伯特空间、幺正演化、相干叠加、直积、直和。即，本文针对的是想了解量子计算而有着基本量子力学基础的读者。 本人对研究如何让量子计算机能算数不感兴趣，而感兴趣研究经典计算机算出来的数。当然上课是上课，研究是研究。 主要参考了文献[1, 2]。全部参考文献列在最后。 一、背景介绍 量子体系所独有的相干叠加和纠缠特性，展现出了天生的并行特性，为进一步提高计算能力提供了一个崭新的平台。为了能在量子系统上有效的执行计算，我们首先需要实现以下几个目标： 获得一个有着足够大维度希尔伯特空间中的量子态 ； 对其执行任意的幺正算符 ； 进行任意测量以得到经典的测量结果； 将 个二态系统 (qubit) 相干的放在一起,可以得到一个有 维的量子系统； 如何对单个 qubit 执行任意的幺正算符，以及对少量 qubit 执行一些简单 的联合幺正演化； 在 -qubit 系统上任意复杂的测量都可以分解成一系列幺正算符和单 qubit 上的测量的叠加，而后者是容易的； 经典计算机是成熟的。 由此，我们发现最关键的问题在于，如何通过单 qubit 算符和一些简单的联合算符组合出任意复杂的幺正算符。 二、基本量子门电路 在进一步讨论这个问题之前，我先对一些基本的概念作一个简介。 如前所述，在谈论量子计算时，我们谈的是 个 qubit ，对其执行一系列算符操作，最后执行测量。如下图，我们常常画出横着并排的条直线，从左到右代表着时间顺序，而不同的直线代表不同的 qubit ；在这些直线上排列着各种小方块大方块还有竖线，代表着各种不同的单 qubit 或多 qubit 幺正算符，每一个幺正算符被称为一个（量子）门；人们常将一些简单的量子门组合成更复杂的量子门；整张图就被称为一个量子网络/量子电路。 一个典型的量子电路
人们给一些常用的量子门取了特定的名字，列举几个如下：
即在单 qubit 上作用算符 （简单起见，以后均记做 ）， 翻转，相当于经典中的非门。同理，还有 门和 门。 Hadamard 门：
控制非(Controlled-NOT, CNOT)门： qubit_A = (qubit_B? X:I)* quibt_A;= qubit_B; 这是一个双 qubit 门，其作用为如伪代码所示：若控制位（图中带黑点的线路）为1，则翻转受控制位（图中带十字圆圈的线路），否则不执行操作；而控制位自身始终不动。更量子一点的说法则是
三、分解定理 在开头所提出的问题事实上已经被通过如下一系列定理解决 [3]。 定理 1. 任意 d 维幺正变换 U 总可以被分解成 d(d − 1)/2 个二维幺正变换的乘积，且这些二维幺正变换都是分别作用在同一组任给定的基底中某两个基矢张成的子空间中。 定理 2. 任何作用在一组 n 个 qubit 上的二维幺正变换,均可用一系列单 qubit 门和双 qubit 量子门 CNOT 门依次作用来实现。 定理 3. 作用在任一组 qubit 上的任意幺正变换均可以用一系列单 qubit 量子门和双 qubit 量子门 CNOT 门依次作用来实现。 定理1的证明纯粹是线性代数的一些技巧，这里略过。我们将通过对定理2的证明，来介绍一些较复杂量子门的实现。 四、组合量子门电路 前面我们介绍了控制非门，控制位为1则加 到受控位，一个很自然的想法是，能不能推广到如果控制位为1则加任意 到受控位？即： qubit_A = (qubit_B? U:I)* quibt_A;= qubit_B; 定理 4. 设 为单 qubit 上的任意幺正算符。存在单 qubit 上的幺正算符 使得： 且 ，其中 是某个整体的相因子。 这个定理的证明不难，这里阐述大致思路：在除去相因子 后，单 qubit 上的全体幺正算符构成了 群。而 群与 群，即三维空间中的旋转相对应。由于任意旋转都可以通过欧拉角的办法分解，所以说不难理解总有分解式 有了这个定理，我们便可以很容易看出，下图所示的电路实现了我们所想要的控制 门：当控制位为0时，受控位作用 相当于没作用；而当控制位为1时，受控位作用 ，再加上一个整体的相位 正好就是 。 对于 CNOT 门另外一个推广的想法是，能不能实现两个门控制一个门？也就是说 qubit_A = (qubit_B&& qubit_C? U:I)* qubit_A;= qubit_B;= qubit_C; 逻辑与操作能不能做？利用如下这个简单的事实：
定理 5. 任意幺正算符是可以开根号的，即对于任意幺正算符 ，存在幺正算符 ，使得 。 我们就能实现这个想法，具体电路实现见下图。CNOT 门绕过来绕过去看上去好像挺麻烦的，但其实一个个情况分析就好。 Toffli 门，能够实现两控一的功能，其中 满足 ，作为幺正矩阵自然有 。 控制端00输入时，什么门都没有触发，不用管；01输入时，给受控位触发两个门，和效果为零；10输入时，二号控制位翻转，触发 ，自身再翻转，一号控制位触发 ，和效果为零；11输入时，二号控制位触发 ，翻转两次，一号控制位触发 ，最后总效果为一个 （在做这些讨论时，始终要记住我们是对一个一般的量子态进行操作，也就是说上面这些情况是可以相干地同时发生的。）。综上，我们实现了预期的功能。当 取做翻转门 时，我们一般将其称为 Toffli 门。 进一步的，能不能实现 控 的操作？答案自然是肯定的。推广方案有很多种，下图给出了一种递归的办法，尽管并不是最优的（事实上，这有着指数级别的复杂度）。 推广后的 Toffli 门，三控一的情形。通过与之前的图的比对很容易断言其正确性。推广到更高阶的情形是很直接的。通过引入一个辅助 qubit 的办法可以将复杂度降低至 ，复杂度的含义是作为基本单元的门所使用的数量。又，量子体系中的辅助 qubit 和经典中一个辅助变量区别很大：一个辅助 qubit 能将体系的维度增大一倍。 五、由量子门电路到任意幺正演化 有了一些组合量子门电路，我们就可以考虑如何执行一些真正有意思的量子操作了。最简单的，我想给某一个特定的基（请注意一个基底与一个量子位之间的区别，它和直和与直积的区别相对应。），比如说 ，添加一个相位 ，怎么办？使用一个五控一的控制门就成。 如下图左所示，图中 。容易看出，通过翻转选出前五个位的态，矩阵再选出最后一个位的态，最后就是只给一个态添了相位而其他态没动。 单分量的精确控制。一般会将此类图简记为右图。
然后,如定理2所述,我们需要实现任意二维幺正变换。在 |0⟩ 和 |1⟩ 张成的子空间中（或者,我们谈论 |0010011 . . .⟩ 和 |1010011 . . .⟩ 张成的子空间）作变换显然是可行的,这就是一个单 qubit 门(或控制门)嘛。那么更复杂一点， |00⟩ 和 |11⟩ 呢?自然是设法将其化归成已经解决的问题。 我们来看上图,基矢 |11⟩ , |01⟩ , |10⟩ , |00⟩ 经过第一个 CNOT 门之后会分别变成|10⟩ , |01⟩ , |11⟩ , |00⟩;好的,我们发现想要变换的两个基已经被塞到一个 qubit 位上面了(成了 |10⟩ 和 |00⟩,只有第一位不同),这个时候就能用一个控制门做完变换；最后再用一个 CNOT 门把基底转回来就成。|01⟩ , |10⟩ 作基的情况是类似的。 更一般的,变换子空间的两个基有 m 个位都不同怎么办?自然还是递归,用CNOT 门一阶一阶的将 m 减小至 0,作一个变换,再转回来就完事。具体的操作我不在此给出。 六、总结与讨论 综上，我们大致算是了解了如何执行一个任意的幺正操作。但是，这仅仅是告诉了我们，量子计算机能算数。而至于量子计算机能不能算得多快好省，本文并没有给出答案。按照定理 1 给出 来看，情况不容乐观，作用在 个 qubit 上的任意幺正操作至多需要个量子门操作来实现！还好，我们所面临的问题大都具有其特殊性，而充分某些特殊性，即能够大大简化所需量子门操作的数目。人们针对傅里叶变换 [5] 、(无结构集合中的)搜寻问题 [6] 和大质因数分解 [7] 都开发出了远优于经典算法的量子算法。 另一个值得注意的点是，我们在讨论上面诸多门电路的时候，都有着不该变的就不能变——不该变的变了可不是浪费掉一个 qubit 的问题，由于全部 qubit 一般都处于一个大的纠缠态上，丢掉一个东西会导致剩下体系发生退相干，进而使量子计算机退出工作状态。在使用辅助 qubit 时这也是一个要注意的问题：辅助 qubit 进来是什么样，出去必须还得是什么样，否则一旦纠缠起来就要废。 上面这段意味着我们不能在计算过程中对哪个量子位作信息擦除，再结合所有量子门（幺正变换）都是可逆的这一事实，我们可以发现，从热力学原理上限制经典计算机能耗极限的兰道尔原理，不作用于量子计算机上（这一可逆计算机，初态制备和末态测量除外）！ 参考文献： [1] Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information. Cambridge University Press, September 2000. [2] 张永德. 量子信息物理原理. 科学出版社, December 2008. [3] D. Deutsch. Quantum Theory, the Church-Turing Principle and the Universal Quantum Computer. Proceedings of the Royal Society of London A: Mathematical, Physical and Engineering Sciences, 400(1818):97–117, July 1985. [4] D. Maslov and G. W. Dueck. Improved quantum cost for n-bit Toffoli gates. Electronics Letters, 39(25):1790–1791, December 2003. [5] Artur Ekert and Richard Jozsa. Quantum computation and Shor’s factoring algorithm. Reviews of Modern Physics, 68(3):733–753, July 1996. [6] Lov K. Grover. Quantum Mechanics Helps in Searching for a Needle in a Haystack. Physical Review Letters, 79(2):325–328, July 1997. [7] Peter W. Shor. Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. arXiv:quant-ph/9508027, August 1995. arXiv: quant-ph/9508027. 附录：绘图时所使用的 Mathematica 代码 预定义函数：
Toffli[source_, target_,
具体绘图（仅举一例）：
t = 6;
