作者:村头二旧
来源:揭秘量子计算的算法和攻击

事情的起因是这样的,2019年11月6日,任正非先生参加一个咖啡对话节目,说出了如下这段话:

任正非是企业家中的翘楚,华为是世界一流的企业,这样位高权重声名显赫的人的一句话,可能会改变很多人的认知,任先生说的是对的吗?
我负责的告诉大家,他的话目前来看作为思想实验来说是有意义的,只是在思想实验上。不过,隐藏了一个基本事实,区块链一文不值的前提是“量子计算机”出来之后,量子计算机什么时间能出来?出来了具体又能怎么样呢?量子计算的算法是怎么样的?下文将对这些问题逐步展开。
谷歌(google)所谓的“量子霸权”究竟到哪一步了?谷歌公司实际上做到的是量子计算芯片,距离真正能够商用或者能够军用的计算机,差距有多大?
我用游戏做个类比,各位读者在年纪很小的时候肯定玩儿过“贪吃蛇”“俄罗斯方块”这类游戏,斯皮尔伯格拍了一部科幻电影叫做《头号玩家》,这里面的游戏世界是未来的一种科幻猜想,谷歌和量子计算机的距离,比“贪吃蛇”到“头号玩家”中的科幻场景游戏还远很多。



关于量子计算我咨询了很多人看了很多资料,包括清华大学计算机系姚班杨光博士(Conflux研究总监),清华大学物理系的专家,和国外量子研究的专家,也阅读了谷歌在美国NASA放出的“量子霸权”文章,以及国内量子比特研究方面的专家中科大潘建伟教授的论文。这些内容我会在文末放上参考文献链接,大家感兴趣的可以一一查阅。
量子计算最重要的优势在于,目前人类发现了三种算法,无法被经典信息编码,但是可以被量子信息编码。本文只提及和区块链密码学关系最紧密的两个。
量子计算网上讲述的内容多是属于科幻领域或者叫思维试验,包括我自己写的那篇关于“量子矿机”的文章(搜“量子矿机”可以搜出来那个思想实验,关于把矿机改造成量子计算机)。里面也是假设量子计算机比起传统计算机的速度提升,是指数级的,可以暴力破解密码,把挖矿这个工作,直接提升到,破解所有BTC私钥。
按照这个思路,能够商用(甚至军用)的量子计算机如果能出来,整个人类的金融系统和银行加密系统首先变得一文不值,在对整个银行加密系统的巨大影响面前,对区块链的影响可以不予考虑。
不过,这里面并不完全准确——不少学术界的人也是这么描述来混一些科研经费,实际上并非如此。
实际情况是这样的,对于n个qubit,确实可以搜索2^n次,这个过程叫做量子傅立叶搜索,但是量子傅立叶搜索的结果只能随机输出n个,所以跟原来的n个比特搜索n次没有区别,甚至还更差。具体来说,量子计算机确实可以提升搜索效率,但是没有那么bug。如果一栋大楼有n个房间,一个房间有奖品,经典计算机需要搜索O(n) 次,这是非常直观的,就是穷举法,而哈希碰撞本质上就是穷举法;量子计算机用一种叫做Grover算法的方法,只需要搜索Q(sqrt(n))次(也就是对n开根号,n次就变成了根号n)。对于哈希碰撞这样n非常大的问题,量子Grover搜索确实可以大幅大幅降低搜索步数,但是仍然很大,而抵抗这种攻击的方法很简单,原来的私钥长度增加1倍长度即可。这就是今天要讲的量子计算的第一个算法“Grover算法”
第二个算法Shor算法,Shor算法构建了大数质因子的量子算法,而非对称加密算法RSA和椭圆曲线加密可以通过Shor算法进行攻击破解,很多人说量子计算机暴力破解BTC,我反对这种说法,因为一点也不暴力,他是非常优雅地破解,采用一种全新的算法,这种算法无法在经典计算机上运行。
除此之外,目前没有发现其他任何算法在量子计算机上更快。
所以量子计算机不可能替代现有的芯片工业,但可能带来一波新的算法革命。
总结,正面回答问题:任正非先生错了吗?是的,他错了。区块链在量子计算机面前,不会一文不值。任正非先生是企业界的领袖,不过对于量子计算的算法和量子计算机,我们更应该相信学术界的成果
或许在未来量子计算会有更新的发展。目前来看,“量子计算机”对区块链的威胁是站不住脚的。

参考文献和咨询人员:
[1] 公链Conflux研究院院长 清华大学姚班 杨光博士
[2] 中科大潘建伟教授18量子比特论文https://arxiv.org/ftp/arxiv/papers/1801/1801.04043.pdf
[3] 谷歌的量子霸权论文https://drive.google.com/file/d/19lv8p1fB47z1pEZVlfDPundihop082Lc-kdD/view
[4],龙桂鲁 . 量子计算算法介绍[J]. 物理, 2010,39(12):803-810. LONGG L . Introduction to quantum algorithms[J]. Physics, 2010,39(12):803-810.

20191121112600_s21N.jpg

20191121112600_s21N.jpg
本文由:村头二旧 发布于:2019-11-21 14:10:40 0 位用户参与了讨论
转播转播 分享淘帖
回复

使用道具

成为第一个回贴人

B Color Link Quote Code Smilies
Copyright © 2001-2019 · 挖矿网 ·   京ICP备12010892号-1 -