Quantum Approximation Complexity of Classical Optimization Problems

标题： 经典优化问题的量子近似复杂度
作者： Stuart Hadfield

问题陈述

本文针对量子优化算法缺乏严谨的最坏情况性能保证的问题进行了研究。虽然许多量子方法（如 QAOA、DQI）在特定实例上表现出高分，或提供了期望值（解码均值）的界限，但它们往往缺乏能够保证在所有输入上都达到特定近似比且具有有界误差的统一算法。本研究旨在正式定义经典近似复杂度类（APX、PTAS、FPTAS）的量子类比，并确定量子计算是否能在保证解质量或达到请求精度所需的时间方面，严格优于随机化经典算法。

方法论

作者将 NPO（NP 优化）问题的框架扩展到包含有界误差量子算法。

1. 量子类的定义： 本文定义了 BQ-APX、BQ-PTAS 和 BQ-FPTAS。这些类的成员资格要求存在一个统一的量子算法，该算法在每个输入上，以至少 $2/3$ 的概率返回一个可行的经典解，并达到声称的近似比。至关重要的是，运行时间包括所有步骤：参数选择、状态制备、测量、解码和重复。解的分数必须是经典可高效计算的。
2. 从解码均值到输出的转移： 引理 6 和推论 7 是一个关键的技术工具，它们建立了解码解的期望分数与有界误差经典输出保证之间的关系。这使得将基于期望值的分析（常见于量子文献）转化为类成员资格所需的严格输出保证成为可能。
3. 条件分离： 本文构建了特定的问题，以在标准复杂度假设（例如 $NP \not\subseteq BQP$ 和 $Factor \notin FBPP$）下展示量子类与经典类之间的严格包含关系。这些构建依赖于“搜索填充”（search padding）和密码学硬度。

核心贡献与结果

1. 量子近似类的形式化层级
在假设 $NP \not\subseteq BQP$ 的情况下，本文确立了量子近似类的严格层级：
$$BQ\text{-}FPTAS \subsetneq BQ\text{-}PTAS \subsetneq BQ\text{-}APX$$
该层级由以下经典问题见证：

• Max-E3SAT： 具有确定性的常数比近似（属于 APX），但没有量子 PTAS。
• 平面顶点覆盖（Planar Vertex Cover）： 具有确定性 PTAS，但没有量子 FPTAS。
  这些结果表明量子类之间是相互区别的，尽管对于这些特定问题，它们尚未实现与随机化经典类的分离。

2. 认证最大阶 (CMO)：一种强力的量子-经典分离
本文引入了 认证最大阶 (Certified Maximum Order, CMO) 问题，其目标是寻找模 $N$ 下某个元素的乘法阶，且该阶由该阶的素因子进行认证。

• 量子结果： 利用分解因数和周期寻找技术，一个有界误差量子算法可以在多项式时间内找到精确最优解（卡迈克尔函数 $\lambda(N)$）。因此，$CMO \in BQ\text{-}FPTAS$。
• 经典障碍： 任何保证甚至仅能达到多项式因子近似比的随机多项式时间算法，都会意味着存在随机多项式时间分解因数的算法。
• 结论： 在假设 $Factor \notin FBPP$ 的前提下，$CMO \in BQ\text{-}FPTAS \setminus R\text{-}POLY\text{-}APX$。这建立了一个条件分离，即量子算法可以提供精确解，而随机化经典算法甚至无法实现多项式因子的近似。

3. 离散对数拟合 (DLog-Fit)：阈值分离
本文定义了 DLog-Fit，这是一个涉及基于离散对数预测样本标签的问题。

• 经典基准： 确定性算法实现 $1/2$-近似（预测多数标签）。
• 量子优势： 量子算法可以找到完美拟合（精确最优）。
• 经典障碍： 任何通过随机化经典算法实现的相对于 $1/2$ 比例的固定改进，都将意味着解决了安全素数子群中的离散对数问题。
• 结论： 在假设安全素数离散对数不在 $FBPP$ 中的前提下，$DLog\text{-}Fit \in R\text{-}APX \cap BQ\text{-}FPTAS \setminus R\text{-}PTAS$。这展示了在 $1/2$ 近似阈值处的差距。

4. 通用搜索填充 (定理 8)
本文提供了一种通用的构造方法，表明任何具有高效可验证见证的搜索问题，都可以转化为一个具有 $1/2$ 近似阈值的 NPO 问题。如果存在一个量子求解器处理该搜索问题，但不存在随机化经典求解器，则所得优化问题属于 $BQ\text{-}FPTAS$ 但不在 $R\text{-}PTAS$ 中。

5. 对现有量子方法的分析
本文将这些定义应用于现有算法：

• QAOA： 对于 3-正则 MaxCut 的固定深度 QAOA，本文利用解码均值转移证明，通过重复可以产生有界误差输出保证（例如，超过最优解的 $2/3$），从而将该特定图族归入 $BQ\text{-}APX$。
• 解码量子干涉 (DQI)： 本文指出，虽然 DQI 在特定族（如折叠 OPI）上显示出改进的期望分数，但在显式输入时间模型中建立分离，需要证明随机化经典算法无法达到相同的比例，这对于不受限问题而言仍是一个开放性挑战。

意义与主张

本文声称提供了第一个关于有界误差量子近似类的严谨定义，并证明了在明确的复杂度假设下，量子计算可以严格改善相比于随机化经典计算的最坏情况近似保证。

• 范围适中： 作者明确指出，对于像 MaxCut 或 MaxSAT 这样常见的、不受限的问题，量子-经典在最坏情况输出比例上的差距仍然是一个开放问题。所建立的分离依赖于特定的、通常是密码学相关的题目构造（CMO、DLog-Fit）或受限的图族。
• 理论框架： 这项工作弥合了启发式量子性能（通常以期望值衡量）与严谨复杂度理论（有界误差输出保证）之间的鸿沟。它澄清了单纯的高基准分数在没有统一性和运行时间限制的情况下，并不足以确立近似类成员资格。
• 未来方向： 本文指出，寻找一种能够保证在标准问题（如不受限 MaxCut）上达到优于经典硬度阈值的统一量子算法，是该领域的核心开放问题。