量子科技中心_量科网

近期，该团队证明了(6.6.6平面)颜色码中的最小权重解码是NP难的。然而，是否有可能在多项式时间内任意精确地近似最小权重解码，这仍然是一个悬而未决的问题。在本文中，作者证明了这是可行的：对于任意 \(\varepsilon>0\)，存在一个多项式时间算法，给定一个综合征后，能够找到一个生成该综合征的误差集合，其权重最多为最小权重解码权重的 \(1+\varepsilon\) 倍。由此可知，对于任意 \(\varepsilon>0\)，存在一个多项式时间算法，能够纠正距离 \(d\) 颜色码中权重不超过 \((1-\varepsilon)d/2\) 的所有误差（即几乎达到理论极限 \(d/2\)）。该研究给出的多项式在实践上规模过大，但为设计合理的多项式时间近似最小权重解码算法打开了大门，并特别表明近似解码并非NP难问题。