4. 经典基线的选择与构建

在量子算法基准测试中，经典基线不是“随便找个能跑的算法”，而是决定整个对比结论是否可信的参照系。一个不合理的基线会让量子算法看起来“已经超越经典”，而实际上只是击败了一个实现糟糕或复杂度类别不匹配的对手。因此，选择与构建经典基线，本质上是在为量子算法设定一个公平、可解释、可复现的竞争环境。

先确定比较的“复杂度类别”

选择基线的第一步，是明确量子算法所解决的问题属于哪一类，以及经典侧对应的是精确解、启发式还是近似算法。这三类基线在时间、精度和可扩展性上的承诺完全不同，混用会导致结论失真。

• 精确解基线：保证返回最优解，例如穷举搜索、动态规划、分支定界。适合小规模验证量子算法输出是否正确，但规模稍大就会因指数或高次多项式复杂度而不可用。
• 启发式基线：不保证最优，追求在合理时间内给出高质量可行解，例如模拟退火、遗传算法、禁忌搜索。适合组合优化类问题，如 Max-Cut、旅行商、投资组合优化。
• 近似算法基线：具有可证明的近似比或误差界，例如贪心、局部搜索、Goemans-Williamson 的 0.878 近似。适合需要理论保证、又无法承受精确解代价的场景。

例如，若量子算法是 QAOA 求解 Max-Cut，那么经典基线至少应包含：小规模下的精确解（用于验证 QAOA 是否真的找到最优）、中等规模下的 Goemans-Williamson 近似、以及大规模下的贪心或局部搜索启发式。只拿穷举做基线，会在 n=20 以上迅速失去可比性；只拿贪心做基线，又可能低估经典能力。

构建基线的四个关键参数

确定类别后，需要把基线落到可执行的实现上。以下四个参数决定了基线是否“合理”：

这些参数必须与量子侧保持一致。如果量子算法运行 100 次取最优，经典启发式只跑 1 次，对比就不公平。通常做法是：固定总时间预算或总采样次数，让双方在相同资源下竞争。

一个可执行的基线构建示例

以 Max-Cut 为例，构建三层经典基线。假设图 G 有 n 个节点，边权为 1，目标函数为割边数。

# 精确解：n ≤ 16 时使用暴力枚举
best = 0
for mask in range(1 << n):
    cut = sum(1 for (u,v) in edges if ((mask>>u)&1) != ((mask>>v)&1))
    best = max(best, cut)

# 近似算法：Goemans-Williamson（SDP 舍入）
# 求解 SDP 得到单位向量 v_i，随机超平面 r 舍入
# 期望近似比 ≥ 0.878

# 启发式：贪心 + 局部搜索
# 1. 随机初始划分
# 2. 逐节点尝试翻转，若割边数增加则接受
# 3. 重复直到无改进或达到时间预算

运行后记录每个规模下的最优值、平均值和运行时间。例如 n=12 时，精确解给出 18 条割边，GW 给出 17，贪心局部搜索给出 16。此时量子算法若在相同时间预算下给出 17，则可以说“达到 GW 水平”，而不是“超越经典”。

如何判断基线是否合理

构建完成后，用三个问题自检：第一，基线是否在相同问题规模和时间预算下运行？第二，基线的实现是否达到该算法在文献中的典型性能？第三，是否至少包含一个精确解用于小规模正确性验证？如果三个答案都是肯定的，这个基线才具备作为参照系的资格。

最后，基线不是一次性的。随着量子算法规模扩大，经典基线也应同步扩展：小规模用精确解，中规模用近似算法，大规模用启发式。只有让基线随问题规模“换挡”，对比才始终有意义。

这张图概括了本节的核心逻辑：从问题实例出发，按规模选择精确解、近似算法或启发式，再用统一的参数体系约束比较条件，最终得到可解释的对比结论。基线选得对，量子算法的“优势”才有意义；基线选得错，再漂亮的加速比也只是数字游戏。