现有两类量子计算机，一是通用量子计算机，二是2011年加拿大D-Wave公司推出的商业化专用量子计算机。

D-Wave量子计算机（来自D-Wave官网）

长期以来，Shor算法被认为是攻击电子政务和电子商务典型公钥密码RSA的唯一有效量子算法，一旦通用量子计算机诞生即可秒杀RSA密码。但是，2014年12月Nature ^[1] 和2018年1月Science ^[2,3] 均认为由于量子器件和基础理论等进展缓慢，实用的通用量子计算机还很遥远。美国Google首席量子计算机科学家、原UCSB（加州圣巴巴拉分校）John Martinis教授^[2]、国际量子专家Matthias Troyer教授（ETH Zürich）等人均指出通用量子计算机采用Shor算法破译实际运行的RSA公钥密码是遥遥无期^[1]。

在国家自然科学基金重点项目支持下，上海大学王潮课题组将目光投向D-Wave专用量子计算机公钥密码RSA破译（大整数素因子分解）。尽管D-Wave最初的应用是洛克希德马丁公司战机飞控软件测试、谷歌图像识别，与密码无关。

上海大学课题组在D-Wave量子计算软件环境验证了D-Wave原理量子退火通过量子隧穿效应对破译RSA公钥密码的可行性，还发现了D-Wave比通用量子计算机更具现实攻击力：2019年1月8日最新推出的IBM Q System One™运行Shor算法在理论上最大可以分解10 bit整数，而王潮团队实验表明当前D-Wave可以最大分解20 bit整数，这是千倍超越；目前，Google提出的72 量子比特芯片狐尾松（“Bristlecone”）由于纠错码等问题尚不能形成密码破译能力。

该成果将刊登于《中国科学：物理学 力学 天文学》（英文版，2019年62卷第6期），王潮教授担任通讯作者，并由著名密码学家、中国密码学会名誉理事王新梅教授撰写点评同期发表^[4]。

量子隧穿如何构成D-Wave量子计算机的计算优势？

D-WaveOne商业化专用量子计算机于2011年问世，运行环境为接近绝对零度的‒273.145度，只有25 kW的低功耗，远低于高性能计算机的功耗，众所周知，摩尔定律（Moore）和功耗问题的登纳德缩放比例定律(Dennard Scaling)是计算机发展的两大瓶颈问题。

量子退火与模拟退火优势对比示意图

如上图所示，在接近绝对零度时，D-Wave原理量子退火（Quantum Annealing）算法利用量子波动产生的量子隧穿效应跳出局部亚优解而逼近全局最优解，这是与经典模拟退火及其他众多计算搜索算法相比的一个独特优势。

量子波动使得量子具有穿透比它自身能量更高的势垒的能力，即量子隧穿效应（Quantum Tunneling Effect）。量子位可以通过2种方式改变自旋方向：通过量子力学的隧穿机制，或者通过经典的热运动。由于加热会破坏量子位的量子性质，必须使用一种通过隧穿效应使得自旋反转的方法。量子的热运动和隧穿效应各自有一个“冻结”时间，量子退火计算依赖于基态和第二低能态的能量差。对系统施以冷却，直到隧穿和热运动导致的转换都已经停止，量子位被“冻结”。通过在不同温度下重复这一过程，通过隧穿效应完成量子退火。

D-Wave破译密码为何被忽视？

国际军火商巨头Lockheed Martin作为首个客户与D-Wave签下订单，致力F-16和F-35^[5]战机飞控软件测试等军事用途；之后Google、NASA、Los Alamos国家实验室、哈佛大学、日本东北大学等在图像识别、蛋白质折叠、天气预报、交通优化、航空调度、海啸扩散预测等多个领域实现了100多个应用，因此鲜有人关注D-Wave的密码设计和破译能力。

根据Google等应用分析，业内认为基于量子退火的专用量子计算机对信息科学非常重要：有利于解决“有指数级可能性的答案”搜索，这是应用于密码设计和密码破译的一个基础。

王新梅教授在为《中国科学：物理学 力学 天文学》英文版撰写的点评^[4]中也指出：“如能用量子退火算法攻击其他知名密码算法，也是有意义的”。众所周知，构造公钥密码的数学难题主要有三类：一是大整数素因子分解难题（RSA密码），还有两类是基于离散对数和椭圆离散对数求解困难的公钥密码（如ECC），通用量子计算机对后两类公钥密码未形成有效攻击，第三类椭圆曲线密码（ECC）也是二代身份证采用的安全密码。需要进一步探讨D-Wave对后两类公钥密码的攻击可行性。

D-Wave还能做什么？

2017年底通过国际合作，上海大学王潮教授课题组在国际上首次完成D-Wave 2000Q专用量子计算机密码设计实验，抗多种攻击多指标密码函数设计转换为多目标优化问题，基于数学的密码设计转为指数级解空间搜索。

D-Wave的原理不同于通用量子计算机，是专用量子计算机，但是我们认为其用途是广泛的，完全不同于当年电子计算机发展历程中的只有单一计算机功能的专用电子计算机。D-Wave公司从2013年起陆续得到美国中情局旗下投资机构In-Q-Tel等机构的多轮投资，其商业化进展迅速。

D-Wave的设计构思非常巧妙，利用量子隧穿效应实现了量子退火，可以将一些组合优化问题求解的NP难题在多项式时间解决，Nature 认为可广泛用于密码学、人工智能、图像搜索、模式识别和机器学习、金融风险分析、生物信息学、情感分析等众多领域。

Google在进一步将D-Wave量子计算机应用于无人驾驶汽车的研究，期望以更加接近人脑的方式对障碍物进行判断，提供更好的导航；大众公司、上海大学王潮教授课题组等也在探讨智能交通领域的应用。

相信未来10年，在通用量子计算机进展缓慢的情况下，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] XinMei Wang. Quest towards “factoring larger integers with commercial D-Wave quantum annealing machines”, Sci. China-Phys. Mech. Astron. 62, 960331 (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

点击下方链接免费读全文：

W. C. Peng, et al. Factoring larger integers with fewer qubits via quantum annealing with optimized parameters, Sci.China-Phys. Mech. Astron. 62(6), 960311 (2019)

https://doi.org/10.1007/s11433-018-9307-1

http://engine.scichina.com/publisher/scp/journal/SCPMA/62/6/10.1007/s11433-018-9307-1?slug=fulltext