通识：量子算法发展的四大阶段

摘要：从本期开始，量子前哨将与中关村产业研究院联合创作，推出一系列文章，针对全球范围内的量子信息科技，尤其是量子计算产业化方面的国家政策、技术脉络、活跃企业以及知名科学家等进行系统性的介绍，以飨读者。这是此系列文章的第二篇。

尽管对于绝大多数人来说，“量子计算”是一个属于科幻世界的遥远词汇，但实际上它已经走过了近四十年的历史。在这四十年里，量子计算及其算法从无到有，从理论概念逐渐变成了现实。我们从量子算法发展的角度来看，大体上可以分成四个阶段。

理论提出及探索阶段（1980-1994）

早在1981年，电子计算机还是非常新鲜的事物，个人电脑尚未进入家庭，就已经有科学家提出了“量子计算机”的概念。曾经参与过美国原子弹研制的“曼哈顿计划”诺贝尔奖得主，著名科学家理查德·费曼（Richard Feynman）在麻省理工大学举办的计算物理第一届会议上，发表了论文《用计算机模拟物理学》，论文里费曼首次提出了“量子计算机的概念”，指出使用经典计算机难以有效模拟量子系统的演化，而使用量子计算机能够对量子系统的演化进行有效模拟。

理查德·费曼（图片来源于网络）

1985年,英国牛津大学教授大卫·德伊奇David Deutsch首次提出了量子图灵机模型,并且设计了第一个量子算法Deutsch算法。1992年，德伊奇又和英国剑桥大学教授理查德·乔萨Richard Jozsa对早期Deutsch算法进行了拓展，给出了它在n个量子比特下的算法。这是人类历史上首个利用量子特性设计出来，专门针对量子计算机的算法，开创了量子算法的先河，为后面的Shor算法、Grover算法等量子算法的设计提供了思路。同时，Deutsch-Jozsa算法还说明了比起经典计算机，量子计算机能够更快速、更有效地解决一些特定的问题，显示出了量子计算机巨大的潜力。

但是，当时的技术水平和工程能力还十分低下，且理论物理学家对于量子的特性也尚未完全了解，这些量子算法还停留在纸面设想阶段。

通用量子算法发展阶段（1994-2009）

从20世纪90年代开始，很多大学和企业已经在开始探索不同物理体系中实现量子计算的实验验证，但是这个时代大家都只能实现单比特和两比特的量子计算。另一方面，量子计算的算法得到很大发展，以Shor算法为代表的三大通用量子计算的算法陆续涌现，标志着这一时代研究的焦点是研发通用量子算法。

彼得·肖尔（图片来源于网络）

1994年，美国贝尔实验室的彼得·肖尔（Peter Shor） 提出了Shor算法，在算法界引起了轰动，它从理论上展示了量子计算机能够把质因数分解问题的求解，从指数时间降到多项式时间。目前通用的计算机加密方案——RSA加密，利用的就是质因数分解的时间复杂性：用目前最快的算法对一个大整数进行质因数分解，需要花费的时间都在数年以上。但通过Shor算法，一台量子比特数足够多的量子计算机，能够“轻易”破解RSA模型下的任何大整数。彼得·肖尔因此荣获1999 年理论计算机科学的最高奖——哥德尔奖。

1996年，Lov Grover提出了Grover量子搜索算法，该算法被公认为继Shor算法后的第二大算法，它解决的是无序数据库搜索问题，也是第一个被完整地实验实现的量子算法。时至今日，Grover算法仍是不同量子计算平台的基准实验之一。

图片来源于网络

2009年，MIT三位科学家阿朗·哈罗（Aram Harrow）、阿维那坦·哈西迪姆（Avinatan Hassidim）和赛斯·劳埃德（Seth Lloyd）联合开发了HHL算法。用于求解线性方程组，比起经典算法有指数加速的效果。线性方程组是很多科学和工程领域的核心，所以HHL算法可在机器学习、数据拟合等多种场景中展现出量子计算的优势。

专用量子算法繁荣阶段（2009-2018）

从2009年开始，以谷歌、IBM为代表的一些企业，开始把规模化量子计算机的工程化作为主要的发展方向。他们从两个比特开始，后来逐渐做到几十量子比特的规模。随着研究的深入，大家意识到实现大规模图灵完备的通用量子计算机是一个超出目前工程化水平太多的技术。在规模化还没有达到足够大的情况下，很多科学家转而研究非图灵完备的专用量子计算架构。此类专用量子架构舍弃了逻辑门，但比起通用量子计算更加容易实用化，可以在一些专业领域，解决某种特定类型的问题。

图片来源于网络

在此过程中，很多专用的量子算法出现了。这其中包括一些优化的算法：如变分量子特征值求解算法（Variational Quantum Eigensolver，VQE）、量子近似优化算法（Quantum Approximation Optimization Algorithm, QAOA）等；还有一些采样的算法，包括玻色采样（Boson Sampling）、量子随机游走（Quantum Walk）等算法，此外还有美国斯坦福大学提出的CIM相干伊辛机（Coherent Ising Machine）、以D-Wave公司为代表的量子退火算法（Quantum annealing）等。

量子AI探索阶段（2018至今）

基于量子的叠加和纠缠等原理，使得量子算法非常适于解决人工智能和机器学习中核心的优化（Optimization）过程类问题，所以从2018年开始，以谷歌为代表的企业纷纷开始投入量子人工智能，特别是与深度学习相结合的领域。具有代表性的成果包括Google公司在2020年提出的Tensorflow Quantum（TFQ）框架。TFQ是一种量子-经典混合机器学习的开放源代码库，允许研发人员在设计、训练和测试混合量子经典模型时，可以模拟量子处理器的算法，在最终联机时，还可以在真实量子处理器上运行这些模型的量子部分。TFQ可用于量子分类、量子控制和量子近似优化等功能。

图片来源于网络

此外量子人工智能的研究范畴还包括量子卷积网络QCNN、量子自然语言处理QNLP、量子生成模型QGM等。包括斯坦福大学等在内的单位还在进行量子神经元（CIM Quantum Neuron）方向的研究。预计在未来3到5年中，将会有更多的企业、资源投入到量子人工智能方向的算法研究，成果不断涌现，将量子AI推向一个新的高潮。

文： 王珩  田静秀

编辑：慕一

——end——

关于量子前哨