arXiv · quant-ph· Robin Kothari, Tony Metger, Ryan O'Donnell, Noah Shutty, Kewen Wu·· 8 天前精选
研究为 F₃ⁿ 子集和问题提出指数量子加速，并严格分析二进制误差 LWE
Exponential quantum speedup for $\mathbb{F}_3^n$-Subset-Sum? Or, rigorous classical algorithms for Binary-Error LWE
arXiv:2609.40321v1阅读论文 PDF ↗
仅依据论文摘要整理；未读取全文，实验条件、证明与基准细节请核对原文。
作者：Robin Kothari, Tony Metger, Ryan O'Donnell, Noah Shutty, Kewen Wu
首次提交：2026-10-01 01:54
研究任务与主要进展
论文作者为 F₃ⁿ 子集和问题提出量子算法：对任意固定 ε>0，只需 m=ε·n² 个输入向量即可在多项式时间内求解，并建立指数运行时间与多项式运行时间之间的完整样本量—时间权衡。作者还严谨分析了二进制误差 LWE 的确定性经典算法，并改进了更大有限域上的经典算法。
阶段、条件与复现 · 深读核对
- 任务输出与输入访问模型是什么？
- 在什么假设、规模与资源条件下成立？
- 与哪种经典基线比较，是否计入编码与读出？
这些是阅读核对问题；材料未说明的条件保留未知。请结合上方论文版本、资料范围与原文核验。
本站判断
基于论文摘要，作者针对有限域子集和问题构造了量子算法，将可解规模推进到对任意固定 ε>0、m=ε·n² 的参数区间，并给出指数与多项式运行时间之间的完整样本量—时间权衡。主要技术增量还体现在对二进制误差 LWE 经典算法的严格化，以及更大有限域上经典算法的改进；这些结论的具体证明与实验细节需以全文核对。
来源：arXiv · quant-ph · arxiv.org