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

4 月 20 日，在机器之心「量子计算」线上圆桌活动中，机器之心邀请到南京大学副教授姚鹏晖做主题演讲《嘈杂量子通信的优势与复杂性》。

机器之心对姚鹏晖副教授的演讲内容做了不改变愿意的整理和编辑，以下是演讲内容：

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

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

理论意义的确是一方面，2005 年《SCIENCE》的一篇文章曾阐明：人类科学目前面临 125 个重大科学问题，涵盖医学、生物、宇宙等多个领域，其中有一个问题就是「计算的边界在哪里」，即什么能计算，什么不能计算。在量子计算领域我们想知道的就是量子计算机的计算边界。

另一方面是出于更现实的考量，即量子计算机不能做的事情。我们可以构造一个量子计算机不能计算的任务，那么这个问题就会很安全。从密码学的角度讲，我们可以设计一个加密协议和加密方案，让量子计算无法破译。过去六七年，密码学界已兴起一个新的研究方向――后量子密码学，专门研究量子计算机无法破译的加密算法。

几年前加州理工的 JOHN PRESKILL 教授提出了 NISQ，称量子计算机已经进入嘈杂中等规模量子计算机阶段，量子计算机未来比特数会越来越多，但是量子噪音在很长一段时间内是无法克服的，并且比特数越多，噪音可能就越大。

那么，有噪音的情况下，量子计算机的优势是否还可以保持？

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

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

1979 年，姚期智教授在经典计算中就提出一个计算模型叫通信复杂性模型，其中对于计算双方（比如两个人），他们要共同计算一个函数，那么他们每个人可能只拿到一部分的输入，所以他们需要通过通信来交换比特。为了计算函数，他们至少需要交换的比特数就被称为叫通信复杂性。大概在 20 世纪 90 年代左右，姚期智教授又提出：如果允许交换量子比特的话，是否可以比交换经典比特？

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

那么，是否存在针对交互量子通信的高效纠错码？量子信息里已经有非常成熟的量子纠错码，但传统的量子纠错码仅仅适用于单向通信，在有噪音的情况下多发一些比特抵消掉这些噪音。

然而在交互通信的情况下，传统的纠错码是不适用的，因为前后的通信是有关联的，如果前面通信出错没有及时纠正的话，后面的通信就是没有意义的。

另外，在交互通信中，由于量子信息是不可克隆的，而且也不能读取，因为读取测量后会发生量子坍缩，继而让发现错误和纠错都变得很困难。

大概从 16 年开始，我和我的博士后导师以及其他几位研究者针对这种交互通信，应对当噪音不高情况的一种非常高效的量子抗噪编码，编码的时间复杂度是 N^2，码率几乎可以达到理论最优。

量子网络中的另一个模型叫量子交互式证明系统，这个相对来说是更加抽象一些的模型。它大概的原理是：我现在有两个机器，一个是计算能力无穷大但不可靠的计算机，另一个是你手上计算能力不行但可靠的经典计算机，现在你可以通过跟计算能力非常强大但不可靠的机器通过交互来提升自己的计算能力。这个其实是计算复杂性过去 20 多年非常核心的一个研究领域。研究者们还进一步设想如果把手上的机器从经典计算机换成量子计算机，交互式证明系统的计算能力是不是可以进一步提升。

大概在 2020 年，这个领域有一个非常大的突破，就是证明当有很多台「不可靠的机器」时，它们之间不能互相通信，但如果你有一台量子计算机的话，通过与这些不可靠机器进行交互，计算能力可以大大提升，甚至完成一些不可计算的函数，比如停机问题。这个其实是非常反直觉的，因为经典计算机的计算能力再强也不可能解决停机问题。

在安全方面，如果要把计算委托给两个机器去计算，但是这两个机器不一定可靠，你又怎么能委托给它们计算呢？这里就有两个目标：要提升计算能力，还要保证计算是安全可靠的。这方面在 18 年也有一个非常大的突破，发现经典计算机通过与不可靠的量子计算机的交互，也可以让经典计算机也实现量子计算机的能力。

上述优势都是基于整个通信模型没有噪音的基础上。如果一个交互证明系统有噪音怎么办？如果是单向通信，可以应用前面所说的纠错方法解决。

我们的工作考虑了一个非常简单的情形，即两台机器共享任意多带噪音的 EPR 态。

当噪音为 0（不带噪音）的情况下，前面别人的工作已经证明了这个系统是不可判定的，也就是说它的计算能力是等在于停机问题，你可以做一些不可判定的问题。

如果在像共享的 EPR 态带噪音的情况下，它的计算能力是否还是等价于停机问题，也就是说它是不是还是不可判定的，换句话说，这个模型是否对于噪音是鲁棒的。

去年我和我的学生一起证明了一件事情，如果它共享 EPR 态也是带有噪音的话，那么这个系统就变成可判定的，计算能力下降了，因此量子交互式证明系统的策略是对噪音不鲁棒。

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

另外我们也重点研究量子复杂性理论，包括量子通信复杂性、量子电路复杂性和分析方法在量子计算理论中的应用。我们希望应用数学分析方法研究量子计算理论的问题。欢迎感兴趣的学生加入我们团队。