中国科学院计算技术研究所孙晓明：实现多项式级加速，量子搜索算法的优势与挑战孙晓明，量子计算实验室主任。他演讲的题目是《量子搜索算法与线路优化》。报告简要回顾了搜索算法和路径优化的发展以及当前面临的挑战，并介绍了他的团队在这两个领域的一些工作进展。演讲回顾视频（点击阅读原文查看）：https://app6ca5octe2206.pc.xiaoe-tech.com/detail/p_62612f69e4b09dda125e441b/6?fromH5=true机器之心对演讲内容进行了无删减改变原意。今天要介绍的是量子搜索算法和电路优化，重点是搜索部分。众所周知，搜索是经典计算机上使用最广泛的算法之一。它可以应用于搜索引擎、路径导航或推荐系统等，现在也可以应用于新药的研发，我们甚至可以把密码破译当作一个搜索问题。比如我们要破译一个hash函数，就相当于去寻找一个字符串，使其在hash后满足一定的特征，比如它的前32位全为0，等等。我们知道有一套被誉为计算机算法领域圣经的书——Knuth的《计算机编程的艺术》（TheArtofComputerProgramming）。它的整个第三卷都是关于排序和搜索的，可见搜索的重要性。性别。量子搜索算法我们也知道，量子计算在20世纪90年代突然流行起来。其中一个重要原因是两个重要算法的提出，即Shor算法和Grover算法。Grover'salgorithmGrover'salgorithm可以在无序数据库中搜索特定的元素，例如，如果要在数据库中查找特定的IP地址，或者查找哈希函数的原像，以及国际象棋游戏的最优策略，都可以被视为搜索任务。对于经典算法来说，在一个没有建立索引的数据库上，如果数据库的大小是n，那么肯定需要n线性的时间。量子算法可以具有平方根量级的加速度。虽然它没有像Shor算法那样实现指数级的加速，但是平方根在很多情况下其实是非常有意义的。比如在大数据处理中，本来要处理1亿条数据，但是Grover算法可以做到万条量级。再比如密码分析，本来是2的90次方的暴力枚举算法，但是我们可以把它降到2的45次方左右。对于当前的超级计算，2的45次方的规模是可以接受的。对于Grover搜索，它使用了一个非常重要的模块——Oracle。我们经常看到这样的说法，如果有50个量子比特，就可以实现2的50次方的并行加速，这基本是对的。他其实是在讲这么一个东西，如果可以准备n位的叠加态，比如我们记住n是logN，那么可以提前准备n个零态，然后经过Hardmard变换，就可以了生成所有到N（或从0到N-1=2的n次方负1）个计算基础的叠加态。然后根据线性，经过一个Oracle之后，可以计算出所有的f(x)(x=1~N)，就会得到这样的状态（图中蓝色的叠加状态）。这里实际上有两个问题，将在报告的其余部分讨论。它们与Oracle的编写有关，是基于QRAM可以实现的角度。但是在很多问题中，这个Oracle都有特定的含义。比如我们刚才介绍的，可能是下图左上角的hash函数，甚至是NP完全问题，比如SAT公式。如何准备这样的神谕？其实大家很早就定性的知道了（比如Nielsen和Chuang的《Quantum Computation and Quantum Information》书）只要是可逆函数，都可以用量子的方式来实现。最近在oracle的量化实现上做了这样一个工作，已经上传到arxiv。我们是针对编写这样一类函数的，即CNF或者SAToracle。论文地址：https://arxiv.org/pdf/2101.05430.pdf另外一个问题是如何读取计算结果？我们知道量子不确定性原理。一次读取所有2^n个结果是不可能的。每次读到的概率其实只有1/2^n，也就是说如果有50个bit，只有1/2^50的机会看到任一结果。如果要得到一个具体的计算结果，重复测量需要2^50的时间，所以这里没有加速。但是Grover算法巧妙的设计了通过几次对称和求逆，然后只需要求N次就大概率得到我们想要的结果。幅度放大算法在Grover之后，理论工作者提出了一种称为幅度放大的算法。它要解决的是这样一个场景：如果现在有一个随机搜索算法，它的成功率可能比较低，比如万分之1。我们希望通过调用这个算法来获得高概率的成功。古人常说，“三个皮匠抵得上诸葛亮”。如果每个算法成功的概率是万分之一，那么我们平均要重复10,000次。但是用幅度放大算法的思路（和Grover很像）可以通过取平方根来完成，也就是说需要10000次，但是只需要100次左右就可以搞定。当然，这需要提前把这个算法变成量子算法，才能产生这样的加速度。比如我们把它应用到刚刚提到的NP-complete问题或者SAT问题上，随机选择一个解的话，成功的概率是1/2^n。因此，如果只是简单粗暴地使用Grover的算法，就可以使根数为2的n次方，即1.414^n。但是也可以加入一些算法设计技巧，因为刚才只是简单的调用了Grover算法，里面并没有算法技术。如果做一些更好的算法设计，使用一些更好的SAT求解算法，其实复杂度可以比原来小很多。也存在一些问题。例如，在大数据中，我们经常想在一个社区中找到一个子集群，即使是最简单的三角形子集群。事实上，这个问题目前还不知道它最好的量子算法能做到什么程度。如果单纯使用Grover的算法，可以做一个n^1.5的算法，因为三角形的总数最多是n^3，所以Grover可以做n^1.5。后来，Szegedy可以做n^10/7，现在他可以做n^5/4。但是否有更好的，我们还不知道。这其实给了我们一个启示，就是为什么很多人问的量子算法比较难设计。在我看来，一个原因是量子确实有点违反直觉。它不像我们的古典世界那样有形，所以设计起来相当困难。另一方面，从事这方面研究的人还不够多。《纽约时报》的一篇报道称，全世界从事量子计算的专家不超过一千人。研究成果介绍Localsearch下面是我之前和Shengyu一起做的一个工作的介绍：Groversearch可以用来求解全局极值，即求根n次的时间是求一个全局最大值或最小值。如果我们只需要找到一个局部极值，比如在机器学习中有很多应用，很多时候其实找到一个局部极值就足够了。Aaronson是第一个研究这个问题的人，并给出了一个基本上做三次提取的算法。圣宇、姚老师和我一起证明了三次方的加速是最好的。WeightDetermination跟大家分享一下我们最近做的一个小工作，叫做weightdeterminationproblem。它需要区分两种情况，即解的个数不是k就是l，k和l是预先给定的两个数。其他情况无所谓，只需要能够区分这两个权重即可。我们可以看到一些特殊情况，比如说k等于0并且l等于n/2，也就是说，正好有一半的解或者没有解。这就是第一个提出的量子算法Deustch-Josza算法所做的。再比如，如果k等于0，l等于1，要区分是否至少有一个解，这就是Grover算法所做的。其实在我们之前，中山大学的邱道文先生就做了一些工作，其他的研究人员也做了一些工作，这里就不再赘述了。主要结果让我们直接谈谈我们的结论。我们给出一个下限和一个上限。这里我用一张图来说明上下界是什么样子的。右上图是上界，是量子算法。对于不同的参数d，我们可以先生成一批点。比如前面的工作中可以做的区域只有绿色、红色和这几个点（中图）。我们基本上解决了所有领域。例如，当d=2时，有两个点（右上图），这两个点的左上只需要1个量子查询，就像绿色的那个（左图）。接下来的Case有5个点，就是下图右上角的4个红点和1个蓝点。在它左上角的淡蓝色区域，Quantum只需要两步就可以解决，完全覆盖了之前的一些结论。同时，这5个点的右下方，也就是右下图中淡黄色的区域。我们可以证明它们不可能用量子两步解决，至少三步解决。然后，我们进一步定义集合S_3，它有另一批点。它的左上角有一个算法可以分3步完成，而右下角的任何算法至少需要4步才能完成，同样可以扩展到任何d。刚才胜宇的作品也提到了我以前的博士生袁培。这项工作是与袁培博士、现任博士生何晓宇和前同事杨光一起完成的。量子复杂度下界同时我们也做了一个下界，就是可以证明有一些领域量子做的不是特别好。核心定理之一是Beals等人证明的结论。在2001年。对于一个精确的量子算法，它的复杂度可以写成这个函数的多项式，它的度数除以2给出一个下界。因此，我们可以将这个问题转化为考虑其多项式表示的多项式次数。研究多项式的次数需要一些工具。这里有一个著名的多项式，叫做切比雪夫多项式（ChebyshevPolynomials），意思是cosmθ（m为整数）可以写成cosθ的多项式，比如根据双角公式，cos3θ可以是写成等等。Grover的搜索背后的关键其实就是这样一个Chebyshev多项式。我们也将在这项工作中使用它，最关键的一点是切比雪夫多项式构成了多项式空间的一组基础。然后我们将任意多项式展开到这组基上，然后利用切比雪夫多项式的一些性质来证明一个下界。Quantumsearchwithpriorknowledge以下是我们最近做的另一项工作，叫做quantumsearchwithpriorknowledge。由于在Grover的搜索中我们对正在寻找的解决方案一无所知，这意味着它要么具有相同的概率。但是在一些搜索问题中，比如α-β剪枝，我们预先知道了一定的概率分布，即走哪条路径的概率更高。如果我们现在把它建模成p=(p_1,p_2,…,p_N)的形式，我们知道1是解的概率是p_1，2是解的概率是p_2，N是解的概率解决方案是p_N。在这种情况下如何进行最佳搜索？我们最近研究了这个问题，总的核心结论是需要准备一个特殊的初始状态。这也是我们与盛宇讨论初始状态准备的出发点之一。准备好这个特殊的初始状态后，后续的算法步骤（对称、翻转等）与格罗弗算法非常相似。我们可以证明这样做在渐近意义上几乎是最优的。电路优化下面简单介绍量子电路优化方面的工作。最近，量子硬件发展迅速。2018年，JohnPreskill教授提出了一个名为NISQ（noisy,intermediate-scalequantumsystem）的概念。刚才圣宇也提到IBM有路线图，说明年可以做到1000多比特。但是，它的特点是噪声很大，所以对压缩电路的深度有要求。我们之前做过这样的工作，讨论CNOT电路的线深。众所周知，CNOT加上单位门是通用的，可以生成任何量子电路。因此，CNOT电路具有一定的重要性。下面是一个CNOT电路如何转换为等效电路的示例。原来的深度是7，现在深度是5。核心点是CNOT电路本质上可以写成这些变量的线性组合。CNOT电路的简化实际上与F_2上的可逆矩阵分解有关。事实上，我们可以在每一层上放置多个CNOT门。比如下图左下图的第一层放置了两个CNOT门，对应右下图的第二个矩阵。从线性代数上看，可以看作是行消元，即第一行加第二行，第三行加第四行。因此，CNOT电路的化简可以转化为这样一个数学问题，即如果允许并行高斯消元，将可逆矩阵转化为单位矩阵需要多少步？请注意，每个步骤都可以并行完成。结果介绍我们取得了以下结果，主线是讨论辅助位与电路深度的关系。这是前面的结果，辅助位达到n^2时有一个结果，辅助位为0时有一些结果。我们可以对两边的结果进行改进，有一个更一般的结果，如果有是m个辅助位，那么这个电路深度可以优化到一个紧界，也就是下图右下方的表达式。特别是当m等于0和m等于n^2时，我们的结果可以分别优化原来的两个边界。团队及书籍介绍下图为我们中科院计算所量子计算与算法理论实验室团队的部分成员，包括张家林、田国靖、袁培博士、蒋嘉庆、何晓宇、杨刚刚工作中提到的帅等。本次活动我们得到了两家出版商的大力支持。我们与尚云教授、李路舟教授、殷章启教授、魏朝晖博士、田国靖博士一起，用三年时间翻译了量子计算领域最经典的教科书MichaelA.Nielsen和IsaacL.Chuang《量子计算与量子信息》(10thAnniversaryEdition)（量子计算与量子信息10周年纪念版），译文570多页。我们认为它是一本非常好的教科书，即使从现在的角度来看也是如此。当然，本书确实缺少一些较新的（例如在硬件实现方面）的内容。但是作为一本入门教材对读者来说是非常友好的，尤其是如果你属于计算机领域，想学习量子计算，那么你只需要掌握最基本的线性代数知识，阅读这本书是没有问题的。
