按年被提到
20232024 · 4 次2026
物理与量子›量子计算·arXiv:2306.10072 · quant-ph

Shor's Algorithm Does Not Factor Large Integers in the Presence of Noise

存在噪声时 Shor 算法无法分解大整数
Jin-Yi Cai · 2023

证明在随机噪声超过极小水平时 Shor 算法不能分解 pq

开始阅读 ↗PDFalphaXiv 讨论
被推荐 · 4 人首次 2024-04-13 · 最近 2025-07-15
4不同的人
4活跃月份
4讨论串
19被引(OpenAlex)

论文在含噪声量子门的设定下考察 Shor 量子分解算法。在(受控)旋转门的一般随机噪声模型下,他证明当噪声超过关于比特数 n 的一个极小水平时,算法无法分解形如 pq 的整数,其中 p、q 取自某个正密度的素数集合。他进一步证明,对随机素数对 (p,q),以概率 1−o(1) 同样如此。

HN 为什么提它

HN 上的人在讨论量子计算机能否真正破解密码时引用它,作为噪声会使 Shor 算法在大整数上失败、仅靠纠错无法拯救的论据;其结论也有人持保留态度。

奠基之作难度 5 / 5约 90 分钟经得起时间
读之前最好知道
1Shor 分解算法
2量子傅里叶变换(QFT)
3量子门噪声模型
4数论与素数分布

学习路径

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

这条路径先读 Shor 算法本身,再看表面码为何是应对噪声的容错路线,以及 NISQ 对含噪设备能力的判断,从而理解噪声下 Shor 算法失效这一结论的意义。

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

    目标论文分析的就是这篇提出的整数分解算法在噪声下的表现。

    读量子傅里叶变换、周期寻找与经典后处理的整体流程;弄清其中的受控旋转门。

  2. 2
    Surface codes: Towards practical large-scale quantum computation表面码:迈向实用的大规模量子计算 · 2012

    说明现实中靠量子纠错与容错来对付门噪声,对照目标论文的无纠错噪声设定。

    读稳定子码、逻辑量子比特与容错阈值的基本概念,不必深入编织细节。

  3. 3
    Quantum Computing in the NISQ era and beyondNISQ 时代及以后的量子计算 · 2018

    讨论没有纠错的含噪中等规模设备能做什么,是目标论文所处的现实背景。

    读NISQ 的定义,以及为什么含噪设备难以运行深线路算法(如 Shor)。

  4. 4
    Shor's Algorithm Does Not Factor Large Integers in the Presence of Noise存在噪声时 Shor 算法无法分解大整数 · 2023 · 就是这篇

    目标论文:证明随机噪声超过极小水平后 Shor 算法无法分解 pq 形整数。

    读噪声模型(受控旋转门的随机噪声)与主定理的陈述;抓住噪声阈值随比特数 n 缩小的结论。

HN 书评

推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及
推荐eigenket · 2024-04

“For the true version see here”

贴出论文作为“真实版本”:噪声下 Shor 算法分解不了大整数
Quantum Algorithms for Lattice Problems原评论 ↗
引用sgt101 · 2024-04

“then no amount of error correction will rescue Shor's - only zero error phase gates.”

引用它:存在噪声时,纠错也救不了 Shor 算法,只有零误差相位门可以
Quantum Algorithms for Lattice Problems原评论 ↗
引用JanisErdmanis · 2024-05

“A recent result considers a generic error model and a subclass for particular kinds of prime numbers [1].”

指出近期有结果考虑通用误差模型及特定素数子类
What You Shouldn't Know About Quantum Computers原评论 ↗
引用sgt101 · 2024-12

“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.”

引用一种观点:QFT 无法扩展,噪声使 Shor 算法无法分解大整数,但有人不予理会
The case against Google's claims of "quantum supremacy"原评论 ↗
引用gsf_emergency_2 · 2025-07

“Pay attention to how the "control gates" (as in SV09) are invoked”

提醒注意其中“控制门”的调用方式,涉及噪声下 Shor 算法的几何和分析
Conceptual synaesthesia as cognitive literacy原评论 ↗