李绿周，量子计算研究要“软硬兼施”，《中国科学报》 (2020-05-07 第3版 信息技术)

http://news.sciencenet.cn/sbhtmlnews/2020/5/354996.shtm

注：引用请注明以上出处，全文如下：

近年来，量子计算受到了极大关注，根本原因在于其具有强大的并行性，可以在有效时间内解决一些经典计算机不能有效解决的问题。

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

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

量子算法的历史阶段

量子算法的第一阶段（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算法媲美，但是在大家苦苦等待新的量子算法出现达10多年之久，HHL算法不失为量子算法设计提供了一条新路径，它或许是把量子模拟应用于数据处理的范例。

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

量子算法的问题思考

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

目前一些量子机器学习方面的研究需要提供更严肃的理论分析。量子机器学习如果要面对实际数据处理问题，有待突破输入/输出瓶颈。所谓输入/输出瓶颈是指，大部分量子机器学习算法或者需要把大规模数据集编码为量子态，或者只是把问题的解生成在量子态中，因此输入阶段的前处理和信息提取阶段的后处理将耗费大量时间，乃至抵消量子算法所节省的时间。

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

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

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

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

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

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

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

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

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

千里之行始于足下

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

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

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