文/王 楠 王国强

我们正在经历一场智能革命，而这场智能革命建立在算法的基础上。无论是智慧城市、智能制造、智慧医疗等宏大愿景，还是自动驾驶、智能机器、虚拟现实等前沿应用，抑或是智能购物、智慧出行、智能娱乐等生活日常，“智能”的实现都离不开算法。可以说，我们生活在一个算法无所不在的时代。

古代算法思想及其发展

人工智能时代的算法

量子时代算法的发展

根据摩尔定律，计算机芯片的性能每18个月翻1番。然而，随着摩尔定律逼近极限，经典计算的算力增长即将遭遇瓶颈。量子计算是利用量子态的相干性、叠加性、纠缠性等量子力学特性进行信息运算、保存和处理操作的新型计算模式。量子计算可以突破经典计算机的算力极限，被认为是未来30年最有可能改变世界的颠覆性技术之一。

●量子计算理论

1979年，美国阿贡国家实验室物理学家贝尼奥夫（Paul Benioff）提出了第一个量子计算机模型。1980年，苏联数学家马宁（Yuri Manin）在其著作《可计算与不可计算》中同样阐述了量子计算的概念。1981年，贝尼奥夫和美国物理学家费恩曼（Richard Faynman）在麻省理工学院举行的第一届计算物理会议上就量子计算发表演讲。贝尼奥夫表示计算机可以在量子力学定律下运行，费恩曼表示使用经典计算机难以有效模拟量子系统的演化，并提出了量子计算机的基本模型。贝尼奥夫、马宁和费曼奠定了量子计算的理论基础。

1985年，英国牛津大学教授多伊奇（David Deutsch）首次提出了量子图灵机模型，并设计了第一个量子算法Deustch算法。然而，Deustch算法没有确定性，其成功的概率仅有50%。1992年，多伊奇和英国剑桥大学教授乔萨（Richard Jozsa）在早期Deustch算法基础上提出了有确定性的Deutsch-Jozsa算法，并将其推广到n个量子比特的Deutsch问题。Deutsch-Jozsa算法首次实现了对经典算法的指数级加速，奠定了量子算法的基本思想。然而，限于当时的理论和技术水平，此时量子算法还停留在纸面设想阶段。

●量子计算核心算法

Shor算法、Grover算法和以HHL算法为代表的对偶量子算法是量子计算的三大核心算法。1994年，贝尔实验室的美国数学家肖尔（Peter Shor）基于量子傅里叶变换提出了针对整数分解问题的大数质因子分解算法（又称为Shor算法）。

1994年，美国数学家肖尔提出针对整数分解问题的Shor算法

Shor算法从理论上展示了量子计算机能够把质因数分解问题的求解从指数时间降到多项式时间，可用于破解目前通用的计算机加密方案——RSA加密算法。假如超级计算机破解一个2048位的RSA密钥需要数十亿年，那么使用Shor算法的量子计算机仅需要几分钟。这意味着依赖RSA密钥机制的银行、网络和电子商务系统在理论上不再安全。然而，Shor算法在量子计算机上的实验实现一直是国际公认难题。2008年，中国科技大学教授潘建伟的团队与英国牛津大学合作，首次在光量子计算机上实现了Shor量子分解算法，标志着我国光学量子计算研究达到了国际领先水平。

1996年，贝尔实验室的美国计算机科学家格罗弗（Lov K. Grover）基于量子黑盒加速工具提出了针对乱序数据库的量子搜索算法（又称为Grover算法）。Grover算法从本质上解决了函数求逆的任务，使无序数据库中“大海捞针”成为可能，其在密码学上的应用可以加速对称密钥算法的破解。然而，原始的Grover算法只能以一定概率输出正确结果，在一些特殊情况下输出错误结果的概率较大。2001年，清华大学教授龙鲁桂利用相位匹配的技巧将Grover算法的成功概率提高到100%，即龙算法。

