继谷歌和九章后，又一领域有望实现量子优势

光子盒研究院出品 

量子计算的主要目标之一是通过实验证明量子机器比经典机器能够更快地执行某些计算任务。法国和英国的一组研究人员目前使用简单的量子光子学实验装置完成了这一任务。他们的工作表明，量子计算机有可能使用所谓的交互式证明协议来验证NP完全问题的解，并且仅提供关于解的最少的未经验证的信息。

这项工作是最近证明量子优势的几个里程碑之一。在2019年，谷歌（Google）声称自己是第一个完成53个可编程超导量子比特（quantum bit）设备的公司。最近，中国的一个团队宣布他们已经成功执行了“玻色采样（boson sampling）”，这对经典计算机而言是一项艰巨的任务。

然而，与这些先前的结果不同的是，发表在《自然通讯》（Nature Communications）上的这项新研究不仅证明了量子优势（quantum advantage），而且有望在安全量子云计算等应用中发挥作用。

虽然NP完全问题很难有效地求解，但一旦找到解，就可以很容易地进行验证。法国国家科学研究中心（CNRS）和爱丁堡大学（the University of Edinburgh）的团队关注的挑战介于两者之间：当仅提供NP完全问题的一部分解时，验证这个解。

当包含部分解或证明的消息的大小固定时，可以证明用于验证解的经典协议将花费的时间与消息的大小成指数关系增长。相反，对于量子协议，标度是多项式。这就意味着，对于信息量大的消息，一台量子计算机将花费几分钟来验证这个解，而经典计算机可能花费数年。

研究人员用来证明这一点的算法称为交互式证明协议。其中实验装置的一个组成部分充当“证明者”，运用相干光脉冲以量子态的形式发送NP完全问题的部分解。

第二部分充当“验证者”的角色，根据给定的有限信息高精度地确定解是否正确。当在验证者的预期精度以及协议在整个交互过程中可以传递的信息量方面的速度和效率设置一定的界限时，就有可能证明量子算法在做同样的事情时远胜于任何经典的尝试。

结果表明，量子算法能够有效地验证NP完全问题的解，为安全的远程量子计算提供了新的应用。例如，拥有基本量子机器的客户端可以验证他们从功能强大的量子服务器接收到的信息，而无需访问完整的解。

这样的证明系统将给未来的量子互联网中的协议带来很多好处，比如安全识别、身份验证甚至是区块链。爱丁堡大学研究员、论文合著者Niraj Kumar说：“在当前越来越关注数据隐私和安全计算的时代，我们的演示提供了另一个令人信服的证据，即量子计算机在实现安全解方面可以胜过经典计算机。”

文章链接：

https://physicsworld.com/a/quantum-computer-has-the-edge-for-np-verification/

论文链接：

https://www.nature.com/articles/s41467-021-21119-1

—End—

相关阅读：

#光子盒社群招募中#

进入光子盒社群，与我们近距离互动，了解量子领域更多产业、商业、科技动态，领取量子技术产业报告。

现添加社群助手微信Hordcore即可进群 ，与我们一起展望未来！

你可能会错过：