量子科技中心_量科网

该研究团队针对max-LINSAT问题建立了紧密的不可逼近性界限，该问题旨在有限域𝔽q上最大化满足线性约束的数量，其中每个约束接受r个取值。具体而言，研究人员通过Håstad定理的直接归约证明：假设𝖯≠𝖭𝖯，任何多项式时间算法都无法超越随机赋值比率r/q的任何常数倍。这一阈值恰好对应于控制解码量子干涉测量（DQI）的半圆定律在ℓ/m→0时的极限——其中ℓ是底层编码的解码半径：随着可解码结构的消失，DQI的近似比率会精确退化至该工作确立的最坏情况界限。这些发现共同勾勒了最坏情况硬度与潜在量子优势之间的边界，表明任何超越r/q的算法都必须利用问题实例特有的代数结构。