“See, for instance, my esteemed colleagues on why some labs' claims to have factored small numbers like 15 are bogus:”
Pretending to factor large numbers on a quantum computer
编译版 Shor 算法只用两个量子比特就能“分解”大数
论文展示如何用编译版 Shor 算法分解大素数之积:对任意两个大于 2 的不同素数 p、q 的乘积都适用,运行时间为常数,只需两个相干量子比特。作者以此说明,实现 Shor 算法的难度的正确度量不是被分解数的大小,而是所求周期的长度。
评论者反复引用它,说明为什么一些实验室“分解 15 之类小数”的量子演示不可信:这类电路往往事先知道因子才能构造出来。
学习路径
读这篇之前,按顺序读书架上的 4 篇 · 参考文献来自 OpenAlex,顺序和要点由 Claude Code 排出这条路径先读 Shor 算法本身,再看几次小规模的实验实现,最后理解为什么编译版只需很少量子比特就能假装分解大数。
- 1
Shor 算法的原始论文,本文的编译版正是它的简化。
读分解转化为求阶(周期寻找)的思路,以及量子傅里叶变换在其中的作用。
- 2
首次用 NMR 实验实现 Shor 算法分解 15,是本文批评的那类演示的代表。
读实验如何选取要分解的数与基,以及电路规模。
- 3
用量子比特回收减少所需量子比特数,是在资源上做精简的类似思路。
读qubit recycling 的做法与能分解的数的规模。
- 4
用约瑟夫森相位量子比特处理器完成分解,是另一类实验实现。
读实验所用的器件与门序列,以及分解的数。
- 5Pretending to factor large numbers on a quantum computer
目标论文:用编译版 Shor 算法只用两个量子比特即可分解特定大数。
读编译为何依赖于已知阶,以及据此说明小规模演示的难度并不在于数的大小。
HN 书评
推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及“Second, see this”
“For those who are interested in the papers about this topic:”
“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".”
“It's not that hard to pretend to factor large numbers on a quantum computer [2].”
“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 ).”