“九章”刷屏的背后：万字长文解析量子计算机和电子计算机各有何优劣？

　　12月4日，中国科学技术大学潘建伟研究团队与中科院上海微系统所、国家并行计算机工程技术研究中心合作，成功构建了 76 个光子 100 个模式的高斯玻色取样量子计算原型机「九章」，其处理特定问题的速度比目前最快的超级计算机「富岳」快了一百万亿倍。相关论文登上了国际顶级期刊《Science》杂志，引发学界、业界热议。

　　近日，中科大校友、UC伯克利在读博士、知乎用户@SIY.Z 在一篇近两万字的长文中，详细分析了“量子计算机和传统电子计算机在算法方面的优劣势”。以下是原文内容:

　　这是一篇我很早以前就想写的文章。我的目的是给稍有数学等基础的人，比较全面客观地介绍量子计算和经典计算在算法上的优劣势，而且会涉及到方方面面，可以说是一个大杂烩。我觉得我是有资格做这件事的，因为 1. 我本人就是计算机科班出身的，对计算机系统以及机器学习都有较为深刻的理解 2. 我本科参与过第一线. 我个人对多个学科都有涉猎，因此可以不至于错的离谱地谈论一些实际应用问题。但是哪怕仅仅接触到最表面的一些问题，如果要解释清楚，都要花费巨大的精力去解释；此外，即使我写了这样一篇文章，可能也少有人关注，毕竟吧宣传知识本身在知乎上可能已经过时了，渲染情绪要容易的多，而且可以天天输出。所以说，我写这篇文章，也是靠了 “九章” 量子计算机的热度，这让我稍微有动力一些。

　　算法研究是一个非常非常复杂艰深的领域，特别是我需要横跨量子和经典两大部分，而且涉及到的应用涵盖了组合优化，密码学，生物学，科学计算，理论计算机等各个领域，以个人水平很难涵盖完整。而且考虑到受众，我有必要模糊化和简化一些概念，而只保证核心思想是正确的。因此如果过程中有差错，请多多包涵。

　　对于大部分日常问题，我们不需要算法，直接按照直觉去做就行了。然而对于一个稍微复杂的问题，它的解决方案就不是那么简单直接，往往需要一系列步骤。简单来说，描述一个问题解决方案的步骤，就是算法。给定一个问题的算法，你就可以一步步的按照算法解决所有的类似的问题。其实生活中最明显的算法的例子是说明书，它告诉你如何一步步地去按照说明书去完成一个功能，比如说如何安装一个软件，如何启动一个电器，等等。

　　如果只是考虑到这一步，算法本身并没有什么魅力。其实在生活中算法往往被视作 “机械、死板” 的代名词。为什么？

　　人执行算法的能力是非常有限的。哪怕对于一个固定的算法，人也需要大量的练习才能熟练解决问题，而这个过程并不有趣，长年按照 “算法” 去组装元件的流水线的工人应该深有体会。

　　人执行算法的准确性很低。比如 DIY 一个玩具，如果说明书只有 10 行，那么大多数人还是很自信的；如果发现说明书竟然要 100 多步，那么很多人组装结束后，如果发现结果不对，会首先怀疑自己中间操作错了。

　　记忆算法很困难。很多人玩过带 “秘籍” 的魔方，可以按照说明书上的算法去慢慢还原魔方。但是一旦离开说明书，很多人就难以自己操作：这些算法需要一定的精力去记忆，而且熟练度很大程度上取决于记忆的难度。极其复杂的算法的对人来说首要挑战是记忆，而不是操作。

　　算法描述的不精确性。说明书中的每一句话，因为自然语言本身的缺陷和场景的复杂性，都容易产生歧义。由说明书产生的困惑是人类共有的体验。

　　由于以上这些问题，在历史长河中，算法并不是科技和生产力的核心问题。虽然算法可能启发来巴贝奇等人发明差分机，但是这并没有扭转历史格局。直到 1936 年，一位英国的计算机学家，数学家，逻辑学家，密码分析家兼理论生物学家，世界级长跑运动员在数学上证实了一个无比强大的机器的存在。在他生后，计算机科学的最高成就会以他的名字命名。

　　这个机器的输入的格式是有限的，这个机器可以执行的操作也是有限的。所以在现实中你可以用有限的零件制造它。

　　需要构成这个机器的基本操作都是非常简单的，而且只需要固定的时间就可以完成。

　　这个机器是万能的。只要你能够用逻辑和数学描述一个算法，它就能自动执行它。

　　没有任何一种机器在使用算法解决问题上比它更加强大。如果一个问题它不能解决，那么其他机器也一定不能解决。

　　1936 年前后，阿兰 · 图灵（Alan Turing）构造式地证明了这样一种机器的存在

　　下面是一种更加简单，但是更加接近现代计算机的一种图灵机构造（而不是最初的 “纸带” 版本），我们在之后会多次提到它：

　　不过，阿兰 · 图灵发明这台机器最初的动机并非来自于算法，而是为了解决逻辑学和数学问题，特别是数论公理化和数理逻辑等最根本的数学问题。当时和他在一个圈子里面的人是希尔伯特，哥德尔，邱奇等人，因此整篇论文充满了逻辑学的风格。这也让图灵机在最初并没有很快走出圈外，为公众所知。在二战期间，图灵将大部分精力投入到了破译纳粹的密码中，并获得了巨大成功。

　　然而，随后人们发现，图灵机并不仅仅是一个数学玩具，它是执行算法的最理想的万能机器。我们来看图灵机为何如此适合算法：上文中提到了人类自己执行算法的缺陷，其中人执行算法的能力和准确性问题并不适用于机器，机器不会疲劳，不会出错，不会有负面情绪；而算法的记忆问题，在图灵机中只要把算法转换成一串符号，写入到中就可以了，自然也没有问题；而算法描述的不精确性也是不存在的，在图灵机中算法就是一堆符号决定的，严格按照来执行，不存在不准确。

　　其中对于 “可计算性” 问题的研究，回答了问题 1 中的一些重要问题。人们知道一些经典问题，比如“任意图灵机的停机问题”，是不能被图灵机解决的。

　　对于问题 2，算法设计也有了长足的发展，成为计算机科学的重要领域。本文中会继续扩展这一段。图灵机的出现改变了算法和机器的关系：从前人们希望为算法找到一个机器，而现在人们为了机器设计算法。

