【技术知识】量子计算机能破译世界密码吗？

通讯

2020年12月4日，官方消息发布：中国科学技术大学潘建伟团队与中科院上海微系统与信息技术研究所、国家并行计算机工程技术研究中心合作，成功打造76光子量子计算原型“九章”。 200秒的“量子计算能力”相当于目前“最强超级计算机”的计算能力6亿年！

随着随机量子计算的兴起和快速发展，有媒体称量子计算机可以破解全世界的密码。 为什么？

2019 年，谷歌 CEO 预测加密技术的终结可能会在 5 年内到来。 为什么？

1 什么是量子计算？ 1.1 基本概念

量子信息包括量子通信和量子计算。 第九章实现量子计算。

注意！ ！ 量子计算不是传统意义上的超级计算机，如神威太湖之光、天河二号等，可以通过大规模并行计算实现超高速计算。 这是另一个概念。 量子计算并不是对所有的事情都很快，但是对某些特定的问题却很快，因为它需要有针对性的量子算法的支持。 量子力学的三大奥秘：叠加、测量和纠缠。

1.2 基本原则

经典计算机的基本运行单位是比特，而量子计算机的基本运行单位是量子比特。 比特就像家里的电灯开关，只有 0-1 两种状态，而量子比特就像旋钮开关，有无限的状态。 所以可以做更多的事情。

在经典计算中，如果有 n 个经典比特，每个比特有两个状态，它们的组合总共有 2n2^n2n 个状态。 如果你想知道一个操作对n位的影响，你需要将这个操作应用于这2n2^n2n个状态。 众所周知，指数增长非常快。 比如数学中n趋于无穷大时，2n2^n2n大于n10000n^{10000}n10000。 这样的数据量在经典计算中会导致计算量的爆炸式增长。

在量子计算中，量子位是不同的。 一个量子比特一般有两个基本状态，一个一般状态等于这两个基本状态的叠加。 对于一个n个量子比特的系统，有2n2^n2n个基本态，一个一般态等于这2n2^n2n个态的叠加。 对这种一般状态的一次操作相当于在具有 n 位的经典计算机上进行 2n2^n2n 次操作。 一个超过 2n2^n2n。 如果使用得当，这可以带来指数级的加速。 过去需要数亿年计算的问题，现在可以在一秒钟内解决。 为什么只有使用得当才能实现，下面第三节量子计算的难点会解释。

2 为什么密码可以被破译 2.1 因式分解

让我们先了解因式分解

例如21 = 3*7，一个数可以分解为两个素数的乘积。 这是一个简单的因式分解过程。 最基本的算法就是把数n除以1...n\sqrt{n}n ，如果不能分解，就说明它是质数。 换成二进制，计算量也是2n/22^{n/2}2n/2，目前效率最高的算法是数域筛法。 但是，该算法的计算量仍然呈指数级增长。 例如，如果一台计算机每秒执行一万亿次运算，那么用数域筛选算法分解一个 300 位数字需要 15 万年，分解一个 5000 位数字需要 50 亿年。 ，地球的年龄只有46亿年。 可以说目前的技术无法分解该因子，所以才被科学家用来保密。

2.1 保密制度RSA

当今世界上最常用的密码系统之一称为 RSA，它是发明者 Ron Rivest、Adi Shamir 和 Leonard Adleman 的首字母缩写。

粗略地说，RSA的操作方式，发送方是Alice，接收方是Bob。 首先，爱丽丝取两个非常大的素数，得到它们的乘积 N=p*q。 这一步很容易，然后把N传给全世界公布，p和q不公布，N是公钥，p和q是私钥量子计算机破解比特币，Alice通过公开的通道发给Bob，Bob可以用自己的私钥解密。

2.3 量子计算可以破解RSA

但是，RSA 在未来是不可靠的。 早在1994年，美国科学家Peter Shor就提出了量子分解算法。 分解一个n位数的计算量约为n2n^2n2，计算量呈指数级节省。 ，分解一个 300 位数字需要 1 秒，分解一个 5000 位数字需要 2 分钟。

因此，媒体所说的可以破解世界上所有密码的量子计算基本可以成立，除了量子密码学。 这也是只有魔法才能战胜魔法的原因。

目前国内研究的最大量子分解数为291 311 =523 * 557，二进制为19位，常用的RSA公钥长度为1024位，距离1024位还有很大差距。 所以目前，要破解世界上所有的密码，还有很长的路要走。 但谷歌的首席执行官预测，加密技术的终结可能会在五年内到来。 《科学》杂志News宣布，IBM将在2023年实现1000个量子位的计算（九章76个量子位），谷歌将在未来十年实现100万个量子位的计算。 因此，谷歌CEO的预测是对公司实力进步的认知所做出的预测。

3 量子计算的难点

量子计算机的发展将经历三个阶段：

第一阶段，研制50-100个量子比特的专用量子计算机，实现“量子优越性”的里程碑式突破。

第二阶段是研制可操纵数百个量子比特的量子模拟器，以解决一些超级计算机无法解决且具有很大实用价值的问题，如量子化学、新材料设计、优化算法等。

第三阶段，大幅提升量子比特的操控精度、积分数量和容错能力，研制出可编程的通用量子计算原型。

目前，“九章”还处于第一阶段，能够计算76个量子比特。

潘建伟团队历经20年艰苦奋斗才取得这一突破。 他们从2001年开始筹建实验室，曾多次打破量子纠缠数量的世界纪录。 “九章”的突破主要攻克了三大技术难关：高质量量子光源、高精度锁相技术、大规模干涉技术。

其中，优质量子光源是目前世界上唯一具有高效率、高同一性、高亮度和大规模扩展能力的量子光源。 “比如我们每次喝一口水很容易，但每次喝一个水分子就非常难了。” 中国科学技术大学卢朝阳教授表示，高质量的光源必须保证每次只“释放”一个光子，而每次要让每个光子完全一样，是一个巨大的挑战。 同时锁相精度要控制在10−910^{-9}10−9以内，相当于传输100公里的距离，偏差不能超过一根头发丝的直径。

此外，为了验证《九章》的计算是否“准确”，他们同时使用超级计算机进行了验证。 “当有10个或20个光子时，结果就能匹配到。当达到40个光子时，就更难超算了量子计算机破解比特币，但‘九章’已经计算到76个光子了。” 另一方面，陆朝阳表示，超算的功耗太大了。 按40个光子计算，需要200万元电费，41个光子需要400万元，42个光子需要800万元。 计算将是天文数字。

4 量子计算的应用

上文提到，超量子计算只能针对特定问题，需要特定算法才能发挥其优势。 具体算法可以应用于以下领域