量子科技中心_量科网

对于一般的max-k-XORSAT问题（k≥3），在最坏情况下，除非P=NP，否则没有多项式时间算法能比随机猜测做得更好：超越随机赋值的1/2近似值已是NP难问题。当每个变量最多出现在D个约束中时，情况发生了变化。在这个有界度数设定下，多项式时间算法能以约1/√D的加性量可靠地超越随机基线。对于布尔实例，这一缩放已知是最优的：相应的难度结果由Trevisan给出，而对应的算法保证由Barak等人建立。这一结论是否对一般有限域成立，以及它对量子算法意味着什么，此前尚未明确。该工作明确建立了这一联系，并将难度结果推广到有界度数D和任意有限域F_q上的max-Ek-LINSAT(q,r)问题，证明超越r/q + 𝒪_{q,r}(1/√D)是NP难的。这些结果为解码量子干涉测量(DQI)、QAOA和经典启发式算法所针对的有界度数实例提供了复杂度理论基准。因此，有界度数实例上的任何量子优势都仅限于常数前置因子。该工作进一步表明，在DQI背景下，对于(k,D)-正则实例，该前置因子对解码器的性质敏感：使用经典解码器的DQI面临信息论上的1/√(D log D)障碍，使其无法匹配难度缩放，而使用量子解码器的DQI则与1/√D缩放兼容——这揭示了量子解码是使DQI匹配复杂度理论缩放的关键要素。