量子算术的综述有个恼人的特点:每篇都自称覆盖全领域,但覆盖面互不重合,而且报的指标口径不同。一篇只讲 Clifford+T 门数,一篇只讲比特数,一篇只讲乘法的渐进复杂度。直接拿它们的表格横向对比,往往是在比较不同定义的量。这一页给出阅读顺序与口径对照。

为什么综述不能直接互相对照

三类最常见的口径错位:

  1. 门集不同。有的以 T 门计(Clifford+T 门集),有的以 Toffoli 计(Clifford+ 的可逆门集),有的以”通用门”计(把任意单比特旋转当免费)。Toffoli 与 T 的换算差 7 倍。
  2. 寄存器约定不同。就地(in-place)与非就地(out-of-place)加法器的比特数差一个量级;mod 与 mod 的深度差很多。表格里往往不写清。
  3. 是否含反计算不同。只报”计算部分”门数而不报反计算的表格,无法与含反计算的表格比较。

这三条与门代价模型讲的是同一件事的不同侧面:先把口径对齐,再看数字。

按需求选的阅读顺序

  • 想入门:先读量子算术线路总览建立概念地图,再读加法卷导读——加法是全领域的语法基础,其余各卷都是它的变体或下游。
  • 想做实现或比较:统一量子线路表示与比特序与寄存器约定是必读,因为它们决定的正是上面那三条口径。
  • 想做研究:直接从你要优化的那个算术族入手,横向对比看各卷末尾的资源对比表,而不是看综述里的汇总表。

本站为什么自己做对比表

因为可核验的汇总表很难找到。调研阶段发现若干篇被广泛引用的”综述”其实无法定位原始记录(编号指向无关论文、或标题与内容对不上),而能定位到的几篇又只覆盖部分算术族。本站的取舍是:宁可自己按统一口径重算,也不转抄口径不明的表格。具体做法见编写与取材说明。

代价是本站的对比表不完整 —— 凡是底稿未能核实到原始文献的部分,宁可留白或写明空白,也不用二手数字填满。

读综述时该追问的五个问题

  1. 报的 T 数还是 Toffoli 数?两者差 7 倍。
  2. 比特数含不含魔法态工厂?不含就无法比较墙钟时间。
  3. 就地还是非就地?寄存器宽度差多少?
  4. 算的是 mod 还是 mod ?后者多一个比较器。
  5. 反计算算进成本了吗?没算的表格不能和算了的表格并列。

这五问与门代价模型末尾的”一个必须警惕的比较陷阱”是同一份清单。

延伸阅读