谷歌搜索将有大变化：修改算法，侧重移动端

机器之心原创
作者：樊晓芳

「相信会有量子计算机，相信量子计算机会以非常棒的方式进入我们生活，相信我们会有一个新的量子技术的生态环境，也相信量子技术会让计算更加安全。」阿里巴巴量子技术首席科学家施尧耘在 10 月 12 日的云栖大会量子技术峰会上如是说道。

此次阿里巴巴量子技术峰会以「量子 IT 展望」为主题，邀请了来自苏黎世联邦理工学院（ETH Zürich）、荷兰代尔夫特理工大学（TU Delft）、悉尼科技大学（UTS）、加拿大圭尔夫大学和滑铁卢大学量子计算研究所（IQC）、荷兰国家数学和计算机科学研究中心（CWI）、中科大等国际知名量子技术研究机构的 9 位教授参会分享，分别就各自在量子信息理论、量子编程语言、量子计算软件、量子算法及计算复杂性、量子计算云平台、量子互联网、量子通信等量子信息技术研究方向介绍了各自的工作成果和见解。

这次量子峰会也是自 2013 年姚期智教授在清华大学交叉信息研究院和 2015 年应明生教授在悉尼科技大学举办量子信息处理国际会议（QIP）后，华人举办的学界嘉宾参与度最高的一次国际性量子信息科学研讨会。

就在量子峰会的前一天、云栖大会的首日，施尧耘与中科院潘建伟院士共同推出了由阿里云与「中国科学院-阿里巴巴量子计算实验室」联合开发的「量子计算云平台」。这也是自阿里巴巴在今年 3 月云栖大会深圳峰会上公布全球首个云上量子通信商用服务之后在量子信息技术业务上的又一新动作。据悉，阿里巴巴自 2014 年开始就陆续在量子密钥分发、数据传输、基于云环境的加密系统、电子处方等量子保密通信业务领域申请了多项专利。

「我其实觉得很惭愧，阿里巴巴在量子通信和量子计算云平台上的众多工作，是在我加入之前就有了，靠团队多年的沉淀积累和努力。我刚加入并没有贡献太多，但还是上台参加了发布仪式。现在我加入后，会更系统地规划考虑。」施尧耘说道，「跟中科院和中科大的合作更多是从硬件层面，如量子器件和量子计算云平台基础设施。未来会继续加深合作，也可以让阿里的人去科大学习他们的实验，开展互补的合作。同时谢崇进谢博士在量子通信方向的工作，也会更加的支持，与谢博士一起努力。」

「量子计算的成功不仅需要量子处理器，还有其他软件、算法、应用三个关键部分。阿里巴巴要重点发展量子计算软件、算法、应用这三个方面，同时和实验团队合作开发处理器。」施尧耘与机器之心强调。

施尧耘似乎更明白，阿里巴巴在 IT 基础设施和算法工程上拥有的多年开发经验及庞大的互联网业务应用场景对开展量子计算软件和应用业务研究具备先天优势。

当谈及阿里云量子实验室（AQL）未来在量子信息技术方向的战略规划时，施尧耘告诉机器之心，「工作重点有四个环节。首先是硬件，阿里巴巴已经和潘建伟教授合作，未来也会和更多研究所合作，包括量子器件、量子控制、量子计算机设计等。再往上是量子软件，应明生教授是这方面的专家。再往上一个层次是量子算法，可与 Andris Ambainis、Mario Szegedy 教授合作。最上层是应用，模拟量子系统。我们希望越早行动越好，做到行业最高水平。」

「同时我们希望被看成是个学术研究机构，把科学问题研究好。在人员上，我们希望与学界一起培养博士生，正式人员多做访问和教育。因此我们不仅会招直接可以工作的人才，更希望从学生开始培养，促进他们思考，增加他们对阿里的感受，等学生学成之后，也会更匹配阿里的战略发展。」

