12195
0
2020-03-17
2020-07-11
量子算法简介
量子计算近年来受到了极大关注，根本原因在于其具有强大的并行性，可以在有效时间内解决一些经典计算机不能有效解决的问题。例如，shor 算法可以在多项式时间内解决大数因子分解问题，从而对现代 密码造成了极大威胁。然而，量子计算的并行性并非直接可以利用，而是需要根据所解决的问题经过巧妙的算法设计才可能。即便量子计算机研制成功，如果没有相应的量子算法，量子计算的潜能还是得不到实质性发挥。因此，要想利用量子计算解决实际问题，能否设计出快速的量子算法是关键。不夸张的说，量子算法的研究是推动量子计算向前发展不可取代的力量源泉。
本文尝试为大众提供一个有关量子算法的通俗性介绍，主要内容如下：
量子计算并行性的根源
量子算法的基本框架
量子算法设计的困难性
量子算法研究简明进程
关于量子算法的两个疑问
总结
一、量子计算并行性的根源
量子计算并行性的根源何在？本文回答如下：
(1) 量子叠加带来潜在的并行性。所谓量子叠加是指一个量子系统可以处于多个基态的线性组合形式，例如一个量子比特可以处于状态a|0> b|1>。由此，一次操作u可以并行作用于两个态|0>和|1>上得到au|0> bu|1>，即所谓的“一次操作同时完成多次计算”。然而，这里在并行性前面加了定语“潜在的”，即这种并行性并非直接就解决了问题，还需要后续算法设计。正如量子计算知名学者scott aaronson在接受《麻省理工学院新闻》采访时所说“你要是光看报、读杂志等，你可能会觉得一个量子计算机可以通过‘并行地尝试每一个可能的解’，然后‘在心脏跳一下的时间里解决np完全问题’。嗯，大概那是门外汉们对于量子计算机最核心的错误印象。”
(2) 干涉(interference)使得并行性得以利用成为可能。中学物理课上大家都学习过一种物理现象叫做“双缝干涉”，即一个单光源经过双缝之后会在后面的屏幕上留下明暗相间的条纹。从数学上来看，干涉可以简单理解为几条不同的带权重（权重可以取正、负数）的路径汇合在一起的时候，权重可能相互抵消，也可能相互叠加增大。能否利用这种干涉现象使得量子计算并行性为我们所用，需要极具智慧的算法设计，关键就是要利用干涉现象使得我们想要的目标路径的权重增大，而我们不希望出现的路径权重抵消趋于零。
总结起来：量子叠加带来潜在的并行性，干涉使得并行性得以利用成为可能，算法通过巧妙利用叠加与干涉发挥并行性解决实际问题。
二、量子算法的基本框架
设计量子算法的关键在于：要保证算法的每一步骤符合量子力学的要求，并最终保证其求解速度比经典算法更快。 能发挥量子计算并行性快速解决的问题在数学上通常是关于函数的某种全局属性，所谓全局属性即依赖于函数在某个区间中多个点处的函数值，例如函数的周期、再如下图中的p(f)。
上图中给出了量子算法的一般性框架，为了简约性图中可能去掉了一些严谨的细节。一个量子算法大致可以分为三个阶段：
制备一个叠加态，它表示函数自变量值的线性组合；
作用u_f(函数f所对应的线性算子（矩阵）)，根据线性性，它会分别作用在每一个基态上，把函数对每一个自变量的值计算出来，即体现潜在的并行性；
提取想要的信息。通过巧妙的设计，利用干涉现象使得系统最后状态能以很大的概率落到目标点|p(f)>。算法设计的巧妙性就体现在这一步。
三、量子算法设计的困难性
要设计出好的量子算法并非易事，甚至可以说极具挑战性。其困难性主要体现在以下两点：
具有思想性的算法从来不容易，即使在经典计算领域也是如此。任何一个原创性算法都是智慧的结晶。
量子力学的反直观性使得在经典世界积累的算法设计经验可能不再适用，而此时还要求设计出比经典算法更好的量子算法，从而变得雪上加霜。目前人们并不太清楚量子计算能加速解决的问题具有什么特征，进行量子算法设计时基本上是摸着石头过河。
四、量子算法研究简明进程
虽然设计好的量子算法不易，但是研究者在这方面做了很多努力，也取得了一系列成果。经常有一种说法“现在就那么几个量子算法”。这种说法在某种程度是对，因为具有代表性的量子算法确实不多。但换一个角度，以上说法又不太正确，因为目前针对不同应用场景的量子算法有上百个，大家可以参考http://quantumalgorithmzoo.org/ 了解目前一些主要的量子算法。
如上图所示，追溯量子算法的历史，大致可分为三个阶段：
（1）量子算法的第一阶段（1985-1994），我们称之为初始阶段，其特点是为量子而问题，即为了展示量子计算优势而构造了一些数学问题并为之设计量子算法，这些问题在当时可能并没有多少实用价值。最早的量子算法可以追溯到1985年的deutsch算法。1985年david deutsch在其关于量子图灵机的开创性论文中给出了一个简单问题，并为之设计了一个量子计算过程，通过利用量子叠加和干涉现象展现出了量子计算可能超越经典计算的优势，这为后续量子算法设计埋下了思想的种子。虽然今天看来，deutsch算法非常简单，甚至会觉得一切都是理所当然的，但是在那前无古人的年代把第一个量子算法雏形设计出来是非常需要洞察力和创造力的。后来的deutsch-jozsa算法、simon算法等进一步考虑更复杂的问题并在某种意义下展现出了量子计算相对于经典计算的指数加速优势。
关于simon算法多说几句。这可能是一个有点被外界忽略的量子算法。事实上该算法的意义至少有以下两方面：
simon算法直接启发了著名的shor算法的发现，这一点无论是在shor算法的原文还是在一些知名学者写的量子计算方面的书里都有非常明确地指出来。
simon算法近年在密码破译方面得到直接应用。虽然它所解决的问题在提出之初并未见明显的应用场景，然而近几年基于simon算法进行密码破译的研究在不断跟进，在密码学顶级会议crypto上就有相关工作发表。
有趣的是，simon算法的作者daniel r. simon似乎除了提出该算法之外并没有其他关于量子计算的成果。或许他只是在量子计算的花园里丢下一颗种子就走的游客，幸运的是种子已经发芽开花。
（2）量子算法的第二阶段（1994-2009），我们称之为质变阶段，其特点是为问题而量子，即针对具有重要应用价值的问题而设计量子算法。1994年，shor算法展示了大数分解问题可以被量子计算机在多项式时间内解决，而该问题在经典计算机下的难解性是rsa公钥密码系统安全性的理论基础。随后，1996年grover发现了无序数据库搜索的平方加速量子算法，使得在无序数据库中“大海捞针”成为可能。由于这些算法所解决的问题具有广泛的应用价值，使得这些算法备受关注，从而也大大推动了整个量子计算领域的发展。后续不少研究就是聚焦于如何把以上两个算法映射到更多具有实际价值的问题。另外，此阶段提出的量子游走也是一类进行量子算法设计的重要工具。
（3）量子算法的第三个阶段（2009-至今），我们称之为新的发展阶段，其特点是面向大数据环境。2009年解线性方程组量子算法（hhl算法）的提出标志着量子算法进入了第三阶段。或许hhl算法并不能与shor算法或grover算法媲美，但是在大家苦苦等待新的量子算法出现达10多年之久，hhl算法不失为量子算法设计提供了一条新路径，它或许是把量子模拟应用于数据处理的范例。量子模拟是量子计算的一个重要方面，也涉及各种模拟算法的研究，不过由于其与物理过程更相关，而本文更侧重于利用量子技术进行经典数据处理，所以此处不作重点介绍。
由于人工智能与大数据领域的诸多方法和技术都与解线性方程组有关，因此hhl算法的提出大力推动了量子计算进入机器学习与大数据处理等领域。量子计算与ai的结合近几年成为热点话题，图灵奖得主姚期智先生也多次在报告中提及，毫无疑问这方面的交叉研究值得进行深入探索。
不过这里需要指出几点：
hhl算法并未把方程组的解以经典可读取的方式呈现出来，而是把其编码在量子态中，需要经过后续的算法设计来提取我们想要的信息。近年来出现的大量有关量子机器学习的研究主要就是基于hhl算法做后续算法设计。
目前一些量子机器学习方面的研究需要提供更严肃的理论分析。
量子机器学习如果要面对实际数据处理问题，有待突破输入/输出瓶颈。所谓输入/输出瓶颈是指，目前大部分量子机器学习算法或者需要把大规模数据集编码为量子态，或者只是把问题的解生成在量子态中，因此输入阶段的前处理和信息提取阶段的后处理将耗费大量时间，乃至抵消量子算法所节省的时间。
近期，华裔学生 ewin tang 受量子推荐算法的启发设计出了一个经典算法，它能以和量子算法相近的速度解决推荐问题，从而使得受量子启发的经典算法设计或者说量子算法的经典化进入了更多学者的视野。在某些问题上量子被证明相对于经典有加速优势，而更多的问题并没有盖棺定论，如果量子算法思维能促进经典算法的发展，这也将是量子计算研究意义的另一种体现。
五、关于量子算法的两个疑问
笔者在平时交流中经常被问及以下两个问题，特别是信息学背景的朋友问得比较多，相关问题和回答如下：
（1）量子计算机没造出来，有必要研究量子算法吗？
从经典计算领域来看，算法的研究远远早于计算机的出现。欧几里德算法出现在古希腊时代，而第一台电子计算机是1946年生产的。另外，图灵机的提出正是为了严格地刻画“算法”。
没有算法支持的量子计算机是否还能称为计算机呢？量子算法是量子计算机的必要软件支撑，同时量子算法的研究也是推动量子计算发展的强大动力，从shor算法的历史地位可见一斑。
（2）没有量子计算机，怎么研究量子算法？怎么评价算法的好坏？
抽象层次的算法设计从来不依赖于具体硬件平台，在经典计算领域就是如此。算法本质上是解决问题的一种方法，量子算法是遵循量子力学规律的一种方法。硬件平台只是实现这种方法的一个工具。当然，软硬件之间的互动与交流对于设计更符合实际情况的算法非常必要。
从算法与复杂性研究的角度来看，算法的好坏由复杂度衡量，这依赖于严格的数学证明，而不是在具体硬件平台上的测试。目前量子算法主流的研究是如此。
六、总结
量子计算机相对与经典计算机在哪些方面有优势？有多大程度的优势？这些问题目前远未搞清楚，这意味着量子算法的研究有非常大的空间。大家都期待量子计算领域有更多具有创新性的算法出现，每一位量子算法研究者也都希望设计出一个代表性算法。然而，罗马不是一天建成的，千里之行始于足下。我们不应只记住shor算法的巧妙，而忘记前人的努力。事实上，shor算法是站在simon算法的肩上，而simon算法源于那些看似没用的deutsch-jozsa算法和deutsch算法。这个过程正好体现了科学研究的魅力：或许很多研究成果会被大浪淘沙，但正是那些一点一滴的看似无用的研究一步一步孕育着一个新的发现！
最后一句：量子计算研究要“软硬兼施“！
研究团队介绍：
本文来自中山大学数据科学与计算机学院量子计算实验室(http://www.scholat.com/team/quantumlab)，研究团队主要研究兴趣为量子计算模型、算法与复杂性，主要从计算机科学角度出发，围绕”量子计算相对于经典计算有何优势与本质不同”这一中心问题开展研究。
中山大学计算机学科从2000年左右开始从事量子计算方面的研究，是国内计算机领域最早从事量子计算研究的力量之一，已培养量子计算方面的研究生数十人，未来将一如既往地为量子计算的研究和人才培养做出努力。如果您是对量子计算感兴趣的学生，欢迎一起来探索量子计算领域有趣的问题。如果您已学业有成，欢迎加入中山大学，我们一直在致力于团队建设。期待有志青年加入，携手共创未来！
研究团队招聘专任教师、特聘研究员、副研究员、博士后，欢迎从事量子计算相关研究的青年才俊加入！招收博士、硕士、高年级本科。欢迎联系咨询（李绿周：lilvzh@mail.sysu.edu.cn），同时可以搜索微信公众号“中山大学数据科学与计算机学院”了解相关招聘信息。
