知识卡片
量子变换门数不能代表端到端成本
书中将长度 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 个量子比特。
这个数只描述该输入模型下的变换电路;若要比较完整任务,还须计入经典数据装载成量子态、测量读出及所需精度。本节没有这些成本,不能据门数宣称端到端加速。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 1 5 . 2 . 6 量 子 小 波 与 小 波 包 算 法 · 查看原书依据
假设信号可以用n个量子比特表示,N=2n为输入信号的长度,在经典计算机上需要O(N)步运算来实现小波变换,O(NlogN)步来实现小波包变换。
参考来源
- 位置:《智能算法导论》第 152 项《1 5 . 2 . 6 量 子 小 波 与 小 波 包 算 法》(源文件:`_epub-src/EPUB/xhtml/chapter15_0013.xhtml`)
- 结论依据:原文以 n 个量子比特表示 N=2ⁿ 个输入量为假设,给经典变换与量子基本门数的数量级;XHTML 的 2 为上标,但未讨论制备和读出。N=1024 的量级演算为依据书中复杂度式补充的示例,不是书中数据或实测。
- 原始内容:假设信号可以用 n 个量子比特表示, N =2 n 为输入信号的长度