← 返回刚才阅读的位置

知识卡片

普通读书笔记卡 · 3776

Grover加速有问题边界

理解等级:中级

本书以 Grover 算法说明量子计算可能加速穷尽搜索:若待查候选有 N 个,书中给出的量级是 O(√N),相对于逐个检查的 O(N) 属于平方加速。这个结论针对特定搜索问题及其查询模型,不能扩展成“量子计算让所有算法指数加速”,也不能凭书中对 RSA、DES 的假设性步数比较断言现实密码已被破解。后续量子机制章节还需解释叠加与干涉如何参与搜索。

书中把 56 位 DES 的经典穷尽约写成 3.5×10¹⁶ 步,Grover 约 2 亿步;√(3.5×10¹⁶)≈1.87×10⁸,与“2 亿”同一量级。这是原文给出的步数对照,不是实测破译记录。实用规模的量子计算在书中仍写为尚在探索。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 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 ]