「我还想做『量子猫』！」此时的施尧耘尤其兴奋。「Quantum Cat」他再次重复道，「这可不是薛定谔的猫。你们有听说过谷歌那个很有名的『找猫』项目吗？谷歌通过发展了大规模机器学习实现了『识别什么是猫』这个任务。找猫的结果并不重要，但是找猫的技术可以解决很多的其他领域的应用问题。找到一个很重要的应用场景，并简化这个技术，用它来解决其他的关键问题。」

自今年 9 月份正式加入阿里巴巴，施尧耘已迅速投入组建阿里云量子实验室（AQL）的工作中。本次量子峰会上受邀参会的嘉宾均为施尧耘从拜访过的国内外量子科学学术和研究机构中邀请的学术代表。据施尧耘透露，未来阿里巴巴也将陆续与这些教授和机构展开更深入的学术交流和人才联合培养的合作。

结合其自身在量子算法和复杂性、量子系统和量子计算模拟等领域的学术背景，施尧耘选择聚焦自己更擅长但国内学界关注度较弱、人才欠缺的量子计算软件、算法和应用研究领域，无疑是能同时借助企业优势发力，满足企业研发需求，并直接促进国内量子计算行业发展的最好方式。

量子软件是量子计算机的灵魂

「量子计算机要发展起来，也要重视量子软件的发展」，现任中国科学院软件研究所副所长、清华大学和悉尼科技大学教授应明生在会上表示。作为量子计算程序理论和语言构造方向最杰出的领军学者之一，应教授早在 2008 年就呼吁：「一旦量子计算机研制成功，量子软件的开发将变成真正发挥量子计算机作用的关键[1]。」

量子计算机软件和经典计算机软件一样，是用户与计算机硬件进行交流和控制的接口界面，其包括量子编程、量子算法、量子计算模型与复杂性等研究领域。

「量子计算机非常难构建，同时也非常难进行编程，现在已有许多人正在关注量子计算硬件研发，我们是时候应该多关注量子编程软件及学习如何控制和使用量子计算机，甚至量子计算机科学。」荷兰国家数学和计算机科学研究中心（CWI）Harry Buhrman 教授在会上提出。

但由于量子物理系统与经典物理体系相比有很多诸如量子叠加态、相干性、纠缠等根本性不同的特征，现有已知的例如带随机存储（RAM）的量子图灵机、量子线路模型、绝热量子计算、拓扑量子计算等主流量子计算模型也都与经典计算机在较多层面上有不同程度的差异。量子计算软件很大程度上不能直接使用经典计算软件的理论、方法和技术，这也让量子软件的开发变得十分困难且备具挑战。

「我的工作是开发量子软件，在不考虑量子计算机硬件的研发情况下增加量子计算机的算力。」来自苏黎世联邦理工学院博士在读生、开源量子软件框架 Project Q 团队的核心成员之一 Damian Steiger 说道。其团队希望通过搭建一个统一的量子计算软件框架，使用接入的量子计算机或超级计算机模拟的量子计算机仿真环境来测试算法的速度和正确性，以便更好地降低传统经典计算机开发者设计和开发量子软件的门槛。该软件可通过 http://www.projectq.ch 下载和安装，直接对接 5 量子比特的 IBM Q 量子计算商用系统。研发者只需懂 Python 即可操作，并可以调用其自带的资料库 FermiLib 以解决例如从分子立体结构到使用汉密尔顿函数的量子门的研发等相关费米子问题，或在模拟环境中验证自己的量子算法是否可行，以及进行量子算法、量子编程、控制量子计算机运作能力甚至量子游戏的开发。

量子编程语言研究保障量子软件工程

「若在量子语言广泛传播之前没有一个扎实的语义基础研究，会对这领域的软件工程造成巨大灾难[2]。」应教授在演讲中引用英国格拉斯哥大学计算机科学学院研究量子计算、通讯和加密方向的 Simon Gay 教授在 2006 年发布的一项研究中的观点，也意在提出，在量子计算硬件存在之前就开始设计和准备量子编程语言，也是一种合理的思路。

