“For the true version see here”
Shor's Algorithm Does Not Factor Large Integers in the Presence of Noise
证明在随机噪声超过极小水平时 Shor 算法不能分解 pq
论文在含噪声量子门的设定下考察 Shor 量子分解算法。在(受控)旋转门的一般随机噪声模型下,他证明当噪声超过关于比特数 n 的一个极小水平时,算法无法分解形如 pq 的整数,其中 p、q 取自某个正密度的素数集合。他进一步证明,对随机素数对 (p,q),以概率 1−o(1) 同样如此。
HN 上的人在讨论量子计算机能否真正破解密码时引用它,作为噪声会使 Shor 算法在大整数上失败、仅靠纠错无法拯救的论据;其结论也有人持保留态度。
学习路径
读这篇之前,按顺序读书架上的 3 篇 · 参考文献来自 OpenAlex,顺序和要点由 Claude Code 排出这条路径先读 Shor 算法本身,再看表面码为何是应对噪声的容错路线,以及 NISQ 对含噪设备能力的判断,从而理解噪声下 Shor 算法失效这一结论的意义。
- 1
目标论文分析的就是这篇提出的整数分解算法在噪声下的表现。
读量子傅里叶变换、周期寻找与经典后处理的整体流程;弄清其中的受控旋转门。
- 2
说明现实中靠量子纠错与容错来对付门噪声,对照目标论文的无纠错噪声设定。
读稳定子码、逻辑量子比特与容错阈值的基本概念,不必深入编织细节。
- 3
讨论没有纠错的含噪中等规模设备能做什么,是目标论文所处的现实背景。
读NISQ 的定义,以及为什么含噪设备难以运行深线路算法(如 Shor)。
- 4Shor's Algorithm Does Not Factor Large Integers in the Presence of Noise
目标论文:证明随机噪声超过极小水平后 Shor 算法无法分解 pq 形整数。
读噪声模型(受控旋转门的随机噪声)与主定理的陈述;抓住噪声阈值随比特数 n 缩小的结论。
HN 书评
推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及“then no amount of error correction will rescue Shor's - only zero error phase gates.”
“A recent result considers a generic error model and a subclass for particular kinds of prime numbers [1].”
“There's a specific view (as I understand it) that QFT's don't scale Shor's Algorithm Does Not Factor Large Integers in the Presence of Noise but some folks seem to dismiss this for reasons I just don't grok at all.”
“Pay attention to how the "control gates" (as in SV09) are invoked”