｜量客江湖系列01｜破RSA大盗——Peter Shor
20世纪80年代，物理学家们首次提出量子计算机的构思时，听起来十分乐观，但只能通过文字的方式来呈现。
后来在1995年，也就是25年前的上个月，应用数学家Peter Shor发表了一篇论文，改变了当时的一切。
图1｜Peter Shor（来源：TQD）
Peter Shor的论文
Shor的论文展示了量子计算机是如何克服一个关键问题的。这些机器将以量子比特的形式处理信息，量子比特是普通比特的量子版本，可以同时处理0和1。
但众所周知，量子态易受到噪音的影响，从而导致信息丢失。他的纠错技术（用于检测噪声引起的错误）展示了如何使量子信息更加可靠。
图2｜Peter Shor在1995年发表的论文（来源：美国物理学会）
Shor目前在剑桥的麻省理工学院工作，同时，他也是一位出版过诗集的诗人。
早在1994年，他就发现了如何使用量子计算机的模型进行计算，这让物理学界和计算机科学界感到震惊。
他提出了一个算法——质因数分解算法，可以让量子计算机以闪电般的速度将整数分解成质因数。今天的大多数互联网流量是基于大质数的加密技术保护的。**这些代码十分困难，因为经典计算机在分解大型整数时很慢。
图3｜Peter Shor在1994年发表的论文（来源：电气电子工程师学会）
量子计算机现在已经成为现实，尽管它们还不足以计算两位数以上的数字。但量子计算机威胁互联网加密只是时间问题。
访谈内容
《自然》杂志采访了Shor，询问了关于他的工作所带来的影响——以及互联网安全的发展趋势。
- 在你的质因数分解算法出现之前，量子计算机纯粹就是为了满足理论层面的好奇心吗？
我的论文的确使人们明白，这些机器可以做一些有用的事情。
计算机科学家Daniel Simon，在我得出我的结论之前，他就解决了一个他提出的问题，该问题表明量子计算机（比普通计算机）快得多。
但是即使采用Simon的算法，也无法得知这些机器是否可以发挥它们的用处。
- 在宣布了你的质因数分解算法后，人们的反应如何？
起初，我只得到了一个不完整的结果。后来，在1994年4月，我在贝尔实验室做了一个关于这个选题的报告。
消息传得非常快，那个周末，计算机科学家Umesh Vazirani就给我打了电话说，“我听说你可以在量子计算机上进行质因数分解，告诉我你是怎么做到的。”
图4｜Umesh Vazirani（来源：伯克利工程学院）
那时，我其实还没有真正解决质因数分解的问题。但很神奇的是，报告结束的五天内，我的结果在人们的奔走相告中，变成了质因数分解成功。而在这五天里，我也确实解决了分解的问题，于是我就可以告诉Umesh我是怎么做到的了。
当时人们都在向我索要我还未完成的论文，所以我只能把粗稿拿给他们看了。
- 但是仍有许多专家认为，量子计算机会在完成计算之前就丢失信息是吗？
其中一个反对意见是，在量子力学中，如果你测量一个系统，你会不可避免地干扰到它。
我演示了如何在不测量计算的情况下测量误差——然后你就可以修正误差，而不破坏计算。
在我1995年发表了关于纠错的论文之后，一些怀疑论者也确信量子计算是可行的。
- 纠错依赖于“物理”和“逻辑”量子比特，这两者间的区别是？
当你写下一个量子计算机的算法时，你会假设量子比特是无噪声的。这些无噪声的量子比特就是逻辑量子比特，而我们的量子计算机中不存在没有噪声的量子比特。
事实上，如果我们试图在没有噪声干预的环境下，运行我们的算法。那错误的发生，是不可避免的。
物理量子比特是量子计算机中的含噪声的量子比特之一。为了在运行我们的算法时，不出现任何错误，我们需要使用物理量子比特对逻辑量子比特进行编码，这其中会用到量子纠错代码。
图5｜量子比特（来源：medium）
而我们所知道的最好的方法，是有相当大的开销的，此方法为每个逻辑量子比特都提供了诸多物理量子比特。
要计算出这项技术还需要多少量子比特是相当复杂的。如果你想用表面码（目前最佳选项）来建造一台量子计算机，那么每一个逻辑量子比特，大约需要100个物理量子比特来支持，甚至更多。
- 在2019年，谷歌展示了其“量子优势”——即54个量子比特的量子计算机，它可以解决一个在经典计算机上耗时冗长的问题，你的反应是什么？
这绝对是一个里程碑。它表明，量子计算机可以比经典计算机做得更好——至少在以人为主导因素的问题上。
即便谷歌做了一些宣传活动，但毋庸置疑的是，这台量子计算机的确让人印象深刻。
在它能创造出奇迹之前，还需要一些完善工作。另外，初创公司IonQ制造的量子计算机，在某种程度上可能比谷歌和IBM的都要好。
- 当量子计算机可以分解大质数时，它们就可以**无处不在的互联网加密系统“ RSA”，这点你如何看待？
是的，但是第一个**RSA的人，要么是NSA（美国国家安全局），要么是一些其他大型机构。
一开始，这些计算机运行会非常缓慢。如果你有一台每小时只能**一个RSA**的计算机，那你肯定将其用于**国家级别安全风险的信息。
比起用量子计算机阅读普通大众的电子邮件，美国国家安全局有更重要的事情可以做——他们将阅读中国大使的电子邮件，哈哈。
- 有没有一种加密系统可以取代RSA，而且在量子计算机时代也是安全的——即“后量子加密”？
我认为我们会有可以代替RSA的后量子密码系统。
但RSA不是当下最重要的问题，当务之急是，还有其他方法可以破坏互联网的安全，比如编程不良的软件、病毒，会将信息发送给一些恶意玩家。
我认为用安全的后量子密码体制，来取代RSA的最大障碍，是我们的不懈努力及编程时间。我认为这是我们知道如何去做的事情，只是我们是否能及时做到还是未知数。
图6｜RSA算法（来源：Exabeam）
- 会不会出现让我们措手不及的风险呢？
会的。为了修复2000年出现的错误（千年虫），人们付出了巨大的努力。
而人们需要付出更大的努力，才能切换到后量子时代。但如果我们等得太久，那就太迟了。
参考链接：
[1]https://www.nature.com/articles/d41586-020-03068-9
[2]https://journals.aps.org/pra/abstract/10.1103/PhysRevA.52.R2493
[3]https://ieeexplore.ieee.org/document/365700
[4]https://link.springer.com/article/10.1007/s00283-020-10022-0
[5]https://www.nature.com/articles/d41586-019-02936-3
[6]https://www.nature.com/articles/d41586-019-03213-z
声明：此文出于传递高质量信息之目的，若来源标注错误或侵权，请作者持权属证明与我们联系，我们将及时更正、删除，所有图片的版权归属所引用组织机构，此处仅引用，原创文章转载需授权。