1996 年，美国洛斯阿拉莫斯国家实验室（LANL）提出了第一个理论上可通过经典计算对量子计算进行预处理来获得量子系统测量结果的主从式量子计算机体系结构「量子随机存储机（QRAM）」以及适合在其体系上实现的量子程序设计伪代码语言[3]，对量子寄存器的应用和引入方法、量子寄存器与传统寄存器之间如何对接转换等问题做出了详细建议，为当时量子编程语言设计领域提供了重要的构想基础和设计启发。

随后的 10 年间，基于 QRAM 体系或结合经典 C 语言等新思考后的一些简单的量子程序设计语言 QCL、qGCL、QPL 被陆续提出。但该领域真正的研究热情和工作还是在美国情报先进研究计划署（IARPA）于 2010 年开启量子计算科学项目之后被激发。至今比较受关注的量子编程语言包括受 IARPA 支持的 Peter Selinger 组的 Quipper、普林斯顿大学等单位合作实现的 Scaffold，企业界代表微软的 LIQUi|> 和量子计算创业公司新秀 Rigetti 的 Quil，以及学界代表 ETH 的 Project Q 等。

「编程工作是经常容易出错的，且相比在经典物理世界，人类在经典世界中获得的常规思维方式和直觉更难适应并理解量子世界，因此在量子计算机上编程更容易出错。」应教授解释道。根据这个思考逻辑，应教授认为在量子程序设计中十分有必要添加验证功能。具体可从其命令式量子程序中的核心语言出发，将合适的验证逻辑结构嵌入量子程序的分析当中。「最有意思的是量子化的『if statement』和『while』这两个结构，他们在量子程序中的验证分析问题都得到了解决。」应教授指着自己的演示文稿有兴许激动，「这样程序就会根据认证结果输出选择后的结果，并选择性地执行循环，用于检验量子程序的完全正确性或部分正确性。」

同时基于对量子编程语言多年的研究基础，应教授也希望在未来重点发展其 Q|SI>量子程序设计环境，具体包含 1）量子程序设计语言，例如在其他编程语言中没有出现过的量子「while」循环；2) 量子编译器qCompiler，将量子编程语言写成的程序编译成例如IBM QASM 2.0 等底层的量子汇编语言；3)量子模拟器 qSimulator，现在正进行 45 个量子比特的量子程序的模拟；4）量子程序认证工具 qVerifier；5）量子程序终止分析工具 qTerminator。

应教授表示其未来的工作重点将更多关注其语言逻辑在比如对量子加密协议和量子关系 Hoare 逻辑的验证上的应用，以及开发更多带有纠正功能算法来进行程序验证。同时，在如增加量子控制、量子递归等角度提出更多程序构念，通过在平行、并发、分布式量子编程上更多的研究工作来实现 49-50 个量子比特/「Quantum Supremacy」的分布式量子计算系统、不同进程中的纠缠状况、并行量子计算机内存模型，以及对量子网络进行编程。

量子算法可实现指数级加速

「这是我们再熟悉不过的 Peter Shor」，罗格斯大学计算机科学系教授 Mario Szegedy 笑着介绍道，「左边是他发明 Shor 算法时的样子，右边是他现在的样子」。Szegedy 教授作为 PCP 定理和流算法的证明者和贡献者之一，曾两次获得理论计算机领域最高荣誉奖 Gödel Prize，其工作对量子算法和计算复杂性以及量子通信密码学和工程研究提供了非常重要的理论基础。同样 Peter Shor 教授也因开发了可用于因数分解的 Shor 算法获得1999 年的 Gödel Prize[4]。
Mario Szegedy 教授的演示文稿中的插图

Shor 算法最明显的用途就是对使用大因数分解方式、依赖计算复杂性制造的 RSA 加密算法进行破译。一个 1024 比特的 RSA 算法需要 1 百万个 CPU 来解决，但现在即使使用最小数量量子比特的量子计算机上运行 Shor 算法，也只需要约 10 小时。随着量子计算机上的量子比特数量逐个增加，其计算能力呈指数级增长。