　　现代编译原理，程序语言设计和软件工程解决了问题 3。这部分仍然在不断进步。

　　图灵机从数学模型到具体应用的道路上，一个重要的节点是 “通用计算机” 这种思维的兴起。早在 1937 年，图灵就意识到因为图灵机的强大特性，一台图灵机可以同时模拟一台甚至多台图灵机（现在最直接的应用就是虚拟机）。图灵等将这种模型称为“通用图灵机”，或者“通用计算机”。但是当时人们只是把它当作一个有趣特性，并不是特别在意：毕竟模拟另外一台图灵机并不会加快解决问题的速度，只能做理论分析时用一用；而且它只是一种概念，在具体的实现上并不会和图灵机有区别。

　　所以 1946 年制造的第一个电子计算机——ENIAC，仍然 “忠实” 地按照图灵机的方式执行：对于每一个算法，首先去拨动一堆开关设置好，也就是计算机的“内存”；然后启动机器，等到停机时再读取结果。

　　然而在 1946 年，就是 ENIAC 诞生的同一年，冯诺伊曼领悟到了 “通用计算机” 真正的意义，并发表了奠定现代计算机体系结构和软硬件生态的一篇论文：

　　冯诺伊曼关于电子计算机的论文，其中提到了 “存储程序计算机” 和“通用计算机“的概念

　　冯诺伊曼想到，既然通用图灵机，或者通用计算机可以模拟任意一个图灵机，而每个图灵机都可以执行任意的算法，那么是不是意味着，我可以将所有的算法都放在同一个图灵机里面，然后用另外一个算法，或者是操作员，去选择我要具体执行哪个算法？这样一来，我就可以将所有的算法都预先准备好，然后需要时直接选择这个算法运行就可以了，而不用像 ENIAC 一样每次都要重新设置所有的开关。

　　冯诺伊曼的这种想法非常简单，也许很多人在他之前就想到了。但是冯诺伊曼意识到这样可以更进一步：写算法的人和机器的分离。我只要给机器写一个说明书，168体育告诉大家这台机器所有支持的 “操作”（称为“指令集”），以及每个指令对应的符号编码（称为“机器码”），这样大家就只要用这些指令去描述算法（由于是图灵机，必然可以用这些指令的组合描述所有的算法），然后把指令一个个翻译成机器码，刻录到纸带上。冯诺伊曼把这种纸带上的内容称为“程序”。这些纸带可以远程寄给计算机操作员，然后每次执行前，就用另一个“转录” 程序把纸带上的内容写到计算机的内存里面，再用一个 “启动” 程序去执行这段程序，最后再用一个 “输出” 程序把结果打印出来，寄回给原来写程序的人。

　　冯诺伊曼称这种这种通用计算机为“存储程序计算机”，同时这种计算机的出现导致了一个新的职业的出现——程序员。有趣的是，最早的程序员更多的是女性，可能是当时的人觉得女性更加耐心，而刻纸带在固有印象中更像是“编织”。

　　如何将图灵机 / 通用计算机的数学概念变成一个真实的机器呢？对应图灵机的数学概念，我们需要状态的集，符号的集合，列表和函数的物理实现。

　　冯诺伊曼等很快意识到，无论是状态还是符号，在本质上都是状态。由于符号是有限的我们可以将每个符号一一映射到不同的状态上。而符号的列表，只是把一堆状态组合到一起罢了。

　　现实中的物理状态正好符合我们的要求——比如电压的高和电压的低就对应了两个状态。因为它们的物理特性不同我们可以区分两个状态。同时我们有电子元件，可以在两个状态之间任意转化。我们将两个物理状态称为 0 和 1，这种基本单元也称为“比特（bit）”

　　同时冯诺伊曼等人发现，只要最基本的 0 和 1，我们可以构造出越来越多的状态，而这些状态依然满足我们要求，而方法很简单，就是将更多的 0 和 1 组合起来：比如 00，01，10，11 就是满足我们要求的 4 个状态，总之个比特就能够表示个状态。这样要求 1 和 2 就满足了。但是我们如何控制这么多状态呢？

　　答案是 “组合逻辑” 这种技术。组合逻辑中，有一个特殊的 “元件” 叫 NAND 门（“门”这个词出自于电路）。如果输入状态是 00，01，10，11，那么输出就分别是 1，1，1，0。这也称为 NAND 的真值表。此外还有一个没什么存在感的东西：复制，也就是把输入复制成任意多份，在电路中就是一根导线分成两根。不要小看复制，这是一个非常重要的操作，我们在之后可以看到，在量子力学中，一般的复制竟然是禁止的，这导致了量子计算机和经典计算机的重要差异。

　　然后组合逻辑的一个重要结论是：只要有 NAND，而且可以任意复制，那么我们可以实现任意多比特作为输入的任意变换。这里举一个简单的例子：取反操作，也就是将 0 变成 1，将 1 变成 0。对于一个输入 x，首先我们将它复制一份，然后将两个 x 都输入到 NAND 中，我就可以实现取反。通过 NAND 的真值表很容易验证这一点。

　　有了组合逻辑之后，给定一个图灵机中的函数，我们就能实现它，无论它多么复杂。在硬件实现上，本质上是利用物理模型的演化规则来控制物理状态（比如晶体管是通过固体物理的一些原理，控制电路的电压电流，从而控制每个比特的状态是 0 还是 1）。

　　好了，我们终于搞定了状态的问题，下面就容易多了：我们只要将图灵机的各个部分变成各个部件，就能够给出一个完整的设计图了：

　　这个设计又称为冯诺伊曼体系结构。其中内存单元（Memory Unit）对应了图灵机的， 每一个都对应了独立的一些比特；中央处理器（CPU，Central Processing Unit）对应了状态和函数。又具体细化为改变的控制单元（Control Unit）和改变的计算 / 逻辑单元（Arithmetic/Logic Unit）；这些单元都可以由组合逻辑实现，而都是一些比特组成的。此外，为了实现冯诺伊曼“存储程序计算机” 的想法，计算机需要输入设备和输出设备，这样我们可以通过输入设备将程序写入到内存单元中，将结果从内存单元输出到输出设备。