Shor算法和Grover算法提出之后，量子算法研究进展缓慢。2003年，肖尔发出著名的“肖尔之问”，即为什么难以发现更多的量子算法。肖尔对这一问题的解释是，量子计算机的运行模式与经典计算机不同，以至于经典算法中的构造设计技巧和直觉在量子计算过程中不再成立。

2002年，龙鲁桂提出酉算符线性叠加的对偶量子算法。酉算符是泛函分析中定义在希尔伯特空间上的有界线性算符，Shor算法和Grover算法都是通过酉算符对信息进行处理。由于酉算符只允许乘除运算，经典计算中的许多技巧不能用于量子计算。对偶量子算法通过引入辅助比特以实现非酉操作，这使酉算符的加减乘除四则运算成为可能，从而解决了经典算法转化为量子算法的问题。2009年，美国麻省理工学院的哈罗（Aram W. Harrow）、哈希迪姆（Avinatan Hassidim）和劳埃德（Seth Lloyd）基于酉算符线性叠加提出可求解线性方程组的HHL算法。求解线性方程组是很多科学和工程问题的核心，HHL算法相对于经典计算有指数加速的效果，因此在机器学习、数据拟合等多种场景中展示出巨大优势。

●量子人工智能算法

量子叠加和量子纠缠等量子力学特性使量子算法非常适于解决人工智能和机器学习研究中核心的最优化问题。所谓“最优化”是指在给定预期结果和约束条件的情况下，从一组可能选项中找到问题最优解的过程。最优化问题是应用数学和计算机科学领域的重要基础研究之一，其理论与方法广泛用于工业生产、工程设计与管理、交通运输、经济决策、市场管理等关乎国计民生的重要领域。1995年，美国计算机科学家卡克（Subhash Kak）首先提出量子神经计算的概念。同年，英国科学家米尼尔（Tamaryn Menneer）和纳拉亚南（Ajit Narayanan）将量子信息学中的多体观点应用到单层人工神经网络，提出了量子衍生神经网络，显示出在处理分类问题上的有效性。2000年，韩国科学家韩国贤（Kuk-Hyun Han）等采用量子比特编码染色体，提出了具有更强并行搜索能力的量子遗传算法。2005年，日本科学家幸田典明（Noriaki Kouda）等将量子位引进神经元定义，提出了量子位神经网络，仿真试验表明该神经网络具有良好的学习能力。2006年，谷歌眼镜项目联合创始人奈文（Hartmut Neven）在D-Wave量子计算机上开发了第一个结合了量子算法和机器学习的图像识别系统。近年来，量子人工智能算法发展迅速，出现了量子卷积网络、量子自然语言处理、量子生成模型等新型算法。以IBM、谷歌为代表的科技企业纷纷加强了量子人工智能在新材料设计、药物设计以及化学反应模拟等领域的算法研究。2017年至2020年，IBM、IonQ和谷歌公司先后利用量子计算模拟出氢化铍、水分子和二氮烯分子，标志着量子计算在模拟和发现小分子化合物上迈出重要一步。2021年1月，谷歌公司与德国医药企业勃林格殷格翰联合成立量子实验室，致力于实现对蛋白质、核酸、多糖等生物大分子的模拟，有望开启在原子、分子层面理解生命和研发新药的新模式。

算法是人工智能的基础。当前，数据和算力已经不再是人工智能发展的主要瓶颈，人工智能的创新主要就是算法的创新。随着人工智能在国家治理、经济发展、科技创新、医疗保健、教育培训，乃至日常生活的应用日益广泛和深入，算法越来越重要。在这样的背景下，只有不断探索新的算法机制，发展新的算法应用，开发新的算法模型，发掘和培养算法人才，才能为推动智能社会发展提供强劲动力。

王楠，中国科协创新战略研究院博士后，主要研究方向为科技战略和科技政策。

王国强，中国科协创新战略研究院研究员，博士，主要研究方向为科技史、科技政策和科技传播。