与 Shor 算法齐名的另一种量子算法是 Grover 搜索算法。Grover 算法的存在让针对搜索问题尝试的次数降到根号级别，花费的时间成根号级数缩短。「量子搜索对大规模数量搜索应用的作用非常大，比如在优化问题中找到最佳路线和规划、破译密码中减少穷尽式尝试密钥所需要的次数、目标事件发生概率预测情况下减少测试数量等解决复杂的统计问题。」拉脱维亚大学物理和数学系教授 Andris Ambainis 表示。Ambainis 教授是该大学计算系量子计算研究组的负责人，其工作重点集中在量子搜索算法、计算复杂性、量子通信和密码学等量子信息理论研究工作。其最近的研究方向是通过使用回溯、量子漫步、Quantum Query 等原理针对可被等价为规模可知但结构未知的搜索树的计算任务来设计对应可进行加速计算的量子算法。

大多数计算机科学视角中的量子计算是指能实现指数级加速的量子算法。现今已知的量子算法大体上可以分为以上提到的以 Shor 为代表的用于因数分解以及解决隐含子群问题（HSP）的算法、以 Grover 为代表的用于非结构化搜索和优化的算法、以 D-Wave 使用的量子退火算法为代表的用于解决量子组合优化问题的量子绝热算法、用于模拟量子化学、超导、材料学和超能物理等量子系统的量子模拟算法、求解线性系统的量子 Harrow-Hassdim-Lloyd（HHL）算法，以及量子漫步等算法[5]。量子算法的优化能使整个量子计算机系统拥有较高的总体效用。

「有很长一段时间，量子计算领域只有 Shor 算法和 Grover 算法两个常被提及的量子算法，但近年情况有所好转。研究者正在发展和构建诸多量子算法设计框架，为针对各种问题的量子算法设计赋能。」悉尼科技大学教授季铮锋在演讲中说道。除了设计量子算法框架，量子算法面临的挑战还包括如何将这些量子算法框架应用到现实问题中，比如用到机器学习、材料科学、量子化学等领域。

量子计算复杂性研究助力算法设计和问题求解

季教授师从应明生教授，多年来的学术研究方向主要在量子计算复杂性。量子计算复杂性主要研究不同计算模型在量子物理的新视角下其计算能力和性质的变化，其领域包括 1）类比经典可计算性理论的量子线路模型、量子图灵机、量子图灵机和量子线路模型等价性、BQP（量子计算机多项式时间能处理的判定问题对应的复杂度类）、Oracle Separation；2）量子黑盒复杂性；3）Quantum Supremacy 和其背后的复杂性理论支持，例如后选择效应（Postselection）、与多项式阶层相关的问题等等。量子复杂性理论中另一个获得长足发展的领域是对应经典计算复杂性理论中证明验证的量子推广。这个领域研究包括 QMA（量子计算版本的 NP 类）、量子 Cook-Levin 理论、哈密顿复杂性等其他与凝聚态物理的相关性，以及量子交互式证明和对量子 PCP 猜想的探索等。

同时，季教授又提及量子复杂性面临的挑战，需要首先更好理解 BQP 类在经典计算与量子计算之间的关系，以及证明或证伪量子 PCP 猜想（其结果也会帮助人们更好理解量子纠缠的原理和纠缠证明的能力）。这些复杂性理论上的进展有望应用在量子计算的委托问题上，也就是将来量子计算能力放至云端后，我们需要考虑如何可信地把我们的计算问题委托给云端的量子计算机来处理。

量子计算云平台加速算法开发及应用

在当今量子计算机还没有商业化应用之前，量子程序设计仍需要在传统经典计算机上进行，但毕竟经典计算体系和量子计算体系在设备的物理原理上存在的根本差异会造成一定的算法设计偏差和验证困难。量子计算云平台的出现为广大研究人员和开发者提供了一个更好的量子程序设计和应用开发环境。

