量子科技中心_量科网

在该工作中，研究人员提出了一种（非交互式、可验证的）证明量子优越性的新方法——通过求解从特定分布中抽取的有限域𝔽₂上（欠定）常次数多元方程组的平均情况𝖭𝖯搜索问题。具体而言，对于任意d≥2，该团队设计了𝔽₂上m<n个次数不超过d的多项式{pᵢ(x₁,…,xₙ)}ᵢ∈[m]的分布，并证明存在预期多项式时间量子算法能对随机向量(y₁,…,y_m)同步求解方程组{pᵢ(x₁,…,xₙ)=yᵢ}ᵢ∈[m]。另一方面，虽然解大概率存在，但通过对现有经典密码分析的全面审视，该工作推测当常数d>2时经典计算难以找到解。该研究由此提出三次函数足以实例化随机预言机以获得非相对化量子优势。 该研究始于Yamakawa-Zhandry（FOCS 2022）突破性量子算法框架。该工作证明该框架可扩展到多元多项式系统场景。 核心技术贡献是对𝔽₂多元多项式一般分布族诱导的傅里叶谱新分析——该类分布需满足2阶独立性与平移不变性，包含所有常数d≥2的均匀随机次数不超过d的多项式分布。该分析为其他多元系统的量子密码分析开辟了潜在新方向。