解码量子干涉测量法：优化问题求解的新路径及其超多项式量子加速

《Nature》：Optimization by decoded quantum interferometry

本刊编辑推荐：为解决组合优化问题的量子加速难题，Stephen P. Jordan团队开发了解码量子干涉测量法(DQI)。该算法通过量子傅里叶变换将优化问题转化为解码问题，在有限域多项式拟合问题中实现超多项式加速。研究证明DQI在OPI问题上的表现超越经典算法，为量子优化算法开辟了新范式。

　　

在计算科学领域，实现组合优化问题的量子加速一直是研究人员追逐的圣杯。尽管经过三十年的探索，量子算法在优化问题上的超多项式加速证据仍然有限。传统基于哈密顿量的量子优化方法主要利用优化景观的局部结构，而这项发表于《Nature》的研究提出了一种创新性的量子干涉测量方法。

解码量子干涉测量法(DQI)的核心思想是利用量子傅里叶变换构建干涉图案，使目标函数值较大的解获得相长干涉。与基于哈密顿量的方法不同，DQI利用了组合优化问题目标函数傅里叶谱中普遍存在的稀疏性特征。

研究团队以最大异或可满足性问题(max-XORSAT)为例阐释DQI原理。该问题要求找到n比特字符串x满足尽可能多的线性模2方程Bx=v。通过Hadamard变换，DQI将优化问题转化为解码问题——具体来说，是求解具有汉明权约束的欠定线性系统，这等价于经典纠错码的校验子解码问题。

DQI算法通过五个关键步骤制备|P(f)>状态：制备Dicke态叠加、施加相位、计算矩阵乘积、通过解码问题反计算y态、应用Hadamard变换。当矩阵B具有稀疏性或特定代数结构时，即使错误数?较大（如与m线性相关），解码问题仍可高效求解。

研究方法上，团队主要采用了量子算法设计、经典解码算法集成（包括Berlekamp-Massey算法和置信传播算法）、理论证明与数值实验相结合的方法。通过分析最优多项式相交(OPI)问题和稀疏max-XORSAT实例，系统评估DQI性能。

最优多项式相交问题研究

OPI问题要求找到次数不超过n-1的多项式Q∈F_p[y]，最大化与给定子集F_y的交集数量。研究显示OPI是max-LINSAT的特殊情况，其中B为Vandermonde矩阵，C^⊥为Reed-Solomon码。利用Berlekamp-Massey解码器，DQI在多项式时间内达到半圆定律预测的近似最优解。

在r/p=1/2的平衡情况下，当n/p=1/10时，经典Prange算法仅满足55%约束，而DQI达到约71.79%的满足率。在n/p≈r/p≈1/2的参数下，DQI更实现93.3%的约束满足率，展现出明显的量子优势。

稀疏max-XORSAT实验

研究团队进一步将DQI应用于稀疏max-XORSAT实例，这些问题可转化为低密度奇偶校验(LDPC)码解码问题。实验使用包含31,216个变量和50,000个约束的实例，比较DQI+BP与多种经典启发式算法。

结果显示，DQI+BP在8秒内达到的约束满足率，模拟退火算法需要73小时（五核并行）才能匹配。尽管针对该实例可以设计专门的经典启发式算法略微超越DQI+BP，但这一比较证明了DQI在特定问题上的竞争力。

研究结论与讨论

DQI算法的重要意义在于建立了优化问题与解码问题的桥梁，使量子傅里叶变换与经典解码理论深度融合。该方法不仅为OPI问题提供了超多项式量子加速的证据，还开辟了通过编码理论指导量子算法设计的新范式。

研究团队指出了三个未来方向：多变量OPI问题扩展、针对max-XORSAT的定制解码器开发、以及公平采样问题的探索。多变量OPI将导向Reed-Muller码解码，有望进一步扩展量子优势的范围。而量子解码器的发展可能使DQI即使在小k值的max-XORSAT问题上也实现优势。

该研究通过严格的数学证明和系统的实验验证，确立了DQI在量子优化算法家族中的独特地位。与Yamakawa-Zhandry问题的联系进一步表明，DQI难以通过经典算法进行相对化模拟，这为其量子优势提供了理论基础。

这项工作的最大价值在于提供了一条不依赖于哈密顿量方法的量子优化新路径，将量子计算与经典编码理论的丰富成果相融合，为在未来量子设备上解决实际优化问题奠定了基础。随着量子硬件的进步和解码算法的发展，DQI有望在组合优化、密码学和机器学习等领域发挥重要作用。