量子计算核心突破!Shor算法实现或使密码成摆设

文章来源：新智元微信公众号

互联网时代绝大多数的加密，都由RSA算法完成。过去我们认为RSA不可破解，但随着量子计算的发展，RSA的安全性正受到挑战。今天刊发在《科学》杂志的最新论文，量子计算机有史以来第一次以可扩展的方式，用Shor算法完成对数字15的质因数分解。IBM物理科学高级主管MarkRitter表示，将Shor算法实现出来这件事，能够与经典计算中的‘Hello，World’相提并论。

互联网时代，密码和网络安全是通信的基础，无论是微信聊天，还是淘宝交易，都需要密码技术保障个人隐私和财产安全。

而现在的大部分加密，都由RSA算法完成，它基于一个非常简单的数论事实：

将两个大素数相乘十分容易，但是想要对其乘积进行因式分解却极其困难，因此可以将乘积公开作为加密密钥。

例如在一套RSA算法下，给定一对解密密钥3和5，由用户自己保存，那么3和5的乘积15，就成为公开的加密密钥。

当把3和5变成1024位的素数A和B时，令C是A和B的乘积。那么验证A乘以B等于C，是一件计算起来比较简单的事，即用户自己的密码可以获得通过；但是要从C倒推回A和B，却是无比的艰难，其运算时间超出计算机的能力，所以密码很难被破解。

所以RSA可以在公开加密密钥、加密和解密算法的情况下，通过验证和求解在时间复杂度上的极端不对称性，建立电子加密的基础。

RSA是目前最有影响力的公钥加密算法，它能够抵抗到目前为止已知的绝大多数密码攻击，已被ISO推荐为公钥数据加密标准。

今天，只有短的RSA钥匙才可能被强力方式解破。到2008年为止，世界上还没有任何可靠的攻击RSA算法的方式。只要其钥匙的长度足够长，用RSA加密的信息实际上是不能被解破的。但在分布式计算和量子计算机理论日趋成熟的今天，RSA加密安全性受到了挑战。

Shor算法

整数的质因数分解，进入多项式的时间

早在1994年，PeterShor就发明了一个量子算法（Shor算法），在整数的质因数分解上，能实现

的时间。这在当年引起了轰动，它展示了一个足够大的量子计算机，在理论上是能够把质因数分解的时间复杂性降到多项式的时间。

多项式时间在这里意义重大。因为RSA加密之所以有效，最重要的是因为整数的质因数分解，在数字特别大的时候，传统的计算方法根本看不到算完的那一天。现在最快的质因数分解算法，其花费的次指数时间，也达到了

但如果能把解密复杂度变成多项式的时间，那么基本任何的RSA模型下的大数，都能够很“轻易”的被破解。所以RSA加密在理论上已经不再安全。

然而，这种算法需要依赖可操作大量量子的计算机。虽然有些人已经尝试了用各种量子系统来实现Shor的算法，但是没有人能在超过几个量子比特的系统上以可扩展（scalable）的方式这么做。所以Shor算法虽然具有理论的意义，但一直没法真正在工程上使用。而世界上也很难找到比RSA更加简单而有效的加密手段，所以RSA加密一直统治着世界，直到现在。

进入21世纪以来，量子计算机开始加速发展。2001年，IBM的一个小组展示了Shor算法的实例，使用核磁共振的量子计算机，以及7个量子位元，将15分解成3×5。然而，对IBM的实验的是否是量子计算的真实展示，有一些疑虑出现，因为没有缠结现象被发现。在IBM的实验后，有其他的团队以光学量子位元实现Shor算法，并强调其缠结现象可被观察到。

《科学》杂志最新论文

论文标题：RealizationofascalableShoralgorithm

作者：ThomasMonz，DanielNigg，EstebanA。Martinez，MatthiasF。Brandl，PhilippSchindler，RichardRines，ShannonX。Wang，IsaacL。Chuang，RainerBlatt

今天，在《科学》杂志最新发表的一篇论文中，量子计算机有史以来第一次以可扩展的方式，实现了Shor算法。

MIT和奥地利Innsbruck大学的研究者们报告说，他们设计并搭建了一台在离子陷阱中只有5个原子的量子计算机。这台计算机使用激光脉冲来在每一个原子上实行Shor的算法，分解数字15的质因数。这个系统的设计允许通过增加原子和激光来搭建更大型更快速、能够分解更大数字的质因数的量子计算机。

“我们展示了，Shor的算法——目前为止已知的最复杂的量子算法——能够以一种可扩展的方式实现：你需要做的一切就是，到实验室去，用上更多的技术，然后你应该就能做出更大的量子计算机了，”IsaacChuang说道，他是MIT物理学教授、电机工程和计算机科学教授，“量子计算机可能还是要耗费大量金钱才能造出来——暂时来看你还不会去造一台量子计算机然后把它放在你的书桌上——不过现在它更多地成为了一个工程问题，而不是一个基础物理学问题。”

穿越量子森林

在经典计算中，用0和1的组合来表示数字，而计算是根据算法的“指导”来进行的，通过操作这些0和1将输入的数字转变为输出的数字。与经典计算不同，量子计算依赖于原子标度的单位，或者叫做“量子比特”，它们可以同时是0和1——这种状态被称作“叠加态”。处于叠加态时，一个量子比特在本质上可以同时进行2个独立的计算流，使得计算效率大大高于经典计算机。

