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

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

导读：在中国国家自然科学基金会的重要项目中，致力于利用 D-Wave 量子计算机研究因数分解的上海大学研究小组王潮团队，通过D-Wave的设计巧妙地实现了量子退火算法、量子穿隧效应技术应用等，并开发了一种基于量子计算破解RSA的新方法，该方法有效地实现Shor算法，并且可分解高达20位整数。随着量子技术的不断发展，量子技术将会被广泛的应用于如密码学、智能交通、智慧城市、图像处理、机器学习、生物信息学、情感分析等领域。

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

人们一直将Shor算法（Shor's algorithm）视为RSA (广泛应用于电子政务和电子商务)密码分解的独特而强大的量子算法，各种媒体和研究人员却指出，RSA 将随着通用量子计算机的出现而迅速崩溃。 然而，《自然》和《科学》却报道[2,3]说，通用量子计算机即便在很长一段时间内仍然不可能成功破解。 圣塔芭芭拉加利福尼亚大学物理系的 John Martinis 教授和 Matthias Troyer 教授也表示，量子计算机要实现一些包括破解代码的实际应用，还需要几年的时间。

在中国国家自然科学基金会的重要项目中，上海大学研究小组王潮团队致力于利用 D-Wave 量子计算机研究因数分解问题。尽管 D-Wave 一开始与密码学没有任何关系，其最初主要用于图像处理(Google)、软体验证(Lockheed Martin)等一些领域，但是王潮团队却开发了一种基于量子计算破解RSA的新方法。

该团队在破译 RSA 密码系统时展示了量子退火算法和 D-Wave 量子计算机的潜力。 此外，研究小组还表明，D-Wave 量子计算机可能比在通用量子计算机中使用Shor算法破解实际的 RSA 代码具有更强大的攻击力。 即使新出的 IBM Q System One (2019年1月8日)已经宣布它可以有效地实现Shor算法，且理论上可以分解的整数多达10位，但 D-Wave 却可以分解20位整数(超过1000倍)！ 事实上，目前包括谷歌的72量子比特计机“Bristlecone"这类基于量子电路的量子芯片计算机，由于受到诸多因素的限制，还不能够实现因式分解。

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

1. 量子穿隧效应如何帮助 D-Wave 机器建立优于其他机器的优势？

D-wave One 机器出现于2011年，它可以以远低于高性能计算机的功耗(目前为25kW) 在接近绝对零度(15mk)的状态下工作，但是目前的发展却受到摩尔定律和丹纳德定标的限制。如图2所示，在绝对零度附近工作的 D-Wave 量子退火算法可以激活量子穿隧效应，允许其从局部次极性跳跃到接近、甚至达到指数的全局最优值。这是 D-Wave 机器相对于其他经典搜索空间的独特优势。

图2

量子穿隧效应（Quantum tunneling effect）是指量子涨落使量子能够以比自身更高的能量直接穿透势垒。 量子态可以通过两种不同的方式改变自转方向: 量子涨落和（或）热波动。 热退火技术将打破量子态，使得量子系统只需要受到量子涨落影响就可以完成量子穿隧过程。 实际上，量子比特的热动力学和量子穿隧效应分别有自己的冻结时间。 量子退火取决于基态和第二、第一激发态之间的能量差，而冷却系统则要等到量子穿隧效应和热波动最终停止，然后从该过程中获得最终量子态。 系统通过重复不同温度下的冷却过程，完成量子退火技术，从而有效地实现量子计算。

2. 为什么D-Wave 的代码破解潜力被忽略了？

全球军火商洛克希德 · 马丁公司(Lockheed Martin Corporation)首先签订了一份购买 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] Elizabeth Gibney. Physics: quantum computer quest. Nature News Feature 516: 25-26. Dec. 3 2014.

[2] Adrian Cho. DOE pushes for useful quantum computing. Science 359, 6372: 141-142. Jan. 12 2018.

[3] Jeffrey Brainard. What's coming up in 2018. Science 359, 6371: 10-12. Jan. 05 2018.

[4] X. M. Wang, Quest towards"factoring larger integers with commercial D-Wave quantum annealing machines", Sci. China-Phys. Mech. Astron. 62, 060331 (2019).

[5]George Leopold. Quantum leaps needed for new computer approach. Defense System. Dec. 09 2016. https://defensesystems.com/articles/2016/12/09/quantum.aspx See the article: W. C. Peng, et al. Factoring larger integers with fewer qubits via quantum annealing with optimized parameters, Sci. China-Phys. Mech. Astron. 62(6), 060311 (2019) https://doi.org/10.1007/s11433-018-9307-1

原文链接：

https://www.eurekalert.org/pub_releases/2019-04/scp-anh040219.php

Line | 整理

Yoking | 编辑

量豆豆 | 校对

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

END

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

▽

Quantum Scientist ◆ 量子客

www.qtumist.com