南京大学副教授姚鹏辉：噪声量子通信的优势与复杂性

机器之心对姚鹏辉副教授的演讲内容进行了编排，没有改动。以下为演讲内容：

我今天的分享是关于我过去几年在嘈杂的量子通信方面的工作。我的研究方向主要是量子计算的复杂性。一般来说，它包含两个问题：一是量子计算机能做什么，二是量子计算机的能力边界。

首先大家比较关心的是量子计算机相对于经典计算机的优势：

在算法方面，量子计算机在时间复杂度方面具有优势；

在安全方面，比如量子密钥分发，中国有很大优势；

沟通优势。

用外行的话来说，量子计算的复杂性是量子计算机无法做到的。你可能有一个疑问：如果你不做计算理论，你为什么要关心量子计算机不能做什么？

理论意义确实是一方面。《科学》2005年的一篇文章指出，人类科学目前面临125个重大科学问题，涉及医学、生物学、宇宙等诸多领域。where”，即什么可以计算，什么不能计算。在量子计算领域，我们想知道的是量子计算机的计算边界。

另一方面是更现实的考虑量子计算机对比特币摧毁，量子计算机无法做到的事情。我们可以构建一个量子计算机无法计算的任务，并且这个问题是安全的。从密码学的角度来看，我们可以设计量子计算无法破译的加密协议和加密方案。在过去的六七年里，密码学界出现了一个新的研究方向——后量子密码学，专门研究量子计算机无法破译的加密算法。

几年前，加州理工学院的 John Preskill 教授提出了 NISQ，称量子计算机已经进入有噪声的中等规模量子计算机阶段，未来量子计算机的位数会增加，但量子噪声无法克服很长时间。并且位数越高，噪声可能就越高。

那么，在存在噪声的情况下，量子计算机的优势还能保持吗？

这个问题很早就研究过了。2000年之前，有量子纠错码和量子容错计算。他们实现了量子电路的一些抗噪声目标，并在存在噪声的情况下保持了量子计算机的优势。.

在通信模式中，这样的优势还能保持吗？我们知道小型量子计算机越来越成熟，物理学家设想通过网络将这些计算机连接在一起，利用通信技术形成网络。在网络通信的情况下，一方面要保持计算的优势，另一方面也要考虑通信的优势。交换量子比特比交换经典比特更好吗？

1979年，姚启智教授提出了一种计算模型，称为经典计算中的通信复杂度模型，其中双方（比如两个人）要共同计算一个函数量子计算机对比特币摧毁，那么每个人可能只能得到一部分输入，所以他们需要通信来交换比特。为了计算一个函数，它们需要交换的最小位数称为通信复杂度。1990年代左右，姚启智教授还提出：如果允许量子比特的交换，能比得上经典比特的交换吗？

后来人们发现了一系列问题，比如量子指纹、隐藏匹配、量子神经网络等。量子计算通过交换量子比特比交换经典比特可以节省很多。因此，在通信复杂度方面，量子通信目前具有无条件的计算优势，但这些优势也是基于通信噪声。在存在噪声的情况下，需要交换更多的量子比特才能保持原有的优势。

那么，交互式量子通信有没有高效的纠错码呢？量子信息中已经有非常成熟的量子纠错码，但传统的量子纠错码只适用于单向通信。在噪声的情况下，会发送更多的比特来消除噪声。

但是，在交互通信的情况下，传统的纠错码是不适用的，因为之前的通信是相关的，如果之前的通信错误没有及时纠正，后续的通信就没有意义了。

另外，在交互通信中，由于量子信息不可克隆，无法读取，由于读取测量后会发生量子坍缩，因此难以检测和纠正错误。

从大约 16 年前开始，我的博士后导师和其他几位研究人员就在研究这种交互式通信，一种在噪声不高的情况下非常高效的量子抗噪声编码，编码时间复杂度为 n^2 ，代码率几乎可以达到理论最优值。

量子网络中的另一个模型叫做量子交互证明系统，是一个相对抽象的模型。它的总原理是：我现在有两台机器，一台是算力无限但不可靠的计算机，另一台是算力不足但可靠的经典计算机。可靠的机器通过交互来提高它们的计算能力。这实际上是过去 20 年计算复杂度研究的一个非常核心的领域。研究人员进一步设想，如果将手头的机器从经典计算机替换为量子计算机，是否可以进一步提高交互式证明系统的计算能力。

2020年前后，这个领域会有一个非常大的突破，那就是证明当有很多“不可靠的机器”时，它们之间是无法通信的，但是如果你有一台量子计算机，通过与这些不可靠的机器进行通信，可以进行交互，可以大大提高计算能力，甚至可以完成一些不可计算的功能，比如关机问题。这其实很反直觉，因为再强大的经典计算机，也不可能解决停机问题。

在安全方面，如果你想把计算委托给两台机器，但是这两台机器不一定可靠，你怎么能把计算委托给它们呢？这里有两个目标：提高计算能力，同时确保计算安全可靠。2018年这方面也有非常大的突破，发现经典计算机也可以通过与不可靠的量子计算机交互来实现量子计算机的能力。

上述优点是基于整个通信模型是无噪声的。如果交互式证明系统有噪音怎么办？如果是单向通信，可以应用上面提到的纠错方法来解决。

虽然机器不能交换信息，但它们可以共享一些量子纠缠态。如果共享量子纠缠中有一些噪声怎么办？例如，如果他们共享一个嘈杂的 EPR 状态，计算能力会受到影响吗？

我们的工作考虑了一个非常简单的情况，其中两台机器任意共享许多嘈杂的 EPR 状态。

当噪声为0（无噪声）时，别人之前的工作已经证明这个系统是不可判定的，也就是说它的计算能力等于关机问题，你可以做一些不可判定的问题。

如果在像共享EPR状态这样的噪声的情况下，它的计算能力是否仍然等同于停机问题，即是否仍然不可判定，换句话说，模型是否对噪声具有鲁棒性。

去年我和我的学生证明了一件事，如果它的共享 EPR 状态也有噪声，那么系统变得可判定，计算能力下降，所以量子交互证明系统的策略是处理噪声不鲁棒。

最后，我将花一点时间介绍我的研究团队。我们团队的研究方向主要集中在量子算法和量子通信协议，包括量子分布式算法、量子信息论、量子信息压缩和抗噪声编码。

此外，我们还专注于量子复杂性理论，包括量子通信复杂性、量子电路复杂性以及解析方法在量子计算理论中的应用。我们希望将数学分析方法应用于量子计算理论的问题。欢迎有兴趣的同学加入我们的团队。

© 结束