2001年时，量子计算领域的开拓者之一，Chuang，设计了一台基于一个分子的量子计算机，这个分子可以处于叠加态，通过核磁共振来进行操作，分解数字15的质因数。实验结果发表在了《自然》杂志上，这是第一次以实验的方式实现Shor的算法。不过这个系统是无法扩展的：随着加入的原子数量增多，控制这个系统变得越来越难。

“一旦你有太多的原子，它就好像成了一片森林——很难逐次控制单个原子，”Chuang说道，“难点在于，如何在一个分离程度足够高的系统里实现这个算法。这样的系统在量子力学的状态里可以维持足够久的时间，让你能够真正有机会完成整个算法。”

“直白明了的可扩展性”

Chuang和他的同事们现在终于研究出了一种全新的、可扩展的量子系统，能够高效地分解质因数。一般来说，分解数字15的质因数需要用到12个量子比特，但是他们找到了一种方法使得对量子比特的需求降低到5个，每个量子比特都用一个单一原子来表示。每个原子都能处于叠加态，同时处在两种不同的能量态中。研究者们在其中4个原子上使用激光脉冲来达到“逻辑门”——或者说Shor算法的元素——的效果。计算结果随后由第5个原子来储存、传递、提取、循环利用，由此以并行的方式实行了Shor的算法，用到的量子比特数量大为降低。

这支团队通过在离子陷阱中控制这些原子来让量子系统保持稳定。量子陷阱中，他们在每个原子上都移除一个电子，让它们带电，随后通过电场来摆放原子的位置。

“通过这种方式，我们能够精确地知晓某个原子的位置，”Chuang解释道，“然后我们用同样的方式处理几微米之外的另一个原子——这个距离大约是人类头发宽度的1/100。把一些这样的原子放在一起的话，它们仍然有相互作用，因为它们带有电荷。这种相互作用让我们能够进行逻辑门的操作，而逻辑门的操作带来了实现Shor算法的基础。无论我们把系统做得多大，我们都可以对其中任何一个原子进行逻辑门操作。”

Chuang的团队首先完成了量子计算机的设计，随后他在Innsbruck大学的同事基于他的理论方法搭建了一台实验设备。他们让这个量子系统分解数字15的质因数——这是能有意义地展示Shor算法的最小数字。在对答案没有先验知识的情况下，这个系统返回了正确的质数，置信度超过99%。

“我们预见到了它未来能拥有直白明了的可扩展性——一旦仪器能够捕获更多的原子、用更多的激光束来控制激光脉冲，”Chuang说道，“我们没有看出有任何物理学的理由阻止它成真。”

IBM物理科学高级主管MarkRitter表示，这支团队通过循环利用量子比特的方式将量子系统所需的资源降低了1/3——这是通往扩大量子计算规模的路上很小却很重要的一步。

“将最新的技术改进1/3是很好的事，”Ritter说道，不过真正将系统扩大“需要的量子比特数量是现在的几个量级，而这些量子比特必须穿梭在更先进的、有数以千计同时发射的激光控制脉冲的陷阱中。”

如果这支团队能够成功地向系统中加入更多量子元件，Ritter说，他们将会达成一项长期没有人能完成的成就。

“Shor的算法是第一个不容小觑的量子算法，拥有对经典算法进行指数级加速的潜力，”Ritter说道，“许多研究者都在关注量子计算，因为它或许能为算法带来可观的加速效果。因此，将Shor算法实现出来这件事能够与经典计算中的‘Hello，World’相提并论。”

这一切最终对于未来的加密机制来说有什么意义呢？

“好吧，一个影响是，作为一个国家，你可能不希望使用某些加密方法来储存你的机密信息——那些基于分解质因数是一个难以操作的问题而开发的加密方法，”Chuang说道，“因为当这些量子计算机开始进入使用阶段时，你将能够解密所有过去使用这些方法加密的机密文件。”

这个研究获得了美国高级情报研究计划署（IARPA）和MIT-Havard超低温原子中心（一所国家科学基金会物理前沿中心）的支持。（来源：ScienceMITTechnologyReviewWiki编译：王嘉俊王婉婷）

核动力宇宙飞船一个半月飞抵火星核动力宇宙飞船一个半月飞抵火星俄罗斯国家原子能公司总经理谢尔盖·基里延科宣布，公司正在研发能够在一个半月内抵达火星的核动力装置。更多精彩>

美国航天员生活：每天看16次日出美国航天员生活：每天看16次日出从太空看地球，除了地表的天气变化、山川河流一览无遗之外，还有不少有趣的收获。更多精彩>

嫦娥五号明年取回第一抔中国月壤嫦娥五号明年取回第一抔中国月壤按计划，嫦娥五号将从月球采回月壤。“这将是科研人员献给祖国的第一抔中国月壤。”胡浩说，带回它，相当于中国人第一次“触摸”到月球了。更多精彩>

科学家发现灰发基因:推迟头发变白科学家发现灰发基因:推迟头发变白《NatureCommunications》杂志前日公布一项最新研究结果称，发现第一个灰色头发基因，证实灰发是受遗传因素而非环境的影响。更多精彩>