20世纪80年代,物理学家们首次提出量子计算机的构思时,听起来十分乐观,但只能通过文字的方式来呈现。

后来在1995年,也就是25年前的上个月,应用数学家Peter Shor发表了一篇论文,改变了当时的一切。

|量客江湖系列01|破RSA大盗——Peter Shor-量子客
图1|Peter Shor(来源:TQD)

 

Peter Shor的论文

Shor的论文展示了量子计算机是如何克服一个关键问题的。这些机器将以量子比特的形式处理信息,量子比特是普通比特的量子版本,可以同时处理0和1。

但众所周知,量子态易受到噪音的影响,从而导致信息丢失。他的纠错技术(用于检测噪声引起的错误)展示了如何使量子信息更加可靠。

|量客江湖系列01|破RSA大盗——Peter Shor-量子客
图2|Peter Shor在1995年发表的论文(来源:美国物理学会)

Shor目前在剑桥的麻省理工学院工作,同时,他也是一位出版过诗集的诗人。

早在1994年,他就发现了如何使用量子计算机的模型进行计算,这让物理学界和计算机科学界感到震惊。

他提出了一个算法——质因数分解算法,可以让量子计算机以闪电般的速度将整数分解成质因数。今天的大多数互联网流量是基于大质数的加密技术保护的。破解这些代码十分困难,因为经典计算机在分解大型整数时很慢。

|量客江湖系列01|破RSA大盗——Peter Shor-量子客
图3|Peter Shor在1994年发表的论文(来源:电气电子工程师学会)

量子计算机现在已经成为现实,尽管它们还不足以计算两位数以上的数字。但量子计算机威胁互联网加密只是时间问题。

 

访谈内容

《自然》杂志采访了Shor,询问了关于他的工作所带来的影响——以及互联网安全的发展趋势。

 

1. 在你的质因数分解算法出现之前,量子计算机纯粹就是为了满足理论层面的好奇心吗?

我的论文的确使人们明白,这些机器可以做一些有用的事情。

计算机科学家Daniel Simon,在我得出我的结论之前,他就解决了一个他提出的问题,该问题表明量子计算机(比普通计算机)快得多。

但是即使采用Simon的算法,也无法得知这些机器是否可以发挥它们的用处。

 

2. 在宣布了你的质因数分解算法后,人们的反应如何?

起初,我只得到了一个不完整的结果。后来,在1994年4月,我在贝尔实验室做了一个关于这个选题的报告。

消息传得非常快,那个周末,计算机科学家Umesh Vazirani就给我打了电话说,“我听说你可以在量子计算机上进行质因数分解,告诉我你是怎么做到的。”

|量客江湖系列01|破RSA大盗——Peter Shor-量子客
图4|Umesh Vazirani(来源:伯克利工程学院)

那时,我其实还没有真正解决质因数分解的问题。但很神奇的是,报告结束的五天内,我的结果在人们的奔走相告中,变成了质因数分解成功。而在这五天里,我也确实解决了分解的问题,于是我就可以告诉Umesh我是怎么做到的了。

当时人们都在向我索要我还未完成的论文,所以我只能把粗稿拿给他们看了。

 

3. 但是仍有许多专家认为,量子计算机会在完成计算之前就丢失信息是吗?

其中一个反对意见是,在量子力学中,如果你测量一个系统,你会不可避免地干扰到它。

我演示了如何在不测量计算的情况下测量误差——然后你就可以修正误差,而不破坏计算。

在我1995年发表了关于纠错的论文之后,一些怀疑论者也确信量子计算是可行的。

 

4. 纠错依赖于“物理”和“逻辑”量子比特,这两者间的区别是?

当你写下一个量子计算机的算法时,你会假设量子比特是无噪声的。这些无噪声的量子比特就是逻辑量子比特,而我们的量子计算机中不存在没有噪声的量子比特。

事实上,如果我们试图在没有噪声干预的环境下,运行我们的算法。那错误的发生,是不可避免的。

物理量子比特是量子计算机中的含噪声的量子比特之一。为了在运行我们的算法时,不出现任何错误,我们需要使用物理量子比特对逻辑量子比特进行编码,这其中会用到量子纠错代码。

|量客江湖系列01|破RSA大盗——Peter Shor-量子客
图5|量子比特(来源:medium)

而我们所知道的最好的方法,是有相当大的开销的,此方法为每个逻辑量子比特都提供了诸多物理量子比特。

要计算出这项技术还需要多少量子比特是相当复杂的。如果你想用表面码(目前最佳选项)来建造一台量子计算机,那么每一个逻辑量子比特,大约需要100个物理量子比特来支持,甚至更多。

 

5. 在2019年,谷歌展示了其“量子优势”——即54个量子比特的量子计算机,它可以解决一个在经典计算机上耗时冗长的问题,你的反应是什么?

这绝对是一个里程碑。它表明,量子计算机可以比经典计算机做得更好——至少在以人为主导因素的问题上。

即便谷歌做了一些宣传活动,但毋庸置疑的是,这台量子计算机的确让人印象深刻。

在它能创造出奇迹之前,还需要一些完善工作。另外,初创公司IonQ制造的量子计算机,在某种程度上可能比谷歌和IBM的都要好。

 

6. 当量子计算机可以分解大质数时,它们就可以破解无处不在的互联网加密系统“ RSA”,这点你如何看待?

是的,但是第一个破解RSA的人,要么是NSA(美国国家安全局),要么是一些其他大型机构。

一开始,这些计算机运行会非常缓慢。如果你有一台每小时只能破解一个RSA密钥的计算机,那你肯定将其用于破解国家级别安全风险的信息。

比起用量子计算机阅读普通大众的电子邮件,美国国家安全局有更重要的事情可以做——他们将阅读中国大使的电子邮件,哈哈。

 

7. 有没有一种加密系统可以取代RSA,而且在量子计算机时代也是安全的——即“后量子加密”?

我认为我们会有可以代替RSA的后量子密码系统。

但RSA不是当下最重要的问题,当务之急是,还有其他方法可以破坏互联网的安全,比如编程不良的软件、病毒,会将信息发送给一些恶意玩家。

我认为用安全的后量子密码体制,来取代RSA的最大障碍,是我们的不懈努力及编程时间。我认为这是我们知道如何去做的事情,只是我们是否能及时做到还是未知数。

|量客江湖系列01|破RSA大盗——Peter Shor-量子客
图6|RSA算法(来源:Exabeam)

 

8. 会不会出现让我们措手不及的风险呢?

会的。为了修复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
 

声明:此文出于传递高质量信息之目的,若来源标注错误或侵权,请作者持权属证明与我们联系,我们将及时更正、删除,所有图片的版权归属所引用组织机构,此处仅引用,原创文章转载需授权。

|编  辑:王嘉雯      |审  校:王新文