　　冯诺伊曼体系结构奠定了现代计算机体系结构的基础，沿用至今。不过，当今计算机做了一些优化，比如说不再区分和，而且它们的数量有多个，称为 “通用寄存器组”。而所含的比特数，称为计算机的“位数”，基于不同的的位数的程序 / 操作系统被称为 xx 位程序 / xx 位操作系统（比如 32 位和 64 位程序）。此外，由于 memory 操作慢于逻辑和运算，现代计算机中的“Memory Unit” 是分级的，CPU 拥有自己的容量更小，但是操作更快的 memory unit，称为“缓存”（Cache），而在 CPU 之外有着一块容量更大，但是操作更慢的 memory unit，这才是现在我们所指的“内存”。现代计算机中的优化要比绝大多数人所想的复制的多，需要系统学习才能全部掌握，限于篇幅我不就不再继续扩展了。

　　在上一节中，我们大概了解了如何在物理世界中制造通用计算机。我们的途径是：

　　在物理模型中找到一个基本的物理状态。确保这个物理状态可以通过组合产生任意大的状态。

　　在电子计算机中，物理模型的演化规则是基于固体物理的，固体物理中研究了半导体等的能带问题，本质上还是基于量子力学；我们甚至可以说，现代电子计算机就是基于量子力学的，量子力学已经给计算机带来了巨大的革命。

　　那么，又是什么东西使得其他计算机机真正区别于 “电子计算机” 呢？答案是状态！

　　生物计算机使用 DNA 和其他化学物质表示状态，用酶和其他化学物质控制状态。

　　量子计算机使用 “量子叠加态” 表示状态，用固体物理 / 光学元件 / 光学共振腔等控制状态。

　　生物计算机等的概念大家应该很久前就听过，但是为何现在主流的还是电子计算机？本质上是因为它们的状态并没有给它们带来根本性的优势，相比而言，电子计算机基于晶体管的设计倒是有极大的优势：

　　极高的内部元件集成度。这意味着可以在极小的空间内实现功能。这对硬件运行速度有很大优势。现代电子元件的主频可以达到 5GHz，也就是每秒钟至少可以进行 50 亿次操作，即使按照真空中的光速，每次操作控制信号只能走 6 厘米，何况任何物理体系内控制信号都无法始终以真空光速传播，且整个路径不一定是直线 个 CPU 的高端服务器上已经可以感受到光速的限制（这个例子并不确切，但是背后的原因是类似的）：由于内存一般紧贴每个 CPU，所有对每个 CPU 而言，对方 CPU 的内存要离自己更远一点；而离每个 CPU 较近的内存访问要比较远的内存访问更快，称为 NUMA（非对称内存访问），这是高性能计算软件优化的重点之一。

　　有 2 个 CPU 的高端服务器主板。可以看到每个 CPU 旁边有紧贴有 4 个内存槽。每个 CPU 访问它旁边的内存，要快于访问另一个 CPU 的内存。

　　2. 极高的可扩展性。基于电信号和光电转换，电子计算机可以轻易组网。现在全世界计算机都在互联网上，已经不足为奇了。对于高性能计算等领域，可以使用内部的高速网络将大量电子计算机互相连接起来，从而成倍地增加运算速度，实现高效的并行计算，这类计算机也被称为“超级计算机”。对于其他类型的计算机我们尚不知道怎么大规模扩展。

　　3. 极高的稳定性。从零下到接近 80 度，电子计算机都可以长期稳定运行。而且自从机械硬盘被替换为固态硬盘后，电子计算机内除了散热风扇以外再也没有活动的部件，因而抗震抗摔性能卓越，可以应用到军事或者卫星等极端环境中。可以说如果现在你摔一部手机，首先坏的是它的光学部分（屏幕，摄像头），而不是它的电学部分。这些对生物计算机等是噩梦。

　　4. 电学状态总体上是容易控制的。首先电学设备的能源很容易获得和保存，生物计算机就要麻烦不少；其次电学设备的控制可以依赖电本身，而光学计算机中让光控制光就很困难，因为绝大多数情况下两束光都会直接穿过对方，因此可能需要非线性晶体，而非线性晶体很难做到晶体管类似的控制精度；如果要通过干涉控制光，就需要相干光，而相干光的控制和维持比电路要复杂地多，而且光还存在衰减问题。至于生化反应的控制。。。emmm，甚至有的时候还处于玄学范围。

　　5. 电路甚至可以给自己编程。在制造 CPU 前，为了验证是否能够正常工作，除了软件仿真外，还会进行硬件仿真。其中有种特殊设备叫 FPGA，就可以来更加精确地模拟硬件。FPGA 本身就是个电路，但是它支持向它写入控制代码，改变内部电路在运行时的“连接”，这是真正改变了内部电路，而不是软件模拟。最近微软还有 Intel 等已经将 FPGA 集成在主板还有网卡上，这样一个软件可以在运行时向 FPGA 写入控制码，让它成为一个专用硬件，从而大大提高处理效率。

　　既然如此，为何量子计算机那么受人重视呢？这是因为，和生物计算机等不同，量子计算机使用量子叠加态作为状态，在加速方面有根本性的提升。这甚至导致人们将所有不利用量子叠加态作为状态的计算机都称为“经典计算机”，以区别于量子计算机。

　　在引入量子力学之前，我们先幻想一个更加简单的物理学模型。通过这个物理学模型，我们会发现我们能够制造更快的计算机。

　　在经典计算机中，我们基于的状态是 “经典物理学” 的状态，比如电压，电流等等。这些 “经典物理学” 的状态有一个特点：它们都是用数字表示的。实际上，我们可以测量到的所有物理量或者物理状态都是数字：长度，速度，质量，能量，体积，辐射强度等等等等。但是你是否想过，会不会可观察到的状态只是真正的物理状态的冰山一角？

　　这并不是我在说“有一条看不见摸不着的大龙在我的车库里”，168体育而是说有一些不能直接观察到的东西，会导致不同的物理效应。一个类似的例子是 X 射线：X 射线并不能被直接看到，但是不意味着它不存在，因为它可以产生让胶卷感光这种物理效应；不过确实因为 X 射线不能被直接看到，导致人们很久之后才发现它并研究它的规律。

