算法与理论计算机2017arxiv.org
无需物理的量子计算导论
An Introduction to Quantum Computing, Without the Physics
进阶 · 约 90 分钟读完前置知识：线性代数、复数与向量空间基础、基本算法复杂度概念
导读
这篇 arXiv 论文是一篇不依赖物理背景的量子计算入门教程，用线性代数和数学方法介绍量子计算的基本概念与算法（如 Grover 算法）。评论者认为其内容严谨扎实，并推荐了配套的量子电路模拟器供读者动手实验。
HN 关注点：HN 读者长期关注量子计算科普，讨论焦点是这类入门材料的可读性，以及澄清大众对量子计算'并行尝试所有组合'的误解。
HN 评论精选
这几条评论里：支持 1 补充 2
补充澄清误解：量子计算不是万能并行，多数任务可能没有量子加速，但密码学除外
我收获最大的量子计算文章是 Scott Aaronson 的这篇，用非常直观的例子讲解 Shor 算法如何做因数分解，只需基础算术。最大的收获是：量子计算并非流行读物说的'同时尝试所有组合'。要让量子计算在某个任务上优于传统计算，你得碰巧找到它擅长的算法。从那篇文章看，大多数任务可能根本没有量子加速方案，所以量子计算或许改变不了太多——除了密码学，那可能改变一切。
daxfohl查看英文原文
The article on QC I got the most out of: http://www.scottaaronson.com/blog/?p=208 Very visual example of how Shor's algorithm works to solve factoring. Nothing more than basic arithmetic required. The big takeaway for me was, it's not just "try every combination at once" as per pop lit on the subject. QC doesn't really do that. To get QC to work any better that traditional for any task, you need to get lucky and stumble across an algorithm that QC can excel at for that task. Just from reading Scott Aaronson's article, it seems likely that most tasks simply don't have a QC optimization, so perhaps QC won't change much at all. (Well, except cryptography, which may change everything...)
补充推荐两个可动手实践的量子电路模拟器
如果想动手试论文里的例子，推荐两个模拟器：1) IBM Quantum Experience，点 'experiment' 开始，有不错的教程；2) algassert.com/quirk，我更喜欢这个，因为可以随时查看机器内部状态，选项更多也更快。
s-macke查看英文原文
Consider these two simulators, if you want to try the examples in the paper: 1. https://www.research.ibm.com/ibm-q/ This is IBM Quantum experience. Click on "experiment" to start. It has a nice tutorial. 2. http://algassert.com/quirk I like this one much better, because you can see the internal state of the machine at any moment. And it has much more options and is much faster.
支持评价论文质量不错但偏数学，并指出一处小瑕疵
快速浏览后觉得写得不错，偏数学严谨，对某些人可能不太理想。但很难避开数学：量子计算就是线性代数的化身。唯一觉得不对的地方很次要：他们说 Grover 算法用的多控制 Z 门可以用 O(n²) 个常数大小门实现，但按那种论证方式，不如直接给出紧界 Θ(n)。
Strilanc查看英文原文
After quickly skimming it it seems well done. Leans towards mathematical rigor, which may not be ideal for some people. On the other hand, it'd be pretty hard to avoid math: quantum computing is linear algebra incarnate. The only thing that caught my eye as off was totally minor. They say the many-controlled-Z gate used by Grover's algorithm can be done in O(n^2) constant-sized gates with an argument-by-reference, but with that type of argument you might as well give the tight bound of Θ(n).
相关资源
从这篇论文所有 HN 讨论帖的全部评论里整理出来的链接。
历次讨论
- 2017Hacker News 讨论帖149 分 · 18 评
同领域还值得读
哲学家为何应关注计算复杂性
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 分钟编辑精选