在量子峰会召开的前一天，中科大潘建伟教授牵头的中科大-阿里巴巴量子计算实验室、清华大学物理系龙桂鲁教授与加拿大圭尔夫大学数学系和滑铁卢大学量子计算研究所（IQC）的曾蓓教授共同带领的实验组、中科大郭光灿院士的本源量子公司同时发布了基于不同物理体系量子计算机的量子计算云平台，也意味着中国在量子计算云平台的工作上迈出了崭新的一步。

「NMRCloudQ 是国际上首个基于核磁共振的量子云计算平台项目。暂时还是初步测试版本，但在上线后的一天内已经收到近 100 个递交的计算任务。」曾蓓教授在会上重点介绍了该项目。「我们参与这个项目的清华团队成员们也都来到了现场，大家有什么技术问题可以直接问他们。」曾蓓教授多次在会上激动地介绍她「可爱的」同学和合作者们。

据了解，NMRCloudQ 对接的核磁共振量子计算机是曾蓓教授在本科时期科研训练方向的老师龙桂鲁教授制作的，包含四个量子比特，但是逻辑门保真度超过 98%，可以完成很多步复杂的逻辑门[6]。同时，该项目将核磁共振量子计算体系的控制层也开发给用户，用户可从实践中对量子计算机体系结构和运行方式有更深度的理解，自行开展量子计算和量子操控的研究。

曾蓓教授介绍 NMRCloudQ 团队

曾蓓教授在核磁共振量子模拟器上的研究还包括使用基于测量量子反馈控制（MQFC）的优化方式制造了一个由 12 量子比特核磁共振量子处理器设计的拥有必要控制脉冲的 12 个相干态，以便通过使用量子处理器最大化其控制能力和精确性[7]。因为 MQFC 也容易迁移应用到其他技术体系的通用量子信息处理器上，为进行更大规模和更精确地控制量子系统提出了一条新思路，也有助于更进一步实现「Quantum Supremacy」的展示。

产研结合让量子计算成为可能

「今天英特尔公布了 17 个量子比特的超导量子计算机芯片，这个芯片就是与我们 QuTech 研究所合作完成的。」，来自荷兰代尔夫特理工大学（TU Delft）的 Stephanie Wehner 教授在演讲时激动地表示。QuTech 是由被誉为「欧洲麻省理工」的荷兰代尔夫特理工大学（TU Delft）和荷兰国家应用科学研究院（TNO）合作的针对实现量子计算和量子互联网成立的高等研究中心。其量子计算实验室分为拓扑量子计算和容错量子计算两大方向，分别与微软量子计算研究 Station Q 在拓扑量子计算方面、与英特尔在超导量子体系路线上有深度合作。
Stephanie Wehner 教授演讲中关于 QuTech 工作架构的介绍

QuTech 有多个物理体系的量子计算硬件平台，包括超导量子电路系统、半导体量子点电子自旋量子比特系统、金刚石 NV（氮-空位）电子自旋和核自旋量子比特系统、超导-半导体体系中拓扑马约拉纳量子比特系统。因为对于做量子计算软件系统的研究者来说了解硬件平台的优缺点来说很有必要，有的系统拥有较快量子门电路速度但其量子比特的寿命较短或相干性维持时间较短，取决于该系统的应用场景是计算还是长距离通信。同时，QuTech 具备整套量子硬件和软件研发环境，并拥有 QuTech Academy 学院来培养未来更多的量子工程师。
Qutech 量子计算硬件平台介绍

由 QuTech 提出的电路模型可编程量子计算机构架 [8]

「我们于 2015 年创办了 QuSoft 学术研究院，专注解决量子软件问题。」来自 CWI 的 Harry Buhrman 教授同样激动地表示。

「量子软件是任何量子计算机的核心，但最直接的挑战是现有量子计算机拥有的量子比特数量远小于 100。不过，我们可以先考虑在仅有 10-50 或更小数量量子比特的量子计算机系统上可以开发何种应用，特别是在这群量子比特还比较脆弱及不稳定的环境下。其次，在现有小规模量子网络的基础上，如何实现量子密码分布式系统、通过长距离量子中继器上的量子对纠缠。再之，需要考虑纠错机制。」Harry Buhrman 教授详细地介绍了 QuSoft 研究院未来的研究方向。