　　同样地，也许真正的物理状态并不能被直接测量到，但是它的效应是改变物理事件发生的概率，最终会改变你观察到的状态，甚至能展现出磁性，超导性等宏观特性。这时候你观察的工具就是“不断制造相同的状态，然后用统计学估计概率”。这实际上就是量子力学的核心所在。一个经典的例子是单光子双缝干涉（知乎上有非常多相关的内容），通过不断重复产生相同的状态（一个通过双缝的光子），你可以在对面屏幕上清楚地看到干涉条纹，这个条纹清晰地反应了这些光子的状态——如果你改变光的波长，或者双缝的宽度，这些干涉条纹就会改变，因为光子的状态改变了。但是，你却无法通过观测某个光子来获得它的状态，如果你试图单独观测每个光子，干涉条纹就会消失。然而，你却不能因为观测单个光子，发现没有观测到“光子的状态是同时从两个缝中射出这种状态”，而认为这个状态不存在，因为你可以用统计学方法确认这种状态改变了光子的分布。

　　特别在量子力学中，物理状态被称为“量子叠加态”，或者简称“量子态”。不过我首先不介绍更多的物理学概念，而是用一个类似但是更加简单的幻想的物理状态，来向读者展示为啥不同的物理状态会加速计算机执行算法。

　　注意到我一直提的是 “加速”，而不是“超越” 经典计算机。因为在理论计算机中，“超越”更偏向于指做到图灵机做不到的事情，也就是解决一些原本即使给予图灵机无限长的时间，无限大的内存，也不可能解决的问题。这类模型称为“超计算”。那么在现实物理世界中，是否可以实现超计算呢？目前的答案是否定的，因为目前已知的超计算都要一些变态的条件，比如将一个永远不会坏的无限大内存的计算机扔到一个永远存在的虫洞里面永远地进行时间回溯，这样计算机经过的永恒的时间对于我们来说就是一瞬间，于是就有可能做到原来无法做到的事情。图灵本人对超计算是否定的，他和邱奇有以下论题：

　　所以按照这个理念，人属于宇宙的一部分，那么人自然也可以被计算机模拟，那么计算机当然可以拥有人的智能。所以图灵后来提出 “人工智能” 这个概念，也不出意外。当然这也成为了很多科幻小说和哲学问题的来源：我们这个宇宙本身会不会只是计算机的一个模拟？

　　这个物理模型中，物理状态都是由向量而不是数表示。我们可以用固定的时间构造任何我们想要的任何元素个数的向量。

　　这个物理模型中，你可以用固定时间构造一个矩阵。这个世界遵循这样的物理演化规则：你可以用这个矩阵乘这个向量得到一个新的向量，这个新的向量就是新的物理状态。并且，这个操作用固定时间就可以完成（现实世界中需要和矩阵元素一样多次乘法操作）。

　　首先我们证明利用这个物理模型构造通用计算机，其运行速度不会低于经典计算机：

　　1、经典计算机中的任意一个状态，或者二进制串，都可以对应到一个向量：比如

　　这些都是正交的单位向量，且一个元素个数为的二进制串对应了一个元素个数为的向量。有自然语言处理（NLP）经验的应该感到很熟悉，这其实就是 one-hot encoding。

　　2、经典计算机中任意一个组合逻辑，都可以对应到一个矩阵。这个很显然，由于状态都是单位基向量，所以只要往矩阵对应的位置填上 1，就可以实现所有的功能。比如 NAND 对应的矩阵：。

　　由于只有右下角有一个 1，所以只有作为列向量相乘才会输出。用类似的方法可以表示任何一个组合逻辑。

　　其次，我们证明这个计算机可以指数快的加速求解一类问题，比如单一结果的无结构搜索问题，而经典计算机做不到。单一结果的无结构搜索问题的表述是：对于输入，其中都是如同之前描述的单位正交向量，我们有一个算法，可以用固定的时间告诉我的结果是 0 还是 1。并且已知所有的中，有且只有一个。求解的具体值。这个问题在现实中对应的问题之一是密码破解：对于固定长度的密码，我们可以去一个个尝试密码是否正确，但是我们只知道只有一个密码是正确的。对于经典计算机，几乎唯一的方法是一个个去试。假设密码由个 bit 构成，那么密码的总数量就是，比如常用的 256 位 AES 密码的总数量就有 936 个，用经典计算机去暴力破解是不可行的。但是注意到，我们这个利用虚拟物理构建的计算机的输入是向量，中间的规则是矩阵。首先我们定义函数然后我们就可以利用分配率来同时计算所有情况：

　　根据我们的物理模型，是可以常数时间构造的，所以对于总数量的密码，我们只要常数时间就可以破解，相对于经典计算机平均需要次，快了指数倍。

　　幸好上文的计算机是用我们宇宙不存在的物理模型制造的，否则任何密码在一瞬间就会被破解了。不过，上文幻想的物理规律是去除了一些 “限制” 的量子力学，如果它发生在我们的宇宙中，会出现无数反常的情况，比如严重违背热力学定律。这个模型实际上是 Scott Aaronson 于 2005 年提出的一个模型的简化版本，原来的模型用于显示只要对量子力学做轻微的修改，就能大大增强量子计算机的计算能力，不过这些修改只是存在理论中，与物理实验不符。

　　在量子力学的框架中，我们对之前的模型加入了以下约束（读者没有必要完全了解）：

　　物理状态的约束：量子态向量的模长固定为 1。也就是只有向量的方向是重要的，你无法使用它的 “长度” 做任何计算。

　　状态制备 / 初始状态的约束：我们仅能够使用步准备一个元素个数为的 one-hot 量子态。这一般作为算法的最初输入。one-hot 即整个向量中，只有一个系数是 1，其他均为 0。

　　演化的约束：从一个量子态到另一个量子态的演化对应的矩阵必须是幺正的（幺正演化），不改变向量的模长。也就是唯一可以对向量进行的操作是“旋转”。所有的幺正演化都是可逆的矩阵。

　　读出的约束：读出结果只能通过 “观测” 完成。根据量子力学的观测公理，一个算法输出的结果只能是一个 one-hot 量子态。得到某个 one-hot 量子态的概率为这个 one-hot 量子态在原来向量中的系数的平方（严格来说是模平方，因为系数可以是复数）。

