量子科技中心_量科网

最优多项式交集问题（OPI）定义如下：给定集合S₁,…,Sₘ⊆𝔽及评估点a₁,…,aₘ∈𝔽，寻找次数小于n的多项式Q∈𝔽[x]，使得Q(aᵢ)∈Sᵢ对尽可能多的i∈{1,2,…,m}成立。解码量子干涉仪（DQI）是一种量子算法，能高效地为该问题提供优质解，即使在最坏情况实例中亦然（Jordan等，2025）。该算法返回解的质量遵循半圆定律，其表现优于已知经典高效算法。但DQI是否获得了理论最优解？即对于最坏情况下的OPI实例，是否存在超越半圆定律的解？令人惊讶的是，在本研究之前，最佳存在性结果竟与最佳算法结果完全重合（且由其推导得出）。 本研究证明，在素域上的最坏情况OPI实例存在更优解。具体而言，DQI与半圆定律并非最优。例如当列表Sᵢ的规模为ρp且ρ∼1/2时，该团队的结果表明：只要n/m≥0.6225，就存在渐近超越半圆定律的解；而当n/m≥0.7496时，则存在渐近完美解。该结果可推广至任意最大距离可分（MDS）码导出的Max-LINSAT问题，以及任意ρ∈(0,1)的情况。突破性发现源于与秘密共享方案局部泄漏鲁棒性的关联，在此过程中该团队还复现了多个达到半圆定律解的存在性证明。