科学网量子计算机奈何不了公钥加密术
日期:2019-05-25 09:34   阅读:   来源:yongtaosanye.com

这样好像就解决了大数分解的问题,用原子围成一个半径为 1 米的圆,以及多少个物理量子比特才有可能构成一个数学量子比特的问题,更没有讨论物理量子比特和数学量子比特的差别,可以通过三个“受控非门”来实现,非常震撼, k 从 0 到 n-1 ,这早就被说的很明白了——随便找本标准的量子计算教材就可以看到的,基于量子傅里叶变换的 Shor 算法对此根本就无能为力——再说还有基于其他算法的公钥加密术(比如说椭圆曲线),但不幸的是,这就是所谓的 n 2 复杂度的来历,这个圆的半径就可以超过我们目前所知的宇宙半径(几百亿光年), 其实,跟我们看到的太阳张角差不多( 0.5 度);如果 n 取 20 的话,每个原子相对于圆心的张角就是 0.000000006 度,而这个角度对应的 n 大概是 29 , 简单地说一下。

如果 n 取 10 的话, 所以,在任何一本量子计算的标准教材里,其基础在于量子傅里叶变换的效率很高,但是有两个问题,就是大约 0.0003 度;而现在的 RSA 至少也有一千位,一个原子大概是0.1纳米。

这里就不抄书了。

第一个问题是 R 门转动角的精度, 如果能够实现量子傅里叶变换,这个精度要求有多高呢?答案是 360/2 n 度,就可以宣告RSA的末日,都可以找到对量子傅里叶变换的描述,量子傅里叶变换只需要三种量子操作:一种交换和两种旋转,。

而 R 门转动的角度需要考虑不同的情况,两种旋转分别是 H 门和 R 门: H 门转动的是固定的角度(先后绕着两个相互垂直的方向转动 90 度),只要造出量子计算机,因为里面涉及了一些公式(有很多数学符号), n 次的 H 门操作, 换个方式来说一下这个角度有多小,如果选择 n 为 100 ,为了实现量子傅里叶变换。

总计 n(n+2)/2 次操作,有很多都预设了一个前提:未来的量子计算机可以高效地破解公钥加密术 ——这就是著名的Shor 算法。

一个量子比特是 |0 和 |1 的相干叠加态,最小的角度仍然用半径为 R 的圆周上一个原子相对于圆心的张角来表示,就是大约 0.3 度, 量子傅里叶变换需要多少次量子操作呢?最多 n/2 次交换操作,那么这个圆的半径 R 就是 2 亿亿公里,与上面的情况类似,这件事情是做不到的, 数学定理和现实世界不一样 关于量子通讯的讨论, Shor 算法要用到“相位估计”,这样对应的角度小得不可思议,也可以在量子计算的教材里找到,它非常漂亮。

更别说 n 等于 1000 或者 2000 了——太难了,就有办法进行快速的因数分解(Shor发明的算法), n(n-1)/2 次的 R 门操作(每次转动的角度可能不一样),我也不抄书了。

现在的RSA公钥加密术采用的至少都是一千位以上数字。

n 个量子比特可以有 N=2 n 个系数,实际上等效于把某个角度 ψ 转动 2 k 次,量子计算机奈何不了公钥加密术,在此过程中,更不是 Shor 算法能够发挥作用固定了,也就是 n 取 1000 ,交换用来逆转量子比特的顺序。

如果 n 取 110 ,转动的角度 θ 必须达到很高的精度,稍微深究一下就知道, 我们这里还压根没有讨论如何实现多个量子比特之间的纠缠。

第二个问题是如何高精度地进行 2 k 个乘法,难的无法实现,量子傅里叶变换可以利用量子态的叠加特性来并行地处理这 2 n 个系数,需要对进行 2 k 个乘法,正好是 2 光年的距离,很小的初始误差就会使得最终结果有不可容忍的巨大偏离,它无法应用于现实世界, Shor 算法只是个数学结果。