D-Wave 量子计算机以数千倍的速度破解 RSA，带来新希望

图：D-WAVE量子计算机（D-WAVE官网）

简介：在国家自然科学基金重大项目中，上海大学王超课题组致力于利用D-Wave量子计算机研究因式分解，巧妙地实现了量子退火算法，量子穿透通过D-Wave 的设计。 应用隧道效应技术等量子计算机比特币破解，开发出基于量子计算的RSA破解新方法，有效实现了Shor算法，最多可分解20位整数。 随着量子技术的不断发展，量子技术将广泛应用于密码学、智能交通、智慧城市、图像处理、机器学习、生物信息学、情感分析等领域。

量子计算机有通用量子计算机和专用量子计算机两种，其中最先进的是加拿大D-Wave量子计算公司研制的商用专用量子计算机。

人们一直将秀尔算法（Shor's algorithm）视为一种独特而强大的RSA（广泛应用于电子政务和电子商务）密码分解的量子算法，但各种媒体和研究人员指出RSA将会并迅速崩溃。 然而，《自然》和《科学》报道[2,3]，通用量子计算机即使再长时间也仍然不可能成功破解。 美国加州大学圣塔芭芭拉分校物理系教授 John Martinis 和 Matthias Troyer 也表示，量子计算机还需要数年时间才能实现一些实际应用，包括密码破译。

在国家自然科学基金的一项重要项目中，上海大学研究组王超团队正在使用D-Wave量子计算机研究因式分解问题。 虽然D-Wave一开始和密码学没什么关系，主要用于图像处理（谷歌）和软件验证（洛克希德马丁）等一些领域，但是王超的团队开发了一种基于量子计算的新破解方法RSA。 方法。

该团队在破译 RSA 密码系统时展示了量子退火算法和 D-Wave 量子计算机的潜力。 此外，该团队表明，D-Wave 量子计算机可能比在通用量子计算机中使用 Shor 算法破解实际 RSA 代码更强大。 尽管新的 IBM Q System One（2019 年 1 月 8 日）已经宣布可以有效地实现秀尔算法，理论上可以分解最多 10 位整数，但 D-Wave 可以分解 20 位整数（超过 1000 次）！ 事实上，目前基于量子电路的量子芯片计算机，包括谷歌的72量子比特计算机“Bristlecone”，由于受到诸多因素的限制量子计算机比特币破解，尚无法实现因式分解。

中国CACR（中国密码学研究会）名誉理事王新梅[4]提到，研究成果将发表在《中国科学：物理力学与天文学》杂志（第62卷第6期，通讯作者：王超),主要内容如下：

1. 量子隧穿如何帮助 D-Wave 机器获得优于其他机器的优势？

2011年出现的D-wave One机器，可以工作在接近绝对零（15mk）的状态，功耗远低于高性能计算机（目前25kW），但目前发展受限于摩尔定律去校准的法律和 Dana 限制。 如图 2 所示，在绝对零附近运行的 D-Wave 量子退火算法可以激活量子隧穿效应，使其从局部亚极性跳跃到接近甚至达到指数全局最优。 这是 D-Wave 机器相对于其他经典搜索空间的独特优势。

图 2

量子隧穿效应（Quantum tunneling effect）是指使量子能够以比自身更高的能量直接穿透势垒的量子涨落。 量子态可以通过两种不同的方式改变其自旋方向：量子涨落和/或热涨落。 热退火技术会打破量子态，使量子系统只有在量子涨落的影响下才能完成量子隧穿过程。 事实上，量子比特的热力学和量子隧穿效应都有各自的凝固时间。 量子退火取决于基态与第二激发态和第一激发态之间的能量差，而冷却系统则等待直到量子隧穿和热涨落最终停止，然后从该过程中获得最终的量子态。 该系统通过在不同温度下重复冷却过程来完成量子退火技术，从而有效地实现量子计算。

