荷兰国家数学和计算机科学中心（CWI）李绎楠：大数据时代下的量子计算

嗨，大家好。这里是学术报告专栏，读芯术小编不定期挑选并亲自跑会，为大家奉献科技领域最优秀的学术报告，为同学们记录报告干货，并想方设法搞到一手的PPT和现场视频——足够干货，足够新鲜！话不多说，快快看过来，希望这些优秀的青年学者、专家杰青的学术报告 ，能让您在业余时间的知识阅读更有价值。

 

 

人工智能论坛如今浩如烟海，有硬货、有干货的讲座却百里挑一。“AI未来说·青年学术论坛”系列讲座由中国科学院大学主办，百度全力支持，读芯术作为合作自媒体。承办单位为中国科学院大学学生会，协办单位为中国科学院计算所研究生会、网络中心研究生会、人工智能学院学生会、化学工程学院学生会、公共政策与管理学院学生会、微电子学院学生会。“AI未来说·青年学术论坛”第五期“量子计算”专场已于2019年5月18日下午在中科院举行。荷兰国家数学和计算机科学中心（CWI）李绎楠为大家带来报告《大数据时代下的量子计算》。

 

李绎楠，荷兰国家数学和计算机科学中心(CWI)博士后研究员。悉尼科技大学博士，师从段润尧教授和乔友明博士，致力于量子信息和理论计算机科学的研究。主要研究方向包括量子纠缠转换，量子大数据处理和有限群同构。研究成果已发表在包括communicationsin mathematical physics 和 IEEE Symposium on Foundations of Computer Science (FOCS)等顶级期刊和会议。

 

报告内容：对大规模数据的处理与计算一直是人工智能领域中的一个最为重要的研究方向。随着量子计算的诞生与发展，量子计算已经在很多计算问题中展现了它独有的优势，例如大数分解，无结构数据库搜索，以及量子系统模拟。近十年以来，一个重要的研究方向是探究量子计算能否让大数据计算变得更加高效。在本报告中，我将从两方面来回答这一问题。一方面，我将介绍大数据处理的量子算法。这些算法可以从理论上实现显著的加速。另一方面，我将介绍如何借鉴量子算法的设计原理来设计更加高效的经典算法，并讨论这些“量子启发式”算法对现行大数据处理算法的影响。

 

大数据时代下的量子计算

 

李绎楠博士先介绍了我们所处的大数据时代背景，我们现在每天产生的数据量非常大，据估算，2018年每天大约产生的数据量是92EB，这个数字预计将在2025年达到491EB。而每天不断增长的数据规模也给我们带来了很多的挑战，比如，存储成本增加，处理速度变慢，很难从大数据中提取有效的信息。应对这些挑战的关键因素是增强算力和优化算法，量子计算，作为一种基于量子力学的计算模型，具有同时解决这两个因素的潜力。

 

接着介绍了量子计算。量子计算的基本存储单元被称为量子比特，它具有很多经典比特（经典计算机的基本存储单元）所没有的特性，例如量子叠加和量子纠缠。基于这些量子特性，量子计算在很多方面可以展现出计算能力上的优势，如量子模拟（LIoyd, Science 96）、大数分解（Shor,FOCS 94）、无结构数据库搜索（Grover, STOC 96）。现在正是量子计算蓬勃发展的年代，我们已经可以制造小规模的量子芯片来实现简单的量子计算。我们国家在量子保密通信等领域已经处于世界领先水平。我们也正在为在NISQ(Noisy Intermediate-Scale Quantum)意义下的量子芯片上实现量子优势而努力。

 

李绎楠博士主要从两方面分享了他对量子计算加速数据处理问题的看法。一方面，量子计算可以提供理论上更快的量子算法加速数据处理。另一方面，我们可以效仿量子算法的设计原理来设计更快的经典算法，从而实现经典数据处理的算法加速。

 

他指出，现在对量子算法快慢的衡量主要是利用了时间复杂度这一在理论计算机领域有着广泛应用的概念。大数分解，量子系统模拟和无结构数据库搜索的量子算法都具有多项式级的复杂度，这样复杂度级别的算法是一般认为的可高效计算。相应的，已知的大数分解和量子系统模拟的经典算法都有指数级别的复杂度，从而在这两个问题上，量子计算已经展现出了它强大的计算优势。另外，虽然无结构数据库搜索也存在着多项式级别的经典算法，但是相应的量子算法仍然可以为我们提供平方级别的加速，并且在很多实际应用中有着重要的意义。

 

对于很多的数据处理算法，例如支持向量机，主成分分析和回归分析，它们都可以在多项式时间内被解决。但是值得注意的是，当我们的数据量以指数级别增加的时候，多项式级别的算法的运行时间也随之以指数级别增加了。这也意味着，当我们在考虑大数据的情形下，未来很有可能需要比多项式级别更快的算法。

 

李绎楠博士从求解线性方程组的量子算法 （Harrow, Hassidim, Lloyd, PRL，2009）这一量子机器学习领域的里程碑式的结果开始介绍量子数据处理的一些量子算法。他指出，当现有的经典数据符合特定的条件，并可以高效地转化为量子数据时，我们可以针对特定的问题设计出相对于经典算法实现指数级别加速的量子算法，例如支持向量机，主成分分析，推荐系统，等等。这些相对于已知经典算法实现指数级加速的算法可以很好地解决数据量过大的问题。特别的，李绎楠博士介绍了他与百度段润尧教授，悉尼大学陶大程教授，刘同亮博士还有杜宇轩同学合作的关于可分非负矩阵分解的量子算法。在一些合理的假设下，他们的算法可以实现指数级别的加速。

 

紧接着，李绎楠博士谈到了去年由德克萨斯大学奥斯丁分校的 EwingTang (现华盛顿大学博士在读)提出的“量子启发式”经典算法。通过改变经典算法的输入和输出的数据结构，我们可以针对某些数据处理任务，如推荐系统，设计出更加高效的经典算法，甚至实现指数级别的加速。相关的文章已经被理论计算机的顶级会议STOC接收。注意到量子算法的优势主要是由于我们采用了量子状态来编码经典数据。而Tang提出的“采样”方法从某种程度上正是在模拟这种量子状态编码。这样的方法对具有“低秩”假设的问题有很好的效果。李绎楠博士随后介绍了和中科院计算所孙晓明研究员，张家琳研究员，陈志怀同学，袁佩同学在可分非负矩阵分解问题上的“量子启发式”经典算法的工作。他们提出的经典算法具有和之前量子算法相同量级的时间上界，从而在理论上实现了经典算法的指数加速。

 

最后，李绎楠博士总结了本次报告的两点内容：数据处理的量子算法和量子启发式算法。他指出，虽然从理论上量子算法可以实现指数级别的加速，但我们在离实现这些量子算法上还有很长的路要走。一方面，现在的技术还无法高效地将经典数据转化为量子算法需要的量子数据；另一方面，现有的量子芯片还无法实现大规模的量子计算，这些问题都应该在未来的研究中得到更多的重视。对于量子启发式算法，虽然我们已经可以在一些人工的例子中实现相对于经典算法的加速，但是“量子启发式”算法对真实数据集的效果并不理想。如何优化这些经典算法，并从理论上降低“量子启发式”算法复杂度中对某些参数的依赖也是未来研究中需要解决的问题。作为结束，李绎楠博士引用了姚期智院士对未来的定义：未来=量子计算+人工智能。这两个领域仍有很多未知的东西等待我们发掘，希望我们能够从报告中有所启发，并下定决心，继续探索。更多精彩内容请关注视频分享。