张家琳：量子算法——算法设计的新大陆？| CNCC专家谈

CNCC早鸟票火热进行中，限期优惠，早鸟票购票成功更有机会获得炙手可热的“CCF会员之夜”入场资格，敬请尽快报名！

随着量子计算热度的不断攀升，不仅在学术领域，公众媒体上关于量子计算的讨论也日益增多。诸如“量子计算具备怎样的计算能力？量子计算可以应用于哪些领域？效果如何？”以及“当前量子计算机能制造多少个量子比特？”等问题被热烈讨论。量子计算潜在的强大计算能力的背后，量子算法的理论研究发挥着基石性的重要作用。

那么，什么是量子算法？量子算法是一种利用量子力学中的独特特性来加速计算的方法。与传统基于经典图灵机模型的算法设计思路完全不同，量子算法充分利用了量子力学中的量子叠加、量子纠缠等特性来进行算法设计。（上图为Google量子处理器和IBM Osprey系统）。

在常见的量子算法中，我们通常使用量子比特和基于量子比特的量子门来描述算法过程，类似于经典计算中用与或非门来描述逻辑电路并进行计算。然而，相比经典逻辑电路，量子算法或者说量子电路有着截然不同的物理内涵，并由此为算法设计领域开辟了一片新的大陆。在经典逻辑电路中，经典比特是二进制表示，然而在量子算法中，每个量子比特都可以处于|0⟩态与|1⟩态的叠加态中，因此相对经典计算，单个量子比特就可以蕴含远超经典比特的信息量。同时，经典逻辑电路的基本逻辑运算只有与或非三种，而在量子电路中，则有更为庞大的量子门家族，如基于单比特的Pauli门（X门、Y门、Z门）、旋转门、相位门、测量门，基于双比特或多比特的各种控制门，如CNOT门，Toffoli门或是任意门等等。在不同的硬件实现方案中，哪些门能够被实现或者是被更精准的实现都是不同的，这也为量子算法在不同硬件中的落地实现带来了更为复杂的研究场景。

作为一种从根本上和传统经典计算不同的新型计算方式，量子计算已经展示出超越经典计算的计算潜力。同时，随着近期基于各种不同路线的量子计算硬件被提出并实现，量子计算的研究发展已经越来越接近在真实应用场景中产生颠覆性的影响。在诸如密码学、人工智能、生物制药、金融工程等多个领域，有越来越多的专家学者关注量子计算的快速发展。而在这些焕然一新的突破性进展背后，量子算法作为其理论基础起到了基石性作用。如果人们相信量子力学，那么根据现在的量子算法理论，就有充分的理由相信量子算法可以在部分问题上做得远比经典算法好。这种信心也进一步推动了量子计算领域火热的研究浪潮。

最著名的两个量子算法莫过于求解大整数分解质因数问题的Shor算法和求解无结构搜索问题的Grover算法。大整数分解问题是指给定一个很大的整数，将其分解为若干个素数的乘积。这个问题目前还不存在多项式时间能求解的经典算法，其中多项式时间指的是算法的运行时间相对大整数的位数是多项式量级的。Peter Shor在1994年给出了这个问题的多项式时间复杂度的量子算法，实现了量子算法相对目前最好经典算法的指数量级加速。因为大整数分解问题目前是否是NP-完全问题仍然是未知的，Shor算法并不能直接说明量子计算有求解NP-完全问题的计算能力，但是大整数分解问题在密码学和数论领域却有着极其深远的影响。它的难解性是RSA等公钥密码算法的理论基础，如果该问题有多项式时间算法，则意味着基于它的公钥密码体系甚至于整个信息安全体系都将产生毁灭性的严重影响。

无结构搜索问题则是指在一个未进行排序的数据库中搜索某个特定元素。显而易见，经典算法至少需要与数据规模成线性量级的运行时间来完成这个任务，然而Lov Grover在1996年提出了一个出人意料的量子算法，只需要在O(√N)的时间内就可以完成对特定元素的搜索，其中N是数据库的规模。虽然Grover算法的加速效果只是平方量级的，而不是指数量级，但一方面由于搜索问题在各种应用场景都极为普遍，另一方面这是在理论上可严格证明的超越经典计算极限的量子算法，因此这个算法的重要性依然是毋庸置疑的。

近些年，人们提出了更多的量子算法来应对不同的应用场景。如求解线性方程组的HHL算法，虽然该算法在输入方式上仍然有一定的争论，但确实在求解方程组的计算过程中做到了相对经典计算的指数加速。另一大类最近很热门的量子算法则是经典量子混合算法，包括量子近似优化算法（QAOA）、变分量子本征求解器（VQE）、变分量子模拟（VQS）等都属于这一大类。由于目前量子计算硬件还不能支撑太多的量子比特和量子门操作，完全依靠量子计算来解决实际应用问题依然遥远，因此这类结合量子计算和经典计算优点的算法设计框架越来越受到研究者的青睐。它通过只让量子计算系统完成少量经典计算难以处理的计算问题的方法，极大减少了对量子计算资源的依赖，在量子化学、金融工程等领域开始有了系统性的研究。（下图是变分量子算法的示例）

从狭义角度来看，量子算法领域会继续致力于研究各类基础计算问题的量子算法设计与分析，以期从中找到更多超越经典算法性能的例子。尽管这听起来和经典算法领域的研究方式类似，只是换了一种计算模型而已。然而，从更广义的角度来看，正是由于这种全新的计算模型，人们目前对它的理解还远远不够，这就为算法设计领域带来了一块全新的大陆：所有在经典领域研究过的计算问题都可以被放在量子视角下重新进行审视；所有经典领域的通用设计范式也都可以考虑是不是有对应的量子计算版本。或者说，量子算法是不是能有全新的设计范式？什么样的计算问题会成为在Shor算法、Grover算法等这些算法之后新的量子算法杀手锏？哪个量子算法会首先在量子硬件上实际落地并解决经典无法有效求解的实际问题？在量子算法所开辟的这片新大陆中，我们拥有无限可能！期待更多的研究者投入其中，共同努力创造新的未来。

本年度CNCC上的技术论坛“量子算法：算法设计的新大陆”，我们邀请了六位业内一线的知名学者济济一堂，分享他们最新的量子算法研究工作，并对量子算法的未来进行深度研讨，敬请关注。