4. QAOA与经典优化对比

在组合优化实践中，选择算法本质上是在“解质量、求解时间、可扩展性”三者之间做权衡。精确算法、启发式算法、近似算法分别占据不同的适用边界，而QAOA（Quantum Approximate Optimization Algorithm）作为一种量子近似算法，其定位并非全面替代经典方法，而是在特定结构的问题上提供新的求解路径。理解这些边界，是判断“什么问题值得上量子”的前提。

三类经典算法的边界

精确算法保证找到全局最优解，典型代表是分支定界、分支切割、动态规划以及整数规划的割平面法。它们的代价是最坏情况下的指数级时间复杂度。以旅行商问题（TSP）为例，20个城市以内用Held-Karp动态规划（复杂度O(n²2ⁿ)）尚可接受；30个城市时状态数已达约3×10¹⁰，内存与时间都难以承受。因此精确算法的适用边界通常是：问题规模小（数十个变量以内）、约束结构允许强剪枝、或对最优性有硬性要求（如医疗排班、金融合规校验）。

启发式算法不保证最优，但能在可接受时间内给出高质量可行解，包括贪心、局部搜索、模拟退火、遗传算法、禁忌搜索、蚁群算法等。它们适合大规模、约束复杂、目标函数不规则的场景，例如上千节点的物流路径规划、芯片布局布线。启发式算法的风险在于：解质量依赖参数与初始解，缺乏可证明的性能保证，容易陷入局部最优。

近似算法介于两者之间：它在多项式时间内给出有理论保证的近似比。例如，顶点覆盖问题的2-近似算法、度量TSP的1.5-近似（Christofides算法）、MAX-CUT的0.878-近似（Goemans-Williamson SDP松弛）。近似算法的边界是：问题必须具有可被松弛和舍入的结构，且近似比在可接受范围内。对于一般MAX-CUT，0.878已是经典多项式时间下的较优保证。

QAOA的定位与潜在优势场景

QAOA属于量子近似算法。它把组合优化问题编码为伊辛模型或QUBO，通过交替施加代价哈密顿量和混合哈密顿量演化，构造参数化量子态，再测量得到候选解。其近似比随电路层数p增加而提升，p→∞时理论上可逼近最优。当前含噪声中等规模量子（NISQ）设备上，p通常只能取1～5，因此QAOA的实际表现仍受限于量子比特数、门保真度和测量采样次数。

QAOA的潜在优势场景集中在以下几类：第一，问题天然对应伊辛/自旋玻璃结构，如MAX-CUT、图着色、社区发现，编码直接、哈密顿量简洁；第二，经典算法陷入瓶颈的中等规模问题，例如数百节点、约束密集、精确算法不可行而启发式解质量波动大的实例；第三，需要多次采样候选解的场景，QAOA测量天然输出比特串分布，可一次性获得多个候选解，适合与经典后处理结合；第四，与经典优化形成混合回路，用量子处理器生成候选，用经典优化器调参或做局部改进。

一个可操作的对比示例

考虑一个50节点的MAX-CUT实例，边密度约0.3。精确算法（分支定界）在普通工作站上通常数小时内可解，但若节点增至200，精确算法基本不可行。此时可用经典近似算法（Goemans-Williamson SDP）获得约0.878近似比的解，或用模拟退火跑10⁶次迭代获得经验上接近最优的解。QAOA在此规模下，若量子比特数足够且p=3～5，理论上可探索经典局部搜索难以覆盖的解空间区域，但当前硬件下其采样解的质量往往还不及成熟的经典启发式。

因此，判断是否使用QAOA，可参考以下决策逻辑：

总结来看，精确算法守住小规模最优性，启发式算法覆盖大规模可行性，近似算法提供结构化保证，而QAOA的潜在价值在于：当问题可自然映射为伊辛模型、经典方法在中等规模上出现质量瓶颈、且允许混合量子-经典迭代时，它提供了一条不同于经典路径的探索方向。当前阶段，理性做法是把QAOA视为经典优化工具箱中的补充项，而非替代项。