揭秘量子计算的算法和攻击：任正非关于量子计算和区块链的表述错了吗？

显示全部楼层 · 发表于 2019-11-21 14:10:40

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

事情的起因是这样的，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

揭秘量子计算的算法和攻击：任正非关于量子计算和区块链的表述错了吗？

相关帖子