算法与理论计算机2018arxiv.org
面向初学者的量子算法实现
Quantum Algorithm Implementations for Beginners
进阶 · 约 180 分钟读完前置知识：线性代数、量子计算基础、Python 编程
导读
这是一篇面向初学者的量子算法教程/综述，系统讲解若干经典量子算法（如 Deutsch–Jozsa、Bernstein–Vazirani、Grover、Shor 等）的原理，并给出在 IBM 量子云平台和模拟器上的具体实现代码。论文的目标读者是刚入门、想动手跑通这些算法的人。
HN 关注点：HN 读者既认可它作为入门动手资料的价值，也集中批评它把“人人需要学量子编程”当作前提的叙事，以及书稿内部符号不统一、概念跳步的问题。
HN 评论精选
这几条评论里：支持 1 质疑 3
质疑质疑论文“需要大规模培养量子程序员”的前提，认为量子计算机只会是少数专用场景的昂贵设备。
开篇那句话说“随着量子计算机向公众开放，需要培养一批量子程序员”，我觉得这和现实脱节。它似乎在兜售一种观念：几年内量子计算机会取代普通计算机，这我完全不信。量子计算机能否做出任何有用的事都还是未决问题；即便可行，很长时间内它也会是昂贵设备，跑在复杂的物理实验装置里，只服务于非常特殊的需求。就我们所知，量子计算机并不是万能更快的机器，只在少数很特殊的算法上有优势。这当然很有意思，但即便可行（这是个大前提），也不会有人很快把它塞进我们的手机，因为根本没必要。如果量子计算机真来了，我们需要的是少数熟悉其算法的专业程序员，而不是一大批。
hannob查看英文原文
The way this starts seems to tell a story that I feel is quite disconnected from reality: > As quantum computers have become available to the general public, the need has arisen to train a cohort of quantum programmers It seems to peddle the idea that in a few years we'll replace all normal computers with quantum computers. I don't think this is even remotely plausible. It's still an open question whether quantum computers that do anything useful at all are feasible. But even if they are - we can safely assume that for a long time they will be expensive devices, running in complex physical experiments, that will be reserved for very special needs. From all we know QCs aren't magically faster computers that are suitable to do everything better. There are just a few very special algorithms where QCs have an advantage. That's certainly interesting, but even if it would be possible - and that's a big if - it's unlikely anyone will add them to our smartphones anytime soon, simply because there's no need for that. If quantum computers arrive we'll need a handful of specialized programmers that are familiar with their algorithms. But not masses of them.
支持肯定其入门价值，并补充推荐 NIST 的量子算法动物园（Quantum Algorithm Zoo）作为延伸资料。
这篇论文很好地体现了自量子信息科学诞生以来量子算法研究进展有多大。想进一步了解量子算法的人还可以看这份综述 [0]。从摘要看，这正是我当初入门量子计算时希望拥有的资料。[0]: https://math.nist.gov/quantum/zoo/
vtomole查看英文原文
This paper is a good example of how much progress we've had in quantum algorithm research since the dawn Quantum information science. Here is another good survey for people who want to learn more about quantum algorithms [0]. From the abstract, it seems like a resource I wish I had when I was starting to get into quantum computation. [0]: https://math.nist.gov/quantum/zoo/
质疑数学背景读者反馈：bra-ket 记号前后不一致、部分公式与定义矛盾、关键概念缺少解释。
我喜欢这个想法，但得承认（我数学出身，对量子物理和物理学家的记号几乎一无所知）读起来相当吃力。尤其是 bra-ket 记号（它破坏了括号匹配的直觉，这一点可能只是需要时间适应），在全文里用得并不一致——我猜不同算法是不同作者写的，差异明显且没有帮助。有些公式我完全看不懂，最近一个例子：Shor 算法里 QFT 的定义中，ket 里的 k 从 0 取到 N-1，但按引言它应该在若干量子比特的所有组合上取值。另外，有些作者把某些概念（比如量子门的性质）当作理所当然，别处从未解释，对我也并不显然。不过这仍是有趣的读物。
giomasce查看英文原文
I like the idea, but I must admit that (with my background of a mathematics researcher, but almost completely ignorant of quantum physics and quantum physicists' notations) it is rather difficult to understand. In particular the bra-ket notation (which to me is already difficult due to its breaking the obvious way to match parentheses, but this might just require some time) seems to be used inconsistently across the paper (I believe that different authors wrote about the different algorithms, and the variations are rather evident and unhelpful). There are some formulas of which I cannot make any sense (last example I found: in the definition of QFT inside Shor's algorithm, the k inside the ket ranges from 0 to N-1, while according to the introduction it should range on all the combinations of a certain number of qubits). Also, some authors seem to take for granted some concepts (such as the properties of the quantum gates) that are not explained anywhere and not obvious to me. Still, an interesting read.
质疑提出经典—量子混合编程/接口问题，认为现有入门材料普遍回避这一层。
我开始读一些量子计算的资料，也在 IBM 的量子计算体验平台上试过，但卡在这里：门和电路层面的基础我能跟上——现有的很多材料本质上是量子汇编语言之类的东西。可经典计算与量子计算如何对接？是把整个程序从头到尾跑在量子计算机上，还是取经典系统的输出作为量子系统的输入？我最感兴趣的量子计算应用似乎都需要与经典计算机交互，至少会引出这个问题，而这类文章通常不谈，仿佛默认你就在机器码/汇编层面编程。
neuxenian查看英文原文
I've started reading some quantum computing texts, and dabbled a bit with IBM's quantum computing experience, and this is where I get stuck: I can follow the basics at the level of "gates" or circuits -- a lot of what's out there is essentially quantum assembly language or something of that sort. But what about interfacing classical and quantum computing? Is the idea that you just run something from start to finish on a quantum computer? Or that you take the output from a classical system and input into a quantum system? Some of the things I'd be most interested in with a quantum computer seem to require an interface with a classical computer, or at least raise the issue, which generally isn't addressed by these sorts of pieces. It's sort of assumed that you're programming whatever it is you're interested in at the level of machine/assembly code.
相关资源
从这篇论文所有 HN 讨论帖的全部评论里整理出来的链接。
- 评论区提到的论文
历次讨论
- 2018Hacker News 讨论帖191 分 · 20 评
同领域还值得读
哲学家为何应关注计算复杂性
Why Philosophers Should Care About Computational Complexity (2011)
Scott Aaronson 的这篇长文论证计算复杂性理论（如 P vs NP、停机问题的复杂度视角）对哲学问题（如知识的本质、中文房间、水槽论证等）具有实质意义，而不仅是技术细…
算法与理论计算机2015 · 552 分 · 120 评进阶 · 约 90 分钟编辑精选通信的数学理论
A Mathematical Theory of Communication
是香农1948年的《通信的数学理论》，为通信建立数学框架：把信息量定义为不确定性或自由度（信息熵），并讨论信源编码、信道容量与可靠传输。
算法与理论计算机2020 · 495 分 · 91 评进阶 · 约 120 分钟编辑精选物理、拓扑、逻辑与计算：罗塞塔石碑
Physics, Topology, Logic and Computation: A Rosetta Stone (2009)
用范畴论充当“罗塞塔石碑”，试图在量子物理、拓扑、逻辑与计算四个领域之间建立统一的结构性类比：物理中的量子过程、拓扑中的配边、逻辑中的证明和计算中的程序，都可被视为某类范畴中的态…
算法与理论计算机2009 · 390 分 · 55 评 · 引用 13专业 · 约 180 分钟编辑精选一种快速、极小内存的一致性哈希算法
A Fast, Minimal Memory, Consistent Hash Algorithm
论文给出一种快速、省内存的一致哈希方案，目标是在桶数量变化时保持较小的键迁移成本，同时降低计算和内存开销。
算法与理论计算机2014 · 327 分 · 57 评 · 引用 4进阶 · 约 25 分钟编辑精选第五个 Busy Beaver 值的确定
Determination of the fifth Busy Beaver value
宣布确定了第五个 Busy Beaver 值 BB(5)：即 5 状态图灵机中停机前运行步数最多的机器（Champion）在 47,176,870 步后停机。
算法与理论计算机2025 · 288 分 · 116 评 · 引用 1专业 · 约 75 分钟编辑精选