2. 为什么 D-Wave 的破译潜力被忽视了？

全球军火商洛克希德马丁公司率先达成协议购买 D-Wave One 以解决最具挑战性的计算问题，例如从 F-16 飞机（未来的 F-35 [5]）中找出错误代码。 紧接着，来自谷歌、美国宇航局、洛斯阿拉莫斯国家实验室、哈佛大学和东北大学的研究人员将 D-Wave 退火技术软件应用于包括图像处理、蛋白质折叠、交通流量优化、空中交通管制、海啸疏散等 100 多个领域应用程序。 这也是为什么大家忽略了D-Wave量子计算机在密码学设计和分析中的应用。

据谷歌分析，内部人士认为，具有量子退火技术的专用量子计算机对信息技术至关重要。 这是因为量子计算机能够找到计算机科学中一类重要问题的近似答案，这些问题只能通过穷尽所有可能的解决方案来真正解决。 因此，为量子退火在密码学中的应用奠定了坚实的基础。

王新梅教授在文章[4]中指出，探索D-Wave量子计算机在攻击其他密码系统方面的潜力非常重要。 众所周知，构建一个高度安全的密码系统实际上存在三个难点。 除了问题分解难度大之外，离散对数问题和椭圆离散对数问题（如中国二代身份证的核心基础ECC）也提供了比其他问题更强大的方法来抵御量子计算机攻击。 因此，D-Wave量子计算机解决后两个问题的可行性值得进一步思考。

3. D-Wave 量子计算机还能做什么？

2017年底，王教授课题组首先通过D-Wave 2000Q系统实现了密码学组件设计实验，将多准则密码学函数设计问题转化为多目标优化问题，使数学问题可以在指数解空间，从而映射到一个优化问题得到解决。

虽然D-Wave量子计算机不同于为特殊目的而设计的通用量子计算机，但我们相信它可以广泛应用于各个领域，这与早期的经典计算机完全不同。电子计算机的发展。 目前，D-Wave自2013年以来已获得包括In-Q-Tel在内的多轮投资，其目标是商业化落地实际应用。

D-Wave的设计巧妙地实现了量子退火量子隧穿效应技术的应用，使得在有效时间内解决一些NP问题成为可能。 《自然》杂志报道说它可以广泛应用于许多领域，包括密码学、图像处理、模式识别和机器学习、金融分析、生物信息学、情感分析等。

谷歌正在进一步探索 D-Wave 量子计算机与自动驾驶汽车的结合，期待开发出一种更像人脑的智能方式来识别障碍物并实现更好的导航。 另一方面，大众汽车和王超团队也致力于量子智能交通应用技术的研究。

我们坚信，未来十年，在物理学家和信息科学家的合作下，将会有更多智慧城市和城市精益化管理的应用得到发展。

参考

[1] 伊丽莎白·吉布尼。 物理学：量子计算机探索。 自然新闻专题 516：25-26。 2014 年 12 月 3 日。

[2] 阿德里安·乔。 DOE 推动有用的量子计算。 科学 359, 6372: 141-142。 2018 年 1 月 12 日。

[3] 杰弗里·布雷纳德。 2018 年会发生什么。科学 359, 6371: 10-12。 2018 年 1 月 5 日。

[4] XM Wang，探索“使用商用 D-Wave 量子退火机分解更大的整数”，Sci。 中国物理。 机甲。 天文。 62, 060331 (2019)。

[5]乔治·利奥波德。 新的计算机方法需要量子飞跃。 防御系统。 2016 年 12 月 9 日。参见文章：WC Peng, et al. 通过具有优化参数的量子退火，Sci. 用更少的量子位分解更大的整数。 中国物理学报机甲。 天文。 62(6), 060311(2019)

原文链接：

专线|

约克 | 编辑

测量豌豆 | 校对

本文由量子客整理发布，欢迎署名转载！

结尾

量子技术前沿技术专业解读

▽

量子科学家