用量子干涉技术优化新方法

NP难问题结果表明，对于许多优化问题的最坏情况实例，无论是经典还是量子多项式时间算法，可能都无法找到精确最优解，甚至足够好的近似最优解。然而，仍有一些组合优化问题（如最近向量问题），经典多项式时间算法的最佳近似结果与最强的复杂性理论不可近似结果之间存在巨大差距。考虑平均情况复杂性时，这种差距更为普遍，因为已知的平均情况不可近似结果很少。这些差距为量子计算机提供了潜在机会，即量子计算机可能在多项式时间内实现经典算法需超多项式时间才能达到的近似精度。

过去三十年，组合优化量子算法一直是研究热点，已发现某些优化问题可能存在超多项式量子加速的证据，但实现这一优势极具挑战性且尚未完全解决。

本文提出一种基于干涉模式的量子优化算法——解码量子干涉测量（DQI）。DQI利用量子傅里叶变换，使目标函数值较大的符号串的量子振幅发生相长干涉，从而提高测量时获得良好解的概率。与基于哈密顿量的量子优化方法不同，DQI利用目标函数傅里叶谱中的稀疏性，若谱有更复杂结构也可利用。

为说明DQI本质，先将其应用于最大异或可满足性（max-XORSAT）问题。该问题给定m×n矩阵B（m>n），需找n位串x，满足尽可能多的模2线性方程Bx=v。其目标函数f(x)为满足方程数与不满足方程数之差，f的阿达马变换非常稀疏，因此易制备量子态。通过制备狄克态、施加相位、计算B^T y、解码（利用纠错码伴随式解码）、阿达马变换等步骤，可制备|P(f)⟩态，测量该态即得优化问题的近似解。

解码通常是NP难的，但当B稀疏或有代数结构时，经典多项式时间算法可解。制备|P(f)⟩态的门数为O(T+m²)，T为解码算法的量子门数。多项式P的次数越高，越能将测量偏向目标值大的串，但需解决更难的解码问题。

本文主要将DQI应用于最大线性可满足性（max-LINSAT）问题，其定义为：在有限域Fₚ上，给定矩阵B和每个约束对应的Fᵢ子集，找x使满足约束数最多。max-XORSAT是p=2且每个|Fᵢ|=1的特例。

对于每个Fᵢ大小为r的max-LINSAT实例，若有多项式时间算法能纠正码C^⊥（C^⊥={d∈Fₚᵐ | B^T d=0}）的至多ℓ个错误，则DQI可在多项式时间内达到近似最优解，其期望满足约束比例由公式（6）给出（称为“半圆律”），该公式将解码性能与优化近似直接关联，为量子优化开辟两条研究路径：借鉴编码理论的解码定理推导DQI性能保证；通过计算机实验比较经典解码启发式与优化启发式的经验性能。

首先，利用严格解码保证分析DQI在最优多项式交（OPI）问题上的性能。OPI问题是在有限域Fₚ上，找次数至多n-1的多项式Q，使其与尽可能多的Fᵧ子集相交。DQI将OPI转化为里德-所罗门码的解码问题，利用Berlekamp-Massey算法可多项式时间解码至码距一半。在r/p=1/2且n/p为常数的情况下，DQI的满足率超过经典Prange算法，而经典算法要达到此精度需指数时间，故DQI实现超多项式加速。

虽然OPI在某些参数范围的经典难处理性尚无直接证明，但特定限制情况（如最大似然解码里德-所罗门码）已知是NP难的。例如，当n≈p/10、r/p≈1/2时，Prange算法满足率为0.55，而DQI达约0.7179，挑战经典算法在此参数下的多项式时间性能。对于n/p≈r/p≈1/2的OPI实例，DQI满足率达0.933，而经典算法在p=521时计算成本极高；DQI结合Berlekamp-Massey解码器，制备|P(f)⟩态约需1×10⁸个逻辑Toffoli门和9×10³个逻辑量子比特。

其次，通过计算机实验在稀疏max-XORSAT实例上对比DQI与经典启发式算法。DQI将稀疏max-XORSAT转化为低密度奇偶校验（LDPC）码解码问题，标准置信传播解码可高效处理。通过调整B的稀疏模式，发现某些稀疏max-XORSAT实例中，DQI结合置信传播解码在相同计算步骤内找到的满足约束比例高于尝试的所有通用经典优化启发式算法（如模拟退火）。不过，针对这些实例可构建定制经典算法（如带温度依赖权重的模拟退火变体），在7分钟内略超DQI+置信传播的性能；但模拟退火需5核运行73小时才能达到DQI+置信传播8秒单核心的结果，差距达五个数量级（需注意这非量子与经典运行时的直接指标，因量子解码需可逆电路和纠错开销）。

讨论部分指出，DQI的思想源于早期格问题量子算法，与线性码紧密相关。Yamakawa和Zhandry的工作表明，某些Oracle问题量子查询复杂度远低于经典，DQI可扩展至此问题，表明其难被经典算法模拟。

最后，DQI开启了量子加速探索，但仍需深入研究：多元OPI（转化为里德-穆勒码解码，有望存在超多项式加速参数区域）、max-XORSAT定制解码器（需开发适应高密度校验矩阵的解码器或量子解码器）、采样问题（DQI能公平采样给定目标值的解，应用于近似计数）。