算法与理论计算机2016arxiv.org
为什么现在正是研究量子计算的最佳时机（2014）
Why now is the best time to study quantum computing (2014)
进阶 · 约 25 分钟读完前置知识：量子计算基本概念、线性代数、计算复杂度基础
导读
这是一篇 2014 年的论述性文章，讨论为何当下（当时）是进入量子计算研究领域的最佳时机——通常从实验进展（小规模量子处理器、超导与离子阱路线）、理论工具（量子纠错、算法）成熟以及资金与人才流入等角度展开。标题即观点，具体论证细节需以原文为准。
HN 关注点：的焦点不在论文本身，而在量子计算会以何种形式进入程序员日常（协处理器/API）、它对现有密码学的威胁，以及入门学习资料的匮乏。
HN 评论精选
这几条评论里：补充 4
补充量子计算将像 GPU 一样被抽象成协处理器和 API，多数程序员无需懂物理细节。
虽然我学过量子计算的基础，但我不认为计算机科学家有必要了解量子计算机那些骇人的物理细节。他们只需要知道，某个原本是 O(n²) 的函数现在有了 O(n) 的神奇实现，另一个原本指数的函数现在变成了多项式。量子计算机很可能以协处理器的形式出现，你可以在传统语言中通过一个封装良好的 API 调用这些实现，比如：#!/usr/bin/env python4 / from quantum import qc / qc.init(device="/dev/quantum0") / factors = qc.factor(15)
dheera查看英文原文
Although I have studied the basics of quantum computing, I don't think it will become necessary for computer scientists to know the gory physics details of quantum computers. All they will need to know is that a certain function that is normally O(n^2) now has a magical implementation that is O(n), and another function that is normally exponential is now polynomial. Quantum computers will likely manifest themselves as co-processors, and you'll have a nice well-abstracted API to access those implementations within traditional languages, i.e. #!/usr/bin/env python4 from quantum import qc qc.init(device="/dev/quantum0") factors = qc.factor(15)
补充提供了一份从零讲起、含双比特处理器与 Grover 搜索实操的入门演讲视频。
我在 31C3 上做过一个关于实验量子计算的入门演讲，讲解一个基本的双量子比特处理器如何工作，以及如何在其上运行一个非常简单的量子算法（Grover 搜索）。视频链接：https://youtu.be/1PcseLsYZ9Y
ThePhysicist查看英文原文
I gave an introductory talk about experimental quantum computing at the 31C3 where I explain how a basic two-qubit quantum processor works and how we can run a very simple quantum algorithm (Grover search) on it, here's the video link: https://youtu.be/1PcseLsYZ9Y
补充一旦出现大规模量子计算机，现有公钥基础设施将被攻破，应尽早投入后量子防御。
如果我还是学生，我一定会投身量子计算。这个领域非常酷，创新机会极多。我常想，当「0-day 量子机器」出现——不再是几个量子比特，而是真正可用的机器——会发生什么。我认为任何掌握这种技术的人都能破解任何 SSL 证书，从而访问网上几乎一切东西。我怀疑犯罪组织是不是已经在暗中投资这类东西？而且，也许我有点偏执，但既然我们几乎确定它造得出来，提前投资防御手段难道不明智吗？我们能用什么安全机制对抗量子计算？难道只有用量子计算才能防御量子计算？
d0m查看英文原文
If I was still a student, I would definitely go in quantum computing. So much opportunities for innovation on a very cool subject. I often wonder what will happen at the 0-day quantum machine where it's not just a few qbit but the real deal.. I think anyone in possession of such technology will be able to crack any SSL certificate, and thus gain access to almost anything online. I wonder if criminal organisations aren't secretly investing in such thing? And, not to be paranoid, but we're almost certain it will be possible to build them, wouldn't it be prudent to start investing in the defense against such things? What kind of security could we have to counter a quantum computing? Would it only be possible to use quantum computing to defend against quantum computing?
补充希望找到像数学教材那样定义—定理—证明结构的量子计算入门材料。
有没有那种「定义—定理—证明—练习」反复循环、专门用作领域入门的精简论文？也许类似 http://www.jiblm.org/downloads/jiblmjournal/V090212I/V090212I.pdf 这种风格。
Qaw查看英文原文
Are there slim definition-theorem-proof-exercise-repeat style papers meant to be an introduction into the field? Maybe something in the style of http://www.jiblm.org/downloads/jiblmjournal/V090212I/V090212I.pdf
相关资源
从这篇论文所有 HN 讨论帖的全部评论里整理出来的链接。
- 视频与演讲
历次讨论
- 2016Hacker News 讨论帖195 分 · 78 评
同领域还值得读
哲学家为何应关注计算复杂性
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 分钟编辑精选