知识卡片
Grover加速有问题边界
本书以 Grover 算法说明量子计算可能加速穷尽搜索:若待查候选有 N 个,书中给出的量级是 O(√N),相对于逐个检查的 O(N) 属于平方加速。这个结论针对特定搜索问题及其查询模型,不能扩展成“量子计算让所有算法指数加速”,也不能凭书中对 RSA、DES 的假设性步数比较断言现实密码已被破解。后续量子机制章节还需解释叠加与干涉如何参与搜索。
书中把 56 位 DES 的经典穷尽约写成 3.5×10¹⁶ 步,Grover 约 2 亿步;√(3.5×10¹⁶)≈1.87×10⁸,与“2 亿”同一量级。这是原文给出的步数对照,不是实测破译记录。实用规模的量子计算在书中仍写为尚在探索。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 量子计算(Quantum Computation,QC)的研究开始于1982年,计算首先被诺贝尔物理学奖获得者Richard Feynman看成 · 查看原书依据
量子计算的并行性、指数级存储容量和指数加速特征展示了其强大的运算能力[1-2],1994年Peter Shor就提出了分解大数质因子的量子算法,它仅需几分钟就可以完成用1600台经典计算机需要250天才能完成的RSA-129问题(一种公钥密码系统),当前公认为最安全的、经典计算机不能破译的公钥系统RSA可以用量子计算机很容易地破译[3];1996年,Grover提出量子搜索算法,证明量子计算机在穷尽搜索问题中比经典计算机有的加速[4],用此算法,可以仅用2亿步代替经典计算机的大约3.5×1016步,破译广泛使用的56位数据编码标准DES(一种被用于保护银行间和其他方面金融事务的标准)。
参考来源
- 位置:《智能算法导论》第 140 项量子计算导言(源文件:`_epub-src/EPUB/xhtml/chapter15_0001.xhtml`;公式图像 `image_330.svg`)
- 结论依据:正文把 Grover 与穷尽搜索相连;导言其余关于 RSA/DES 与全面加速的叙述缺少适用条件。DES 的 2 亿对 3.5×10¹⁶ 是原文数字,开方核算用于说明“平方加速”量级,不是实验室结果。
- 原始内容:1996年,Grover提出量子搜索算法,证明量子计算机在穷尽搜索问题中比经典计算机有的加速 [ 4 ]