← 返回刚才阅读的位置

知识卡片

普通读书笔记卡 · 3776.a

Grover放大目标测量概率

理解等级:中级

本书把 Grover 搜索与相干叠加态的干涉相连,又称其通过“概率的求反放大”提高目标结果的测量机会。可保留的联系是:量子算法需改变测量概率,让合格结果更可能出现;这不同于一次读出所有候选。书中未给目标标记、放大操作或迭代细节,不能仅凭这段话实现算法。平方查询量级及其适用边界见 [[Grover加速有问题边界]]。

量级对照(补充教学示例,非书中该节数据):集合大小 N=100 且仅一个合格元素时,经典为使成功率接近 100% 约需近 100 次试验;书中称 Grover 步数与 √N 成正比,√100=10。这只说明查询次数量级,不是把 10 写成实测步数。放大依赖相位取反再干涉,见 [[量子干涉可重分配测量概率]]。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 1 5 . 2 . 3 基 于 量 子 特 性 的 优 化 算 法 · 查看原书依据

      若该集合中只有一个元素符合要求,为使搜索成功率达到100%,一般说来步骤数要接近N;而在Grover算法中,搜索成功的运算步骤只与成正比[34],它对状态空间的快速搜索是通过概率的求反放大实现的。由此可以设想,它对优化问题也能构成快速搜索。

    参考来源

    - 位置:《智能算法导论》第 149 项《15.2.3 基于量子特性的优化算法》(源文件:`_epub-src/EPUB/xhtml/chapter15_0010.xhtml`) - 补充位置:第 143 项《15.1.2 状态的相干》(源文件:`_epub-src/EPUB/xhtml/chapter15_0004.xhtml`) - 结论依据:第143项将 Grover 与相干干涉相连;第149项称快速搜索通过概率的求反放大实现,并写经典步骤接近 N、Grover 与 √N 成正比。N=100 的开方是补充教学示例,非该节实验数据。 - 原始内容:Grover等量子算法主要利用了这一量子机制……它对状态空间的快速搜索是通过概率的求反放大实现的。