　　在量子力学的限制下，我们利用量子态来构造的计算机的加速能力也会相应受到限制。比如说，上文的“单一结果的无结构搜索问题”，量子计算机最多可以带来平方的加速，也就是著名的 Grover 算法。Grover 算法显示了量子计算机优势的同时，也被认为显示了量子计算机的局限性。所以量子计算机其实并不能像很多人想象一样，轻松破解所有的密码，AES 等加密方案面对量子计算机是安全的；不过之后我们会谈到，RSA 等加密方案在未来可能因为量子计算机变得不安全。

　　如果我们使用量子态为基础去构造图灵机，用某个 “幺正演化” 构造转移函数，那么我们我们就实现了量子图灵机，或者是量子通用计算机（和之前一样，两者主要是概念上的区别）。我们可以证明的是，不会有一种量子计算机，比量子图灵机 / 通用量子计算机更加“强大”，比如可以解决通用量子图灵机不能解决的问题；此外通用量子计算机甚至可以高效模拟任何量子力学过程。量子通用计算机是一些量子算法的预设，但是我们离物理上实现它还差的很远。

　　在上文中，我们使用 “幺正演化” 构造转移函数，实现了量子图灵机。但是在实现中，可能是极其复杂的。在经典计算机的例子中，我们知道我们可以把状态分解为一串比特，而状态的转变可以用组合逻辑表示，任意组合逻辑又可以用 NAND 门和 “复制” 来实现。那么我们可否在量子力学中构造类似的东西呢？

　　首先，量子力学中，一个 one-hot 量子态在物理上可以分解为一个个独立的，只有 2 个基的向量，而它们可以有独立的物理载体（比如每个对应一个光子，或者超导约瑟夫森结，或者一个冷原子）。类比于经典的比特，我们称它们为“量子比特”。作用在量子比特上的操作称为“量子门”。

　　那么 “幺正演化” 是否可以由一些简单的 “量子门” 来构成呢？答案是无法用有限的量子门来组成任意的幺正演化，但是如果只要求是近似，是可以的。一般认为 H，S，T，，CNOT 这几个量子门就足够了。其中 H，S，T，都是作用到一个量子比特上，而 CNOT 是唯一一个作用到两个量子比特上的操作，也是现实中最难实现的操作。

　　此外量子线路的一个特殊操作是测量，根据量子力学的公设，（简单地说）测量会导致量子态变成一个 one-hot encoding 的量子态，我们可以将这种量子态对应到经典的比特上，用于控制一些量子门（比如 1 对应使用量子门，0 对应不使用量子门）。下图展示了一个典型的量子线路：

　　由于任何一个量子线路都可以被通用量子计算机等效地执行，而通用量子计算机依然离我们很远，所以很多量子算法都只是用量子线路来描述的，而这些算法在真正的物理实现上也是类似量子线路的形式。之前 Google 的超导量子计算机和现在的“九章”，都更接近量子线路（甚至它们比一般的量子线路都特殊得多），而不是通用量子计算机。当我们能够制造出一个类似 FPGA（上文提到过 FPGA）一样的设备，可以任意编写大规模（比如大于 100,000 个可靠的量子门）的量子线路时，我们离通用量子计算机就近了。

　　这一章节中，我将反复使用的一个词是 “fineprint（细小的条款）”。这也是一些量子计算研究者会用的词，因为在讨论量子算法时，经常有一些微妙的差别，从而导致完全不同的结果。

　　类似经典算法，量子算法通过对量子状态进行一步步操作，进而解决问题。然而，不同于经典算法，量子算法的每一步，要不就是一个幺正操作，要不就是测量。这给编写量子算法带来了很大的困难。

　　最直接的困难就是，不允许对未知的一个状态进行复制（比如说算法输入的某个量子态，以及所有受到输入影响的状态；这里要顺便指出量子图灵机中的 “读取” 和“写入”也不是通过复制完成的，而是通过 “交换“或者” 观测 “等量子力学允许的方式实现）。这是“量子不可克隆定理” 限定的，本质上是幺正操作和测量无法复制未知的状态。这让很多经典算法设计思想很难应用到量子算法设计上。

　　如何利用量子态的性质来加速也是一个问题，因为如果设计出来的算法没有明显超过经典算法，那么在解决问题上是没有意义的。如果使用经典的算法设计思想，是很难造出超过经典算法的量子算法的。

　　输入输出问题。如果输入输出是某个特定的 “量子态”，那么设计一些量子算法会变得相当容易，但是现实世界无法去直接利用量子态（因为量子力学根本上阻止我们直接观测它们）。因此如何从经典比特构造出想要的“量子态”，以及如何保证最终将“量子态” 通过观测变成想要的经典比特，是一个烦。

　　在仅有的一些量子算法中，相当多的算法（特别是远远优于经典算法的一些）的共同特点是使用了 QFFT （量子快速傅立叶变换）。这是 Shor 算法以及 HHL 算法的基础。

　　快速傅立叶变换本身就是一个相当重要的数值算法，它可以快速地分析出数据中的周期，在时域和频域之间转换，并可以加速卷积等操作。

　　这 3 个重要特性让人立刻意识到，快速傅立叶变换和逆变换都对应量子力学中的幺正变换。然后，这个幺正变换可以用含有个量子门的量子线路描述！而我们只需要个量子比特就可以构成元素个数为的输入向量。而经典算法中，用电路对一个元素个数为 N 的向量进行快速傅立叶变换，电路深度为，这意味着，量子算法对经典算法在 FFT 上有指数加速。

　　不过不要高兴得太早，这里有一个 fineprint（细小的条款）：量子算法中的 “向量” 是量子比特构成的量子态，和用比特构成的数值的向量是两回事。也就是这个量子算法操作的对象是量子态对应的向量的系数，因而只要个量子比特；而经典算法中每一个系数都是都是实实在在的用比特表示的数字。也就是，根据量子力学的基本原理，我们没有任何办法，直接写入或者读取这些系数。而且我们甚至没有已知有效方法将任何经典算法中一个向量，转变成量子态向量的系数，因而 QFFT 并不能加速 FFT。