QuSoft 研究院研究方向介绍

迈向「量子霸权」？

自 2011 年加州理工学院物理学家 John Preskill 教授提出「Quantum Supremacy」[9]的概念以来，业界对提出该词这个行为本身的意义、对该词的理解是否存在偏差或过分解读的情况、学术界短期追逐创造更高数量量子比特的量子计算机的利与弊等话题都充满了讨论。

「我不是很喜欢 Quantum Supremacy 这个词。」当机器之心问及 Buhrman 教授时，他回答道，「因为现有一些还没开发出应用价值的算法即使实现了 Quantum Supremacy，也仅仅是运用量子处理器在解决某一运算任务上的成绩比较好，但其没法去模拟经典计算机能处理的问题。但也算是下一步比较好的研发方向。」

Ambainis 教授则表示，「我认为 Quantum Supremacy 在短期还是非常重要的目标，表示大家在争取实现一些量子优势。玻色采样算法是个很有意思的例子，因为针对量子算法的商用价值，你还需要其他各种资源、更先进的量子设备、对应用场景更清楚地理解来进行研究。」

Buhrman 教授又笑着向机器之心解释说，「通常人们需要先对量子计算机在计算何种问题上比经典计算机计算得快的想法，然后才会去尝试考虑运算的实用性和具体应用领域。所以我们首先是要先尽力寻找量子计算机能在做什么任务时速度可超越经典计算机的运算。即使暂时还没看到这些算法的具体应用，也要坚持去做，有些算法现在看起来没用，但可能算法在变体后就有用。正如第一个量子算法是由 David Deutsch 提出[10]，能很好展示量子计算确实能够在某些问题的计算能力上远超经典计算机，但在当时看来其算法都是没有应用价值的。但后来Peter Shor 突然发现可以利用 David Deutsch 的这些想法来分解数字，于是提出了现在最有应用价值的算法之一『Shor』，这样一个无用的算法瞬间变成特别有用。这些成果在事先都是没法预测的，只要跟随个人的好奇心，一定会有意想不到的成绩出现。」

参考文献

[1] 量子程序理论及相关问题研究. 冯元, 段润尧,季铮锋, 应明生. 中国计算机学会通讯.2008.07
[2] S.Gay, Quantum Programming Languages: Survey and Bibliography (MathematicalStructures in Computer Science 16(4), 2006)
[3] E. H.Knill, Conventions for quantum pseudocode. Technical Report LAUR-96-2724, LosAlamos National Laboratory, 1996
[4] GödelPrize http://eatcs.org/index.php/goedel-prize
[5] A.Montanaro, Quantum algorithms: an overview. arXiv: 1511.04206v2. 17 Dec 2015
[6]NMRCloudQ: A Quantum Cloud Experience on a Nuclear Magnetic Resonance QuantumComputer. arXiv: 1710.03646v1. 10 Oct 2017
[7] DaweiLu, Keren Li, Jun Li, Hemant Katiyar, Annie Jihyun Park, Guanru Feng, Tao Xin,Hang Li, GuiLu Long, Aharon Brodutch, Jonathan Baugh, Bei Zeng, RaymondLaflamme (2017). Towards quantum supremacy: enhancing quantum control by bootstrappinga quantum processor. arXiv: 1701.01198v1. 5 Jan 2017
[8] X.Fu, L. Riesebos, L. Lao, C. Almudever, F. Sebastiano, R. Versluis, E. Charbon,and K. Bertels, “A heterogeneous quantum computer architecture,” in Proceedings of the ACM International Conference on Computing Frontiers. ACM,2016, pp. 323–330
[9] J.Preskill, “Quantum computing and the entanglement frontier,” arXiv:1203.5813
[10] David Deutsch and Richard Jozsa (1992). “Rapid solutions of problems by quantum computation”. Proceedingsof the Royal Society of London A. 439: 553.