按年被提到
20132013 · 1 次2026
物理与量子›量子计算·arXiv:1301.7007 · quant-ph

Pretending to factor large numbers on a quantum computer

在量子计算机上“假装”分解大数
John A. Smolin, Graeme Smith, Alex Vargo · 2013

编译版 Shor 算法只用两个量子比特就能“分解”大数

开始阅读 ↗PDFalphaXiv 讨论
被提及 · 4 人首次 2013-04-07 · 最近 2026-01-08
4不同的人
6活跃月份
6讨论串
125被引(OpenAlex)

论文展示如何用编译版 Shor 算法分解大素数之积:对任意两个大于 2 的不同素数 p、q 的乘积都适用,运行时间为常数,只需两个相干量子比特。作者以此说明,实现 Shor 算法的难度的正确度量不是被分解数的大小,而是所求周期的长度。

HN 为什么提它

评论者反复引用它,说明为什么一些实验室“分解 15 之类小数”的量子演示不可信:这类电路往往事先知道因子才能构造出来。

其他难度 3 / 5约 20 分钟经得起时间
读之前最好知道
1Shor 算法
2量子比特与量子线路(quantum circuit)基础
3整数分解与周期查找(period finding)
4初等数论

学习路径

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

这条路径先读 Shor 算法本身,再看几次小规模的实验实现,最后理解为什么编译版只需很少量子比特就能假装分解大数。

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

    Shor 算法的原始论文,本文的编译版正是它的简化。

    读分解转化为求阶(周期寻找)的思路,以及量子傅里叶变换在其中的作用。

  2. 2

    首次用 NMR 实验实现 Shor 算法分解 15,是本文批评的那类演示的代表。

    读实验如何选取要分解的数与基,以及电路规模。

  3. 3

    用量子比特回收减少所需量子比特数,是在资源上做精简的类似思路。

    读qubit recycling 的做法与能分解的数的规模。

  4. 4

    用约瑟夫森相位量子比特处理器完成分解,是另一类实验实现。

    读实验所用的器件与门序列,以及分解的数。

  5. 5
    Pretending to factor large numbers on a quantum computer在量子计算机上“假装”分解大数 · 2013 · 就是这篇

    目标论文:用编译版 Shor 算法只用两个量子比特即可分解特定大数。

    读编译为何依赖于已知阶,以及据此说明小规模演示的难度并不在于数的大小。

HN 书评

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

“See, for instance, my esteemed colleagues on why some labs' claims to have factored small numbers like 15 are bogus:”

引用同事的论文,说明部分实验室分解 15 之类小数的说法是假的
Lockheed Martin pays $10M for D-Wave's Quantum Computer原评论 ↗
引用jessriedel · 2017-12

“Second, see this”

让人看这篇,了解小数量子分解演示为何有误导性
Design of a silicon quantum computer chip原评论 ↗
引用acqq · 2019-09

“For those who are interested in the papers about this topic:”

列出相关论文,称编译版 Shor 演示事先知道答案,并非真分解
IBM will soon launch a 53-qubit quantum computer原评论 ↗
引用Strilanc · 2021-05

“In [1] it's shown that, if you know the factors behind a factoring problem of any size, you can derive constant sized quantum circuits that "solve it".”

指出知道因子后,可构造常数大小的量子电路来“解”分解问题
Quantum Computer Datasheet [pdf]原评论 ↗
引用iamawacko · 2024-01

“It's not that hard to pretend to factor large numbers on a quantum computer [2].”

引用论文说明在量子计算机上“假装”分解大数并不难
Ask HN: What has quantum computing achieved so far?原评论 ↗
引用Strilanc · 2026-01

“Also, footnote a of that paper points out (correctly) that the circuits that were used likely needed knowledge of the factors to create (e.g. as explained in Pretending to factor large numbers on a quantum computer ).”

指出论文脚注说得对,所用电路很可能需要事先知道因子
2026 Predictions Scorecard原评论 ↗