　　QFFT 的输出结果的几乎唯一的一个用途，就是如果输出的向量的系数中，有一个系数相对其他的系数特别大，那么我们对这个向量进行观测后，就会以很大概率获得这个系数对应的 one-hot encoding，而这个 one-hot encoding 直接对应了一个经典的比特串。但是，正是这个用途，让很多算法得到了巨大的加速。

　　这些算法的共同特点是：1. 输入的量子态比较容易构造 2.输入 QFFT 的向量中有一个明显的“周期”，QFFT 变换到频率领域后，对应的频率的系数很大，因而我们最终能以较大概率得知这个周期是什么。我们之后可以看到，这成为了 Shor 攻破 RSA 加密算法的关键（当然前提是有一个可以跑 Shor 算法的量子计算机，就目前拥有的信息还早的很）。

　　Shor 算法显示，量子计算机可以指数加速 “分解大质因数” 这个问题，从而对 RSA 这种非对称加密算法构成威胁。在《夏日大作战》中，主角读了 Shor 算法后破解了 RSA 加密，造成了一次互联网危机（其实人脑按照 Shor 算法去分解 21=3*7，可能比刷一整页《吉米多维奇》的不定积分花的时间还要长）。

　　首先简要介绍一下非对称加密。非对称加密是指一类加密和解密密钥并不相同的加密算法，这两个密钥分别称为 “公钥” 和“私钥”，且经典计算机中根据公钥计算出私钥是困难的。非对称加密可以做非常多对称加密（用同一个密钥加密解密）无法完成的事情，比如向任何一个人证明自己的身份（也就是私钥的拥有者）：首先你向全世界公开你的身份 A，A 可以是一个虚拟身份，你的公钥是 p。由于之前不存在一个是 A 的人，所以大家都知道 A 这个身份就和公钥 p 绑定了。然后某次交易中，对方需要确认你的身份是 A，对方可以用你公开的公钥 p 加密一个随机的无法猜出的文本，由于只有你拥有私钥 q，所以只有你可以很快地解密内容发送回去，这样对方就知道你确实是 A。现实中的一个最常用的应用就是网络安全。如果网站的地址包括“https”，那么这个网站就实现了 SSL 协议，这个协议可以让你验证这个网站是否是真实的：在 CA，操作系统以及浏览器的共同作用下，你本地存放有对应的网址的公钥，你就可以通过上述方法去验证这个网站的身份；如果有人通过攻击改变了这个网址对应的网站，比如说劫持居民的光纤，由于攻击者没有私钥，你会发现对方无法证实身份，这样就可以及时终止交易，避免泄露个人信息。注意到，对称加密是无法解决这种问题的：你不能将可以解密的密钥给用户，因为这个是你的身份的“证明”，而对称加密中，加密解密使用同样一个密钥，所以无法工作。

　　在上述协议中，如果有人可以用很小的代价从公钥推导出私钥，那么后果将是灾难性的。特别地，对于 RSA 这种非对称加密算法，如果你有高效解决 “大质因数分解” 问题的算法，就可以高效地从公钥推导出私钥。

　　Shor 算法就是一种高效的分解大质因数的算法。大质因数分解问题的陈述如下：

　　在数论中，我们有这样一个问题：是待分解的一个大数。对于任何一个数，如果不是的因数（否则你就分解了），求解最小的正整数，使得(也就是 a 的 r 次方除以 N 余数是 1)。

　　通过数论可以证明如果解决了这个问题，就可以通过后续简单的步骤解决分解大质因数问题。

　　而很显然：是待分解的一个大数。对于任何一个数，如果不是的因数（否则你就分解了），定义，的最小周期就是。这是因为

　　而我们怎么求周期呢？既然是周期函数，一个简单的方法是对进行傅立叶变换，找出周期对应的频率。可惜现实中 FFT 算法对于这个问题实在是太慢了，而且即使我们进行了傅立叶变换，在这么大的范围内寻找周期，是不现实的。这个时候，我们的 QFFT 就有了用途了：首先构造出一个量子态向量，这个向量编码了对所有的计算结果。然后我们用 QFFT 对向量进行傅立叶分析，然后对输出的向量进行测量。由于傅立叶变换后周期对应的频率的 “系数” 比较大，那么量子测量后根据测量公设就会以很大概率得到周期对应的单位基向量，且错误率是一个有限的常数。这意味着不断重复这些步骤就可以以非常高的概率得到正确的周期，进而最终分解。

　　我们看到 Shor 算法成功的原因是根本原因是巧妙利用了周期特性，然后用 QFFT 求出周期。这个技巧可以用于构造破解所有现在大量使用的非对称加密算法，包括离散对数，椭圆曲线。由于这些算法都依赖于数论中的难题，因而都可以构造出类似的周期，从而被破解。

　　那么是否所有的非对称加密算法都可以被量子计算机破解呢？答案是否定的。Shor 算法在上个世纪公开以后，密码学界就开始研究新的一类非对称加密算法，称为“后量子密码学”，这些算法避开了数论难题，并基于格点，纠错编码，哈希函数等新的数学对象构造数学难题。目前尚未发现有高效解决这些问题的量子算法。由于新的数学难题会稍微增加加密解密的计算量，所以在量子通用计算机出现之前，尚未有主流网站用后量子加密算法取代 RSA。

　　通用计算机量子计算机被认为是必要的原因是，以目前的发展水平，实验中展示出的用 Shor 算法分解的最大的数是 21。而要破解现在通用的 RSA 算法，则需要分解一个大约 2048 位的数，也就是分解类似这样的数: 55

　　2.3 量子和经典算法的快慢，还是量子计算机和经典计算机的快慢？我们究竟在比较什么？

　　在我们最初的讨论中，我们是想比较量子计算和经典计算机的快慢。但是读者会发现，到这里时，似乎我们转向了讨论量子算法和经典算法的快慢。这两个东西是一样的吗？

　　首先，讨论机器本身的快慢实际上没有意义的，最终我们希望的是解决问题，因此比较的是“在经典计算机上解决问题的（最优）算法，和在量子计算机上解决同一个问题的（最优）算法的快慢”，简称为“算法的快慢”。

