量子算术的综述有个恼人的特点:每篇都自称覆盖全领域,但覆盖面互不重合,而且报的指标口径不同。一篇只讲 Clifford+T 门数,一篇只讲比特数,一篇只讲乘法的渐进复杂度。直接拿它们的表格横向对比,往往是在比较不同定义的量。这一页给出阅读顺序与口径对照。
为什么综述不能直接互相对照
三类最常见的口径错位:
- 门集不同。有的以 T 门计(Clifford+T 门集),有的以 Toffoli 计(Clifford+ 的可逆门集),有的以”通用门”计(把任意单比特旋转当免费)。Toffoli 与 T 的换算差 7 倍。
- 寄存器约定不同。就地(in-place)与非就地(out-of-place)加法器的比特数差一个量级;mod 与 mod 的深度差很多。表格里往往不写清。
- 是否含反计算不同。只报”计算部分”门数而不报反计算的表格,无法与含反计算的表格比较。
这三条与门代价模型讲的是同一件事的不同侧面:先把口径对齐,再看数字。
按需求选的阅读顺序
- 想入门:先读量子算术线路总览建立概念地图,再读加法卷导读——加法是全领域的语法基础,其余各卷都是它的变体或下游。
- 想做实现或比较:统一量子线路表示与比特序与寄存器约定是必读,因为它们决定的正是上面那三条口径。
- 想做研究:直接从你要优化的那个算术族入手,横向对比看各卷末尾的资源对比表,而不是看综述里的汇总表。
本站为什么自己做对比表
因为可核验的汇总表很难找到。调研阶段发现若干篇被广泛引用的”综述”其实无法定位原始记录(编号指向无关论文、或标题与内容对不上),而能定位到的几篇又只覆盖部分算术族。本站的取舍是:宁可自己按统一口径重算,也不转抄口径不明的表格。具体做法见编写与取材说明。
代价是本站的对比表不完整 —— 凡是底稿未能核实到原始文献的部分,宁可留白或写明空白,也不用二手数字填满。
读综述时该追问的五个问题
- 报的 T 数还是 Toffoli 数?两者差 7 倍。
- 比特数含不含魔法态工厂?不含就无法比较墙钟时间。
- 就地还是非就地?寄存器宽度差多少?
- 算的是 mod 还是 mod ?后者多一个比较器。
- 反计算算进成本了吗?没算的表格不能和算了的表格并列。
这五问与门代价模型末尾的”一个必须警惕的比较陷阱”是同一份清单。