按年被提到
20162016 · 2 次2026
物理与量子›量子计算·arXiv:1611.06999 · quant-ph

An Efficient Quantum Algorithm for a Variant of the Closest Lattice-Vector Problem

针对一种最近格向量问题变体的高效量子算法
Lior Eldar, Peter W. Shor · 2016

声称给出量子算法求解一类格上有界距离解码问题(后被撤回)

开始阅读 ↗PDFalphaXiv 讨论
被提及 · 3 人首次 2016-11-23 · 最近 2017-05-24
3不同的人
3活跃月份
3讨论串
0被引(OpenAlex)

利用此前引入的格的标准形式 SysNF(基向量满足某种互素条件)对格做“平滑”分析,设计出一个量子算法,声称能高效求解有界距离解码问题的一个变体:给定格 L、向量 v 以及 a、b,判定 v 到 L 的距离是在 [a/2, a] 内还是至多为 b。摘要指出,若能把参数改进到 a = b = λ₁(L)/√n,就会推翻 LWE 密码体制抗量子攻击的一个安全假设。

HN 为什么提它

评论者主要拿它当“声称量子攻破 LWE 的论文后来被撤回”的例子,也提醒点开 v1 仍能看到原来有错误的版本。

方法难度 5 / 5约 90 分钟有时效性
读之前最好知道
1格与格密码学(lattice)
2Learning with Errors(LWE)
3量子算法基础
4有界距离解码问题(BDD)

学习路径

读这篇之前,按顺序读书架上的 1 篇 · 参考文献来自 OpenAlex,顺序和要点由 Claude Code 排出

先读 Shor 算法,了解量子算法如何解决格相关问题背后的数论问题,再读这篇声称给出格问题量子算法的论文。

  1. 1
    Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer量子计算机上素因数分解与离散对数的多项式时间算法 · 1995

    量子算法求解隐含周期结构问题的代表,目标论文类似地声称利用量子变换解格问题

    读看量子傅里叶变换与周期查找的思路,不必深究数论细节

  2. 2
    An Efficient Quantum Algorithm for a Variant of the Closest Lattice-Vector Problem针对一种最近格向量问题变体的高效量子算法 · 2016 · 就是这篇

    声称给出格上有界距离解码变体的量子算法(后被撤回)

    读看 SysNF 的平滑分析和算法声称的参数范围,同时留意该结论后来被撤回

HN 书评

推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及
批评greeneggs · 2016-12

“But if you click on v1, you can still access the original paper (incorrect, in this case).”

Library-managed 'arXiv' spreads scientific advances rapidly and worldwide原评论 ↗
引用VLM · 2017-05

“there was that paper around Thanksgiving last year (which did get retracted) claiming to partially quantum break LWE.”

提到去年那篇声称部分量子破解 LWE 后被撤回的论文
Post-quantum RSA原评论 ↗
被提交为 story · 1 次