Decoded Quantum Interferometry Under Noise
中文速览 本文对一种名为“解码量子干涉”（DQI）的新型量子优化算法在噪声环境下的性能进行了严格的分析。DQI算法在理想情况下，能够利用目标函数傅里叶谱的稀疏性，为特定结构的问题提供指数级加速。然而，其在真实噪声环境中的鲁棒性此前尚不明确。本文的核心贡献在于，通过傅里叶分析方法，揭示了在局部退相干噪声模型下，DQI算法的性能与一个新提出的“噪声加权稀疏度”参数 \(\tau_1(B, \epsilon)\) 紧密相关。该参数直接关联了问题实例矩阵 \(B\) 的结构稀疏性与噪声强度 \(\epsilon\)。研究证明，算法的优化效果会随着实例矩阵稀疏度的降低（即约束中涉及的变量增多）而呈指数级衰减。这一理论发现通过在“最优多项式相交”和“最大异或可满足性”两个具体问题上的数值模拟得到了验证，为评估和保持DQI在实际应用中的量子优势提供了关键的理论指导。 English Research Briefing Research Briefing: Decoded Quantum Interferometry Under Noise 1. The Core Contribution This paper presents the first rigorous analysis of the Decoded Quantum Interferometry (DQI) algorithm’s performance in the presence of noise. The central thesis is that DQI’s resilience is fundamentally governed by the structural sparsity of the optimization problem instance. The authors’ primary conclusion is that the algorithm’s performance gain over random guessing decays exponentially as the problem’s constraints become less sparse. This relationship is precisely quantified by a novel noise-weighted sparsity parameter, \(\tau_1(B, \epsilon)\), which elegantly connects the algebraic structure of the problem to the physical noise level. This finding reveals a critical sensitivity in DQI, providing a clear criterion for identifying problem classes where its potential quantum advantage might be preserved on realistic hardware. ...