　　为了消除歧义性，我们首先需要定义什么是算法的“快慢”。算法有实际上的快慢，也就是生活中我们运行一个程序跑的时间，但是实际中的快慢是难以进行理论分析的：它受到的影响很多，比如硬件的价格和工艺，软件的编写质量，环境的温度，甚至是是否在运行过程中受到其他程序干扰。何况算法的目的是为了使用，我们往往在使用之前，甚至设计之前就需要知道它的快慢。

　　在这一章节中，我们希望理论分析算法的快慢，因为这才是对选用算法以及设计算法真正有用的东西。在理论分析中，算法的快慢定义为“图灵机执行的时间”，我们进而约定经典图灵机和量子图灵机执行一步的时间都是固定的，因此时间其实对应了图灵机执行的步数。在量子图灵机的每一步中，都可以对整个量子态，也就是整个向量进行操作，比如 QFFT 中的一个量子门；而经典图灵机却做不到：如果将这种向量和矩阵的乘法作为经典图灵机的一个操作，那么这步操作的时间就没有上限，因此不能称为“固定时间的操作”，所以这不能作为经典图灵机的一个基本操作。这样一来，经典图灵机中的算法就需要用更多步数实现向量和矩阵的乘法。因此，在有些算法中，量子图灵机可以充分利用自己的优势，设计出执行步数少得多的算法。所以在我们的理论分析中，解决同一个问题的最优算法的快慢就反映了量子图灵机和经典图灵机的相对优势：如果最优的量子算法快于经典算法，说明量子计算机本质上支持用更快的算法解决相同的问题，这就是量子计算机的优势。

　　然而，具体研究解决问题的算法时，我们发现大部分 “非平凡” 的问题会有一个参数，称为输入规模。比如快速傅立叶变换中的输入规模就是输入向量的元素个数，破解密码的规模是密码的长度。一般而言，规模和问题的输入占用经典计算机的比特数成正比。我们对算法进行分析后，会发现某个问题的最优算法的执行步数是输入规模数学表达式，比如快速傅立叶变换是。算法分析中，我们关心的是某个问题的最优算法的执行时间随着输入规模的变化趋势，我们可以根据变化趋势给问题分类，而我们将同一个类型的问题归入同一个集合。

　　显然，相同的问题，对于量子计算机和经典计算机，可能有不同的分类，这意味着量子计算机和经典计算机会将问题划分为不同的集合（下面所有的算法都默认是对应问题的最优算法）。

　　首先，我们可以定义一个集合 P，集合 P 包涵了所有的一类经典计算机的最优算法能够在输入规模的多项式时间（算法时间的表达式是一个多项式，或者比多项式增长更慢的项，比如 logN 等）内解决的问题。这类问题包括排序，快速傅立叶变换，求解两地直接的最短路径等等。P 内部的问题在理论分析中被认为是“容易的问题”。

　　另外我们可以定义一个集合 NP，集合 NP 包涵了所有的可以多项式内验证结果的问题。显然 P 是 NP 的子集，因为 P 问题可以通过再解一遍验证结果。如果 P 问题类似检查数学证明，那么 NP 类似于给出证明。关于 P 和 NP 有一个非常著名的数学难题：

　　虽然 P 是 NP 的子集，但是我们至今都没有证明它是真子集。大多数理论计算机学家都相信 P 不等于 NP，一是因为 “验证答案的难度和写出答案的难度一样” 过于违背直觉，二是因为人们发现了一个 NP 的子集，称为 NPC（NP-complete）。NPC 内部的问题有这样一个性质：如果其中任何一个问题被证明属于 P，那么 P = NP。NPC 内部有非常多有趣的问题，比如逻辑满足问题，定点着色问题，哈密顿回路问题，子图同构问题，但是若干年都没有任何一个人发现多项式时间解决它们的算法（就像找不到黎曼猜想的反例一样），这让大家愈加相信 P != NP。

　　此外，非常有趣的一点是，相当多和密码学相关的问题都属于 NP（RSA，离散对数，椭圆曲线），但是它们既不属于 P，也不属于 NPC。

　　如果我们更进一步，如果问题询问的是结果是 “真” 的结果的个数，且验证每一个结果所用的时间是多项式时间（相当于对一个证明题，我不仅要求一个证明，还要求得到所有不多于某个字数的所有的证明的个数），这些问题的集合称为 #P。显然 NP 是 #P 的一个子集，因为它至多只有一个结果为真，我们只要解决这一个问题就可以了。

　　经典算法中有一大类称为“随机算法”，这些算法的执行有随机性，不一定每次都能给出正确结果，但是正确的概率更大。所以只要通过多次执行，我们就可以通过统计越来越清楚地知道哪个是正确的结果。其中一类问题的集合是 BPP (bounded-error probabilistic polynomial time) 。BPP 中的问题对应的算法，每次执行的时间是多项式的，结果错误率是一个低于 1/2 的常数，也就意味着我们总共只要多项式的时间就可以以很高的概率得到正确结果。典型的问题是判断一个数是否是素数。此外集合 PP (probabilistic polynomial time) 不再限制错误率是一个低于 1/2 的常数，而是允许它随着问题规模任意接近 1/2，所以其中可能有一些问题相当难以解决。显然 BPP 包含于 PP。

　　除了时间意外，我们可以用问题使用的内存分类问题。以上所有问题都包括在 PSPACE 这个集合内，因为解决它们所消耗的内存是规模的多项式倍；我们还可以考虑一个更大的集合，EXPSPACE，这个集合包括了消耗的内存是规模的指数倍的问题，几乎所有能够想到的问题都存在于 EXPSPACE 中，否则问题的内存消耗就能够穷尽整个宇宙的物质。

　　算法分类问题是名副其实的数学上最难的问题之一， P ?= NP 只是其中的问题之一，实际上我们不知道以下任何一对集合的是否相等（不过人们倾向于认为它们之间都是线 个未解决的难题：

　　由于量子计算机天生就有随机性，所以量子计算机的问题分类结果主要是按照随机算法，而量子计算机视角下对应于经典计算机 BPP 定义的集合称为 BQP(bounded-error quantum polynomial time)。

　　我们考虑所有问题的集合，画出我们定义的这些集合的 Venn 图（根据理论进展，有些问题的复杂度类可能会发生改变）：

