Fault-tolerant cost of shallow QAOA on near-symmetric optimization problems

技术摘要：浅层 QAOA 在近对称优化问题上的容错成本

问题陈述
Montanaro 和 Zhou [1] 证明了深度为 1 的量子近似优化算法（QAOA）电路可以以常数概率 $\Omega(1)$ 找到某些近对称约束满足问题（CSP）的植入解（planted solution）。相比之下，这些问题的显式实现表现出经典强力求解器明显的指数级运行时扩展。虽然这暗示了经验性的指数加速，但实现在早期容错量子计算机上实现这些电路的资源需求尚不明确。这些问题的代价哈密顿量包含 $\Theta(n^\ell)$ 个子句（其中 $\ell \ge 5$），这意味着在使用标准的 Clifford+$T$ 合成时，其非 Clifford 门计数规模为 $\tilde{O}(n^\ell)$。这种规模使得相关的实际问题规模超出了早期容错硬件的能力范围。

方法论
作者分析了应用于这些近对称实例的深度为 1 QAOA 电路的容错资源成本，特别关注相位分离层（phase-separator layer）的合成。分析过程分为三个主要步骤：

1. 相位匹配与角度缩放： 作者重新审视了实现常数成功概率所需的相位匹配条件。对于相对于植入解在变量置换下对称的代价函数，相位分离角 $\gamma$ 必须满足 $\gamma = \Theta(n^{1-\ell})$，以确保主汉明壳（Hamming shells）的相长干涉。
2. 小角度合成： 利用 $\gamma$ 随系统规模减小的特性，作者应用了小角度 Clifford+$T$ 旋转合成技术（具体为 Bothe 等人 [9] 的方法）。他们利用准概率和概率混合形式，其中小角度旋转以高概率被近似为恒等变换，只有极小比例的旋转需要进行非 Clifford 合成。
3. 显式子句编译与泄漏分析： 作者从值算符模型（仅查询代价值 $C(x)$）过渡到电路编译所需的显式子句列表模型。他们通过分析由显式子句列表导出的代价函数的傅里叶系数，来确定编译过程是否会无意中泄露解。
4. 欺骗性实例构建： 为了测试这种加速相对于利用显式结构的经典攻击的鲁棒性，作者构建了“非植入”近对称实例。这些实例具有一个包含 NP-难子问题的指数级大的最优汉明壳，其代价景观（cost landscape）旨在诱捕局部搜索算法。

核心贡献与结果

• 二次方非 Clifford 缩放： 主要结果是，针对这些实例的深度为 1 QAOA 的非 Clifford 代价降低至 $\tilde{O}(n^2)$，且与子句局部性 $\ell$ 和稀疏化率无关。这种降低是因为总相位质量（$m\gamma$，其中 $m$ 是子句数量）随 $n$ 线性缩放，而小角度合成成本取决于该相位质量的平方。因此，此前因 $\tilde{O}(n^\ell)$ 缩放而被认为不可行的规模，现在在早期容错设备上变得可行（见图 2）。
• 植入族中的经典泄漏： 对于文献 [1] 中研究的植入族，作者表明编译所需的显式子句列表暴露了植入解。相位匹配条件（$F'(1/2) \neq 0$）固定了代价函数的一阶傅里叶系数（局部场）的符号。这些符号可以通过对子句列表进行简单的线性时间经典扫描，直接通过局部场揭示植入解 $s$。因此，虽然 QAOA 能以常数概率成功，但显式实现使得该问题在经典层面变得平凡。
• 非植入实例的存在性： 作者证明了小角度机制和 $\tilde{O}(n^2)$ 成本缩放并不依赖于植入解的存在。他们构建了没有植入解的近对称实例，其中：
  • 全局最优解位于一个指数级大的汉明壳内。
  • 在该壳内寻找精确最优解是 NP-难的。
  • 代价景观具有“欺骗性”，会使局部搜索和通用 MaxSAT 求解器陷入次优区域，并被高能垒隔开。
  • 在小角度下的深度为 1 QAOA 同样能将输出集中在最优壳上，并保持 $\tilde{O}(n^2)$ 的非 Clifford 成本。
  • 在这些非植入情况下，一阶系数是均匀的，不会揭示解，从而保留了对不利用特定对称结构的经典算法的难度。

意义
本文确立了低深度 QAOA 在近对称问题上的经验加速可以在显著低于此前假设的容错资源下实现，即 $\tilde{O}(n^2)$ 个非 Clifford 门而非 $\tilde{O}(n^\ell)$。这使得这些浅层、小角度电路成为早期容错硬件的一个现实目标。

然而，作者谦虚地指出存在一个关键的权衡：实现小角度合成的机制（相干局部场）同时也使解暴露于经典攻击之下（在植入场景中）。这项工作的意义在于识别了一个可以实现高效优化路径的区间，同时强调了支持这种效率的特定结构特性可能是一把双刃剑。作者总结道，核心的开放性问题在于，这种“廉价”的小角度机制是否可以扩展到更深的电路或不同的问题结构中，从而在保持对低阶经典攻击隐藏的同时，实现一种既是容错廉价又是经典抗性的真正量子优势。