数学家Peter Shor：量子计算机威胁到网络加密，只是时间问题
The following article is from Nature自然科研 Author Nature自然科研
而在25年前，美国应用数学家Peter Shor提出Shor算法，证明了如何让量子计算变得可行，量子计算会如何威胁到数据。
撰文 | Davide Castelvecchi
● ● ●
上世纪80年代，当物理学家首次提出量子计算机的想法时，它们听起来就像是理论上很精彩、但可能注定只能停留在论文里的概念。到了1995年，也就是25年前的10月，数学家 Peter Shor 发表的一篇论文 [1] 改变了人们的看法。
Shor在论文中证明了如何克服量子计算机的一个关键问题。量子计算机以量子比特为单位处理信息——量子比特对应经典比特，但能同时表示0和1。已知量子态对噪声非常敏感，这会造成信息丢失。Shor提出的误差修正技术能检测到噪声导致的错误，带来了一种让量子信息更抗噪的方法。
Shor目前就职于麻省理工学院，同时也是一位出版过作品的诗人。1994年，他第一次发现了 [2] 使用理论量子计算机的方法，震惊了物理学界和计算机科学界——这种方法可能有用但也令人担忧。他写了一种算法，可以让量子计算机以闪电般的速度将整数分解质因数。今天的大部分网络流量的安全性都是由基于大质数的加密技术来保证的。破解这些密码很难，因为经典计算机分解大整数质因数的速度很慢。
如今，量子计算机已经成为现实，但它们分解超过两位数数字的能力依然处于初级水平。但是，量子计算机威胁到网络加密只是一个时间问题。
最近，Shor在接受《自然》杂志采访时，就如何看待自己研究的影响力，网络安全的未来将走向何方等分享了自己的看法。
在你的分解质因数算法出现前，量子计算机是否只停留在理论层面？
我的论文确实给了大家一种印象，就是这些计算机能做些有用的事。计算机科学家 Daniel Simon 在我的结果出来前，解决了他遇到的一个问题，证明了量子计算机（比普通计算机）快了好几个指数级。但即使有了 Simon 的算法，人们依然不清楚量子计算机能有什么用。
你公布这个分解质因数算法时，人们有何反应？
刚开始，我只得到了中间结果。1994年4月，我在[当时我就职的新泽西州]贝尔实验室（Bell Labs）做了一次关于它的演讲。消息传得很快，那个周末，计算机科学家 Umesh Vazirani 给我打了个电话。他说：“我听说你能用量子计算机分解质因数，请告诉我是如何做到的。” 那时候，我其实还没有解决分解质因数的问题。我不知道你听说过儿童游戏 “打电话” 没有，但不知怎的，五天时间里，我的研究结果就变成了分解质因数，因为人们都在这样传。在那五天里，我正好也解决了那个问题，所以我能告诉Umesh如何做。
我的论文还没写完的时候，就有各种各样的人来问我要论文，所以我只能把还不完整的草稿先寄给他们。
但是许多专家还是认为量子计算机会在完成计算前丢失信息？
有一个反对意见是说在量子力学中，如果你测量一个系统，你就会不可避免地干扰它。我证明了如何在测量错误的同时不测量计算，这样你就能纠正错误，而不会破坏整个计算。
在我那篇1995的纠错论文发表后，一些怀疑人士也开始相信量子计算或许是可行的。
纠错依赖 “物理” 和 “逻辑” 量子比特。这两者有什么差别？
为量子计算机写算法时，假设的是量子比特是无噪的，算法中描述的这些无噪量子比特就是逻辑量子比特。实际上量子计算机中没有无噪量子比特，事实是，如果我们在不进行任何降噪的情况下运行算法，几乎必定会出现错误。
物理量子比特是量子计算机的其中一种噪声量子比特。如果要在不出错的情况下运行算法，我们就要利用物理量子比特编码逻辑量子比特，使用一种量子纠错码。据我们所知，实现这一步的最好做法要求相当高—— 每个逻辑量子比特都需要许多物理量子比特。
要计算出这项技术需要多少量子比特是一项非常复杂的工作。如果你想用表面码（目前最好的候选对象）构建一个量子计算机，每个逻辑量子比特大约需要100个物理量子比特或更多。
2019年，谷歌用54量子比特的量子计算机解决了一个经典计算机几乎不可能完成的任务，这也是对 “量子优越性” 的首次演示。您对此有何评价？
它肯定是一个里程碑。它表明了量子计算机可以比经典计算机做得更好—— 至少是在一些人为设计的问题上。谷歌确实进行了一些宣传。但他们也有一台非常值得称道的量子计算机。但这个计算机依然需要改进，才能做出有意思的事来。还有初创公司IonQ，他们看起来好像能构建一个在某种程度上超过谷歌或IBM的量子计算机。
如果量子计算机能做大数质因数分解，它们就能破解 “RSA” ——无处不在的网络加密系统。
是的，但是最先破解RSA的人不是来自NSA（美国国家安全局），就是来自其他大型机构。这些计算机一开始会很慢。比如，如果你有一台只能一小时破解一个RSA密钥的计算机，那么任何不属于优先事项或国家安全风险的东西都不会被破解。相比看你的邮件，NSA的量子计算机有更重要的事情要做。
有没有能取代RSA的密码系统，即使在量子计算机时代（“后量子密码”）也是安全的？
我认为已经有能取代RSA的后量子密码系统了。RSA不是现在的大问题，现在的大问题是还有其他方法可以破坏网络安全，比如恶意编程的软件、病毒、向并非绝对诚实的一方发送信息等。我认为用安全的后量子密码系统取代RSA的唯一阻碍是意志和编程时间。我认为我们已经知道要如何做到这一点，只是不清楚是否能及时做到。
我们是否有被突然袭击的风险？
是的，人们已经为解决千年虫问题（Year 2000）投入了大量精力。你需要付出大量努力才能过渡到后量子时代。如果我们等得太久，就太迟了。
原文以Quantum-computing pioneer warns of complacency over Internet security 为标题发表在 2020年10月30日的《自然》的News Q&A版块上，《知识分子》获授权转载中文译文。
制版编辑 | 卢卡斯
点击阅读原文，获取本文英文原文。