知识卡片

普通读书笔记卡 · 3781.a

量子变换门数不能代表端到端成本

理解等级:中级

书中将长度 N=2ⁿ 的信号已由 n 个量子比特表示作为前提,称周期化的小波及小波包变换可用 O(log²N) 个基本量子门,而经典计算机上小波变换需 O(N) 步、小波包变换需 O(N log N) 步。

演算(补充,只看量级、忽略常数):N=1024 时 n=log₂N=10,log²N≈100,而 N log N≈10240。差距来自“信号已在 10 个量子比特里”这个前提——经典算法要逐个处理 1024 个数,量子电路只作用于 10 个量子比特。

这个数只描述该输入模型下的变换电路;若要比较完整任务,还须计入经典数据装载成量子态、测量读出及所需精度。本节没有这些成本,不能据门数宣称端到端加速。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《智能算法导论》第 152 项《1 5 . 2 . 6 量 子 小 波 与 小 波 包 算 法》(源文件:`_epub-src/EPUB/xhtml/chapter15_0013.xhtml`) - 结论依据:原文以 n 个量子比特表示 N=2ⁿ 个输入量为假设,给经典变换与量子基本门数的数量级;XHTML 的 2 为上标,但未讨论制备和读出。N=1024 的量级演算为依据书中复杂度式补充的示例,不是书中数据或实测。 - 原始内容:假设信号可以用 n 个量子比特表示, N =2 n 为输入信号的长度