中国科学报 李绿周

近年来，量子计算受到极大关注，根本原因在于其具有强大的并行性，可以解决一些经典计算机现阶段无法解决的问题。

然而，量子计算的并行性并非直接可用，还需要结合所解决的问题进行巧妙的算法设计。即便量子计算机硬件研制成功，如果没有相应的量子算法，量子计算的潜能还是得不到实质性释放。要想利用量子计算解决实际问题，设计出快速的量子算法是关键。当然，量子算法需要运行在量子计算硬件平台上才能起作用。

因此，量子计算研究要“软硬兼施”。

发展中的量子算法

量子算法的第一阶段（1985—1994），称之为初始阶段，其特点是“为量子而问题”，即为了展示量子计算优势而构造了一些数学问题并为之设计量子算法。这些问题在当时可能并没有多少实用价值。

最早的量子算法可以追溯到1985年的Deutsch算法。1985年牛津大学的物理学家David Deutsch在其关于量子图灵机的开创性论文中给出了一个简单问题，并为之设计了一个量子计算过程，通过利用量子叠加和干涉现象展现出量子计算可能超越经典计算的可能。这为量子算法后续的设计埋下了思想的种子。

虽然今天看来，Deutsch算法非常简单，但是在那前无古人的年代把第一个量子算法雏形设计出来是非常需要洞察力和创造力的。后来的Deutsch-Jozsa算法、Simon算法等进一步考虑更复杂的问题，并在某种意义下展现出了量子计算相对于经典计算的指数加速优势。

Simon算法可能是一个或多或少被外界忽略的量子算法。事实上该算法的意义至少有以下两方面：一方面，Simon算法直接启发了著名的Shor算法的发现，这一点无论是在Shor算法的原文还是在一些知名学者的书里都有明确显示；另一方面，近年来Simon算法在密码破译方面得到直接应用。

量子算法的第二阶段（1994—2009），称之为质变阶段，其特点是“为问题而量子”，即针对具有重要应用价值的问题设计量子算法。1994年，Shor算法发现大数分解问题可以被量子计算机解决，而该问题在经典计算机下的难解性是RSA公钥密码系统安全性的理论基础。随后，1996年Grover算法在搜索无序数据库最小值中得到应用，使得在无序数据库中“大海捞针”成为可能。

这些量子算法所解决的问题具有广泛的应用价值，因而备受关注，这也大大推动了整个量子计算的发展。后续诸多研究就聚焦于如何把以上的算法映射到更多具有实际价值的问题中。

量子算法的第三个阶段（2009年至今），我们称之为新的发展阶段，其特点是面向大数据环境。2009年解线性方程组量子算法（HHL算法）的提出标志着量子算法进入了第三阶段。或许HHL算法并不能与Shor算法或Grover算法媲美，但是HHL算法不失为量子算法的一条新路径，它或许是把量子模拟应用于数据处理的范例。

由于人工智能与大数据领域的诸多方法和技术都与解线性方程组有关，因此HHL算法的提出大力推动了量子计算进入机器学习与大数据处理等领域。量子计算与人工智能的结合近几年成为热点话题，图灵奖得主姚期智也多次在报告中提及，这方面的交叉研究值得进行深入探索。

量子算法的深入思考

HHL算法并未把方程组的解以经典可读取的方式呈现出来，而是将其编码在量子态中，需要经过后续的算法设计来提取人类想要的信息。近年来出现的不少有关量子机器学习的研究主要是基于HHL算法开展的。

目前，一些量子机器学习方面的研究需要提供更严肃的理论分析。量子机器学习面对实际数据处理问题，有待突破输入/输出瓶颈。

所谓输入/输出瓶颈是指，大部分量子机器学习算法或需要把大规模数据集编码为量子态，或把问题的解生成在量子态中，因此输入阶段的前处理和信息提取阶段的后处理将耗费大量时间，甚至能抵消量子算法所节省的时间。

近期，华盛顿大学华裔学生Ewin Tang受量子推荐算法的启发设计出一个经典算法。该算法能以与量子算法相近的速度解决问题，这也让受量子启发的经典算法设计或者说量子算法的经典化进入了更多学者的视野。如果量子算法思维能促进经典算法的发展，这也将是量子计算研究意义的另一种体现。

笔者梳理了有关量子算法的两个常见问题和回答，以供参考。

问：量子计算机还没造出来，现在有必要研究量子算法吗？

答：首先，从经典计算领域来看，算法的研究远远早于计算机的出现。欧几里德算法出现在古希腊时代，而第一台电子计算机是1946年生产的。另外，图灵机的提出正是为了严格地刻画“算法”。

其次，没有算法支持的量子计算机还能称为计算机吗？量子算法是量子计算机的必要软件支撑，同时量子算法的研究也是推动量子计算向前发展的强大动力，从Shor算法的历史地位可见一斑。因此，研究量子算法也是研制量子计算机的重要环节之一。

问：没有量子计算机，怎么研究量子算法？怎么评价算法的好坏？

答：抽象层次的算法设计从来不依赖于具体硬件平台，在经典计算领域就是如此。算法本质上是解决问题的一种方法，量子算法是遵循量子力学规律的一种方法。硬件平台只是实现这种方法的一个工具。当然，软硬件之间的互动与交流对于设计更符合实际情况的算法非常必要。

从算法与复杂性研究的角度来看，算法的好坏由复杂度决定，这依赖于严格的数学证明，而不是在具体硬件平台上测试。目前量子算法主流的研究均是如此。

随着量子计算技术的发展，越来越多的量子算法得以在真实量子平台上进行原理性验证。可能有时研究者会在经典计算机上对量子算法进行一定模拟以加深理解，但那并非在经典计算机上实现了量子算法。

千里之行始于足下

量子计算相对于经典计算在哪些方面有优势？有多大的优势？这些问题目前尚未搞清楚。这意味着量子算法的研究有非常大的空间。大家都期待量子计算领域有更多具有创新性的算法出现，每一位量子算法研究者也希望设计出一个代表性算法。

罗马不是一天建成的，千里之行始于足下。我们不应只记住Shor算法的巧妙，而忘记前人的努力。事实上，Shor算法是站在Simon算法的肩膀上诞生的，而Simon算法源于那些看似没用的Deutsch-Jozsa算法和Deutsch算法。

这个过程正好体现了科学研究的魅力：或许很多研究成果会经历大浪淘沙，但正是那些一点一滴的看似无用的研究，一步一步孕育着一个新的发现。

（作者系中山大学教授，本报记者沈春蕾整理）

版权声明：本文转载仅仅是出于传播信息的需要，并不意味着代表本网站观点或证实其内容的真实性；如其他媒体、网站或个人从本网站转载使用，须保留本网站注明的“来源”，并自负版权等法律责任；作者如果不希望被转载或者联系转载稿费等事宜，请与我们接洽。