　　其中 BPP 集合内部的问题，可以认为是经典计算机可以 “高效” 解决的问题，而 BQP 集合内的问题，是量子计算机可以高效解决的问题。我们注意到两点：1. BQP 集合内包括比 BPP 更多的问题，这意味着有更多经典计算机难以高效解决的问题，可以被量子计算机高效解决。2. BQP 没有完整包括 NP，所以依然有大量有趣的问题无法被量子计算机高效解决，因此量子计算机并不是解决一切的“万能工具”。

　　注：BQP 和 NP 两者的具体关系还没有解决，我们只知道有些 BQP 内的问题不属于 NP（也就是必然存在一些问题，量子计算机可以高效解决，经典计算机不能高效解决）

　　但是 NP 是不是 BQP 的子集呢？这是一个未解决的问题，不过一般的看法是否定的。这是因为 1. 我们没有发现任何一个 NPC 内的问题属于 BQP 2. “单一结果的无结构搜索问题”是一个 NP 问题，但是量子计算机最多只能带来平方的加速，也就是著名的 Grover 算法；而相当多虚构的可以高效解决任何 NP 问题的机器都可以指数加速这个问题（比如上文中的虚构物理体系中），这可能暗示了量子计算机的局限性。

　　首先，我们讨论对于经典计算机无法高效解决的问题，也就是在 P 之外的问题。

　　在上面的 Venn 图中，我们发现根据量子算法相对经典计算机的优势是各不相同的。但是我们结合它们的实现难度，以及用途来列一张表：

　　结合这个表格，下一步最有价值也最容易实现的还是量子体系的模拟，这也是已经展示了量子霸权的各个量子计算团队下一步的重要目标之一。

　　然后我们讨论经典计算机已经可以高效解决的问题，也就是在 P 之内的问题。

　　（请原谅我在下面的介绍中不使用算法复杂度标记，因为我觉得没有必要再介绍新的概念了）

　　是不是如果一个问题，经典计算机已经可以高效解决，那么就不需要量子计算机呢？这可不一定。算法理论中的“简单，高效”，往往是指对于规模，可以在大约这种多项式时间内解决的问题。当比较大的时候，现实中已经很难解决很大规模的问题；一个非常极端的例子是 AKS 素数测试算法，也就是一个判断数是不是素数的算法，在最新的结果中，这个算法的（问题规模是素数的位数），在实际中很难运用，所以实际中真正使用的反而是一些随机算法，这些随机算法虽然有微乎其微的概率错判，但是要比 AKS 快的多。

　　这里我们讨论一个非常有代表性的问题：线性方程组的解。我们知道，对于一个规模为的稠密（大部分系数不是 0）的线性方程组，用经典算法求解需要大约步；而对于稀疏（大部分系数是 0）的线性方程组，用经典算法求解需要大约步，其中是矩阵的“条件数”(矩阵极大和极小特征值或者奇异值的比值)，是“稀疏度”。

　　对于稀疏矩阵而言，存在一个称为 HHL 的算法（HHL 代表了 Arram Harrow, Avinatan Hassidim 和 Seth Lloyd 三人，发表于 2008 年），仅用（改进版本），也就是大约步就可以解这个方程组。这相对于经典算法的相对问题规模快了指数倍。

　　这个算法在当时引起了轰动，因为解线性方程组是一个非常非常重要的问题，几乎用于各个领域。下面好几年出现了一大堆“指数加速算法”，基本思想都是找一个经典的依赖解线性方程组的问题，然后用 HHL 算法指数加速。这在 2014 年左右又大火了一波，因为大家开始对机器学习感兴趣，而一大堆机器学习问题中都要解线 年，量子算法权威 Scott Aaronson 在 HHL 作者的帮助下，直接发了一篇 nature 评论 “Quantum Machine Learning Algorithms: Read the Fine Print“ 指出了很多人对 HHL 的“使用不当”（有趣的是这篇评论的引用数占了原 HHL 的 1/5，考虑到发表时间已经相当多了）。那么 HHL 有哪些“fineprint” 呢？

　　和 QFFT 一样，输入的向量必须编码到是量子态向量的系数上。如果向量最初是经典计算机中的向量，那么显然读取数据就需要步（因为向量本身有个元素），这样你就无法获得加速优势。同样的，矩阵本身的元素也不能全部来自经典计算机的稀疏矩阵，否则读取数据就会占用更多时间。所以大部分机器学习问题，除非人为构造数据，否则很难直接用 HHL 加速。

　　矩阵必须是稀疏的，也就是远小于，否则主导运行时间的就是，而不是，加速效果就会大打折扣。完全无视这一点的相关研究可以说几乎是故意在骗人了。当然，也有一个 HHL 的变种算法，可以加速稠密的线性方程组的求解，但是相对经典算法并没有指数加速。

　　输入的稀疏矩阵必须是可逆的，而且数值特性良好，否则状态数会很大，这样也会失去加速。

　　这个算法的输出和输入一样，也是编码到量子态向量的系数上的，这意味着你没有办法直接将结果直接转换成经典的表示，比如导出成一个数组，打印到屏幕上。不过，你可以通过一些后续的算法研究这种输出的一些性质（虽然还是不能直接得到输出）。

　　如果你的问题没有上述任何一个困扰，那么恭喜你，你可以使用 HHL 来指数加速你的问题求解。

　　看到这些 fineprint，你可能会发现 HHL 和之前的 QFFT 算法有一些相当类似的“共性”，这是因为 HHL 本身就是依赖 QFFT 的。HHL 算法的例子说明了，指数加速一个经典问题，有的时候并不是免费的午餐，越大的加速往往就带来了越多的对求解问题的限制（这也间接说明了量子计算机是有局限性的，不是万能的机器）。

　　这一个例子进一步展现了量子通用计算机的重要性：有相当多的量子算法，可以对各类非常具体的经典问题进行一定的加速，但不是指数加速，因而在量子通用计算机研制出来之前，无法展现优势，其加速不及指数加速也导致它们难以像 Shor 算法，HHL 算法一样有很高的宣传热度。也许最坏的情况是，等到通用量子计算机出现后，人们发现大部分实际问题在实际的条件下只能获得平方加速，但是这并不意味着通用量子计算机的概念并不伟大——要知道比起平方加速，我们很多时候只是优化常数。

　　原标题：《「九章」刷屏的背后：万字长文解析，量子计算机和电子计算机各有何优劣？》