jiyang1971的个人博客分享 http://blog.sciencenet.cn/u/jiyang1971

博文

量子计算机奈何不了公钥加密术 精选

已有 2854 次阅读 2019-5-24 09:15 |个人分类:察见渊鱼者不祥|系统分类:科普集锦


 

数学定理和现实世界不一样

 

关于量子通讯的讨论,有很多都预设了一个前提:未来的量子计算机可以高效地破解公钥加密术——这就是著名的Shor算法,其基础在于量子傅里叶变换的效率很高。

 

其实,量子计算机奈何不了公钥加密术,这早就被说的很明白了——随便找本标准的量子计算教材就可以看到的。

 

一个量子比特是|0>|1>的相干叠加态,n个量子比特可以有N=2n个系数。量子傅里叶变换可以利用量子态的叠加特性来并行地处理这2n个系数。在任何一本量子计算的标准教材里,都可以找到对量子傅里叶变换的描述。因为里面涉及了一些公式(有很多数学符号),这里就不抄书了。

简单地说一下,量子傅里叶变换只需要三种量子操作:一种交换和两种旋转。交换用来逆转量子比特的顺序,可以通过三个“受控非门”来实现。两种旋转分别是H门和R门:H门转动的是固定的角度(先后绕着两个相互垂直的方向转动90度),而R门转动的角度需要考虑不同的情况。

量子傅里叶变换需要多少次量子操作呢?最多n/2次交换操作,n次的H门操作,n(n-1)/2次的R门操作(每次转动的角度可能不一样),总计n(n+2)/2次操作,这就是所谓的n2复杂度的来历。

如果能够实现量子傅里叶变换,就有办法进行快速的因数分解(Shor发明的算法),也可以在量子计算的教材里找到。我也不抄书了。

 

这样好像就解决了大数分解的问题,只要造出量子计算机,就可以宣告RSA的末日。但是有两个问题,稍微深究一下就知道,这件事情是做不到的。

第一个问题是R门转动角的精度。为了实现量子傅里叶变换,转动的角度θ必须达到很高的精度。这个精度要求有多高呢?答案是360/2n度。如果n10的话,就是大约0.3度,跟我们看到的太阳张角差不多(0.5度);如果n20的话,就是大约0.0003度;而现在的RSA至少也有一千位,也就是n1000,这样对应的角度小得不可思议。

换个方式来说一下这个角度有多小。一个原子大概是0.1纳米,用原子围成一个半径为1米的圆,每个原子相对于圆心的张角就是0.000000006度,而这个角度对应的n大概是29。如果选择n100,最小的角度仍然用半径为R的圆周上一个原子相对于圆心的张角来表示,那么这个圆的半径R就是2亿亿公里,正好是2光年的距离。如果n110,这个圆的半径就可以超过我们目前所知的宇宙半径(几百亿光年)。更别说n等于1000或者2000了——太难了,难的无法实现。

第二个问题是如何高精度地进行2k个乘法。Shor算法要用到“相位估计”,在此过程中,需要对进行2k个乘法,k0n-1,实际上等效于把某个角度ψ转动2k次,与上面的情况类似,很小的初始误差就会使得最终结果有不可容忍的巨大偏离。

我们这里还压根没有讨论如何实现多个量子比特之间的纠缠,更没有讨论物理量子比特和数学量子比特的差别,以及多少个物理量子比特才有可能构成一个数学量子比特的问题。

 

现在的RSA公钥加密术采用的至少都是一千位以上数字,基于量子傅里叶变换的Shor算法对此根本就无能为力——再说还有基于其他算法的公钥加密术(比如说椭圆曲线),更不是Shor算法能够发挥作用固定了。

所以,Shor算法只是个数学结果,它非常漂亮,非常震撼,但不幸的是,它无法应用于现实世界。




http://blog.sciencenet.cn/blog-1319915-1180861.html

上一篇:“水氢发动机”大概率是又一次“水变油”
下一篇:[转载]任正非接受媒体群访全文实录(2019.05.21)

14 李颖业 李维纲 徐晓 徐明昆 马红孺 张江敏 李东风 晏成和 杨正瓴 武夷山 黄永义 武伟伟 王春艳 岳东晓

该博文允许注册用户评论 请点击登录 评论 (3 个评论)

数据加载中...

Archiver|手机版|科学网 ( 京ICP备14006957 )

GMT+8, 2019-6-19 05:33

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部