量子计算应用前景广阔，但需更高效算法

文／田国敬 孙晓明

量子力学是上世纪最伟大的科学发现之一，其从根本上改变了人类对经典物质结构及其相互作用的理解。量子调控技术的进步有望推动第二次量子革命，从而对未来社会产生本质的影响。

量子计算旨在利用量子力学特性来获得比经典计算在性能上潜在的提升，并已经在一些计算问题上展示出了超越经典计算的能力。首先，不同于经典计算中的比特只能够处在0或1之中一个确定的状态，微观粒子可以同时处于0和1——即0与1叠加的状态。例如思想实验中，在黑箱中的薛定谔猫处于生与死的叠加状态，即同时是活的猫也是死的猫。但是一旦打开黑箱，这一叠加的状态会塌缩为一个经典的状态，猫只能是生或死中确定的一种，即“观测即改变”。

此外，不同于经典世界中两个比特之间的概率相关性，微观世界中相距遥远的两个微观粒子可以处于纠缠的状态，观测其中一个可以瞬时影响另一个的状态，这一过程的一个形象的比喻就像一对双胞胎虽然分隔在两地却能与对方有“心灵感应”。量子叠加和量子纠缠已经被物理学家通过实验多次反复验证。

小学生可以很容易地知道11×17=187，也能够计算出12347×34589的结果，对于再大一些的数相乘（例如两个有100位数字的整数），计算机仍然可以立即给出答案。但是如果给一个有200位数字的整数，想要把它分解成为两个100位整数的乘积，问题一下就困难了许多。这个问题被称为整数素因子分解问题，是目前广泛使用的RSA公钥密码（1977年由三位学者一起提出的，RSA是他们三人姓氏开头字母的缩写）的根基。

目前，在经典计算机上最好的算法需要指数量级的时间：在最快的超级计算机上分解一个有512位数字的整数需要数周时间，而分解一个有1024位数字的整数需要的时间将是一个天文数字。因此，通常认为RSA公钥密码目前是安全的。

1994年，贝尔实验室的彼得·肖尔（Peter Shor）提出了一个整数素因子分解的量子算法，可以在量子计算机上花费多项式量级时间内完成整数的素因子分解，例如分解1024位数字的整数在通用量子计算机上只需要几秒。这动摇了RSA公钥密码的理论根基，给密码安全带来了潜在的威胁。需要指出，这种威胁目前仍是理论层面的，要想破解1024位RSA公钥密码需要3000个以上的逻辑量子比特，而现阶段的超导量子硬件设备大约可以达到50—70个物理量子比特。

另一方面，我们也需要看到量子实验技术的发展非常迅速，事实上从研制5个超导量子比特到研制出50个超导量子比特只用了不到三年的时间。IBM等公司宣称，将在2023年实现超过1000个量子比特的量子硬件设备。或许未来突破实验瓶颈之后，不需要太久具有更多量子比特的量子硬件也将被研制出来。此外，肖尔量子算法主要针对整数素因子分解问题和离散对数问题。密码学家很早就在寻找基于其他困难问题的密码方案，即后量子密码体系。但同样是否也会有针对这些问题的快速求解量子算法呢？学者们仍在积极探索。

除了肖尔量子算法之外，另一个经常被人们提到的量子算法是格罗弗量子搜索算法，该算法由同样来自贝尔实验室的洛夫·格罗弗（Lov Grover）提出，其利用了量子相干特性来加速在无结构的数据库中搜索目标，比经典搜索算法在时间上能够有开平方数量级加速。譬如，有1亿条无索引的记录需要被处理，假设处理每条记录的平均时间需要0.01秒，经典算法总的处理时间大约需要12天，而量子算法只需要约100秒。

虽然格罗弗算法没有像肖尔算法那样能够提供指数级别加速，但是由于搜索问题的应用范围和场景要比整数素因子分解问题广泛得多，因此学者们在这一方向进行了非常系统和深入的研究。例如：量子振幅放大算法能够集成多个弱的算法变成一个更强的算法；量子局部搜索算法能够更快地找到局部最优解；量子游走算法能够加速经典的随机游走算法等。该算法也可以直接被用来破解密码或求解NP（即非确定性图灵机在多项式时间内可求解的问题）困难的组合优化问题。

除了上述两个经常被提及的量子算法之外，学者们还研发了多个重要的量子算法，这些量子算法的提出，为量子特性在计算领域的应用提供了非常有意义的指导和示范。虽然学者们已经研发出了多个重要的量子算法，但是相较于浩如烟海的经典算法，目前的量子算法可能还只是冰山一角。

量子计算要想充分发挥出其优势，既需要量子硬件的支撑，也需要量子算法的创新。在中大规模量子硬件设备即将到来之际，我们必须设计更多更高效的量子算法来解决数学、物理、化学、医药、金融等关乎国计民生的诸多重要问题，为人民群众的美好生活作出贡献。

目前，量子计算已经成为世界各国学界和业界竞相争夺的新高地。在一些专门设计的任务上，量子优势已经被实验验证。如何深刻理解量子特性本身，并设计更高效实用的量子算法，针对实际应用问题去展示更具现实意义的量子优势，在真实量子硬件上实现实用量子算法的编译优化和高效运行，以及如何克服现阶段实验遇到的量子比特保真度低、相干时间短、噪声和串扰高等困难和挑战，研制中等规模量子硬件设备并能够稳定运行，将是未来一段时间需要重点突破的瓶颈。