2. 量子算法与经典算法的对比框架

要判断一个量子算法是否真的“更好”，不能只看它是否利用了叠加、纠缠或干涉，也不能只看某一次实验是否跑出了结果。真正可比较的对象，必须被放进同一套坐标系中：同一个问题定义、同一套输入规模度量、同一类资源口径、同一种精度要求，以及同一组可扩展性假设。否则，“量子加速”很容易变成不同问题、不同指标之间的错位比较。

本节要建立的，是一个面向算法评估的统一对比框架。它的核心不是给出某个固定结论，而是提供一组可操作的维度，使量子算法与经典基线能够在同一张表、同一张图上被公平地审视。

一、五个核心维度：问题规模、复杂度、资源消耗、精度、可扩展性

统一对比坐标系可以拆成五个相互关联的维度。它们不是并列的五个标签，而是从“问题如何定义”到“算法如何增长”再到“实际能否落地”的递进关系。

• 问题规模：必须明确规模参数是什么。例如，整数分解中的比特长度 n，线性方程组中的矩阵维度 N，组合优化中的变量个数 m，量子化学中的电子数或基函数个数。规模参数选错，复杂度曲线就没有意义。
• 复杂度：包括经典时间复杂度、量子时间复杂度，以及两者所依赖的电路深度、门数量或查询次数。复杂度必须写成规模参数的函数，例如 O(N)、O(√N)、O(poly(n))，而不是只写“更快”。
• 资源消耗：经典侧关注内存、CPU 时间、通信量；量子侧关注逻辑量子比特数、物理量子比特数、T 门数量、电路深度、测量次数和纠错开销。资源消耗往往决定“理论加速”能否变成“实际可运行”。
• 精度：经典算法常以浮点误差、迭代残差或近似比衡量；量子算法则涉及采样误差、门保真度、读出误差和统计置信区间。比较时必须把精度目标对齐，例如都要求误差小于 ε，或都要求达到某个成功概率。
• 可扩展性：关注规模增大时，资源与精度如何变化。一个算法在小规模上表现良好，不代表它在大规模上仍占优。可扩展性通常通过复杂度阶、常数因子、并行度和纠错阈值来综合判断。

二、统一对比坐标系的构建方法

建立坐标系时，建议按以下顺序固定口径。第一步，写出问题的形式化定义，包括输入、输出和判定条件。第二步，选定唯一的规模参数 n，并说明它与实际数据量的关系。第三步，为经典基线和量子算法分别列出时间、空间、精度和成功概率。第四步，把资源折算到同一单位，例如经典侧用“基本操作次数”，量子侧用“逻辑门数量 + 测量次数”。第五步，画出随 n 变化的曲线或表格，观察交叉点与渐近趋势。

这里有一个关键原则：比较必须在同一精度约束下进行。如果经典算法允许近似解，而量子算法要求精确解，那么两者的复杂度不可直接相减。同样，如果量子算法只报告查询复杂度，却忽略电路深度和纠错开销，那么它只完成了部分比较。

三、复杂度对比：不能只看阶，还要看常数与深度

复杂度是坐标系中最容易被误用的维度。经典算法常以时间复杂度 T(n) 表示，量子算法则常以查询复杂度 Q(n) 表示。查询复杂度只统计对黑盒的调用次数，不统计每次调用内部的电路代价。因此，当有人说“量子算法只需 O(√N) 次查询”时，必须追问：每次查询对应的电路深度是多少？是否需要 O(log N) 个辅助比特？纠错开销是否被计入？

一个更完整的写法是同时给出三元组：(查询次数, 电路深度, 逻辑量子比特数)。例如，Grover 搜索在理想情况下查询次数为 O(√N)，但电路深度与 √N 同阶，且需要 O(log N) 个量子比特。经典线性搜索需要 O(N) 次查询。两者对比时，量子侧的优势体现在查询次数上，但代价是深度和比特数。如果深度受限于相干时间，实际加速可能被大幅压缩。

四、资源消耗：从逻辑量子比特到物理量子比特

资源消耗是连接理论与工程的关键维度。量子算法论文常报告逻辑量子比特数，但真实硬件需要纠错，物理量子比特数可能是逻辑数的数百到数千倍。例如，一个需要 100 个逻辑量子比特、T 门数量为 10^10 的算法，在表面码纠错下，物理量子比特数可能达到 10^5 量级，运行时间也可能从理论上的微秒级膨胀到小时级。

因此，资源对比表应至少包含以下字段：逻辑量子比特数、物理量子比特数估算、T 门数量、电路深度、测量次数、经典内存占用、经典 CPU 时间。只有把这些字段放在同一张表中，才能判断量子算法是否在目标硬件上可行。

五、精度与可扩展性：决定“能不能用”的边界

精度维度要求把误差来源拆开。经典侧通常有截断误差、迭代残差和浮点舍入误差；量子侧有门保真度、读出误差、采样统计误差和退相干误差。比较时，应统一到“达到目标精度所需的资源”这一口径。例如，都要求残差小于 10^-6，然后比较各自需要多少次迭代或多少次采样。

可扩展性则关注规模增大时的行为。一个实用的判断方法是画出资源随 n 变化的曲线，观察量子曲线与经典曲线是否存在交叉点。如果交叉点出现在 n=10^6 以上，而当前硬件只能支持 n=10^2，那么该量子算法在当前阶段不具备实际优势。可扩展性分析必须明确假设：是否允许近似、是否允许并行、纠错阈值是否达标。

六、可复用的对比检查表

下面给出一份可直接用于算法评估的对比检查表。它不依赖具体算法，而是作为统一坐标系的落地工具。

统一对比坐标系的价值，在于把“量子算法更快”这种模糊判断，转化为可检查、可复现、可争论的结构化结论。问题规模决定比较的起点，复杂度描述增长趋势，资源消耗决定工程可行性，精度约束保证公平性，可扩展性则回答“规模变大后是否仍然成立”。只有五个维度同时对齐，量子算法与经典基线的对比才真正有意义。