算法与理论计算机2015arxiv.org
布尔可满足性的多项式时间有界误差量子算法
A Polynomial Time Bounded-Error Quantum Algorithm for Boolean Satisfiability
专业 · 约 40 分钟读完前置知识：量子计算基础、密度矩阵与量子纠缠、SAT 问题定义
导读
论文声称给出一个求解布尔可满足性（SAT）的多项式时间、有界误差量子算法；若成立，将直接意味着 NP 包含于 BQP，即量子计算机能高效解决 NP 完全问题。评论普遍认为其构造属于“并行计算所有可能输入再提取结果”的思路，并迅速指出论文中存在关键错误。
HN 关注点：如果成立将颠覆计算复杂性理论并让量子计算机高效求解 NP 完全问题，因此 HN 讨论迅速转向怀疑：评论者给出了具体公式漏洞，并质疑作者此前类似论文未获社区认可。
后来怎么样
论文声称的 NP⊆BQP 结论很快被指出存在关键错误，未获领域接受，也未产生后续方法学影响。
HN 评论精选
这几条评论里：质疑 3 补充 1
质疑基于作者此前类似论文未获关注和结果过于轻易，怀疑论文可信度。
[我是这个方向写硕士论文的学生] 我倾向于认为这是胡扯，依据是一个元理由：他们引用自己 2015 年 5 月的一篇论文，那篇已经用另一个 NP 完全问题声称证明 NP 包含于 BQP（和本文基本是同一个突破性结果），却不知为何完全没在社区引起反响。粗读本文没发现明显错误，但整体给人一种“太容易、太新奇、没有建立在任何公认部分结果之上”的感觉。这个问题被成百上千研究者攻过，他们恰好发现一个没人想到的怪招，实在不太可信。这些只是启发式判断，我很愿意自己错；但人生太短，没法对一篇可疑论文投入超过 15 分钟。我可以试着在量子模拟器里实现这个算法，但要做好很费时，还是让别人去证伪/确认吧。
algorias查看英文原文
[Note: I am a master student doing my thesis in this area] Ok, I'm going to go out on a limb here and call bullshit, based on the meta-reason that they cite a paper of theirs which already claims to show that NP is contained in BQP using a different NP-complete problem, published in may 2015 (which is basically the same groundbreaking result as this paper), but this somehow completely failed to make waves in the community. Additionally, on a superficial reading of the paper nothing seems wrong with it, except that it has this air of everything being too easy, too novel, not building on any widely recognized partial results. Considering this problem has been attacked by hundreds (?) of researchers over the years, it seems highly implausible that they just happened to find this one weird trick nobody had thought of before. Anyway, those are just heuristics, and I'd love to be wrong on this occasion, but life is too short to give my full attention to a dubious paper for more than 15 minutes. I could attempt to whip up this algorithm in a quantum simulator, but that would take a considerable amount of time to do right, so I'll let somebody else do the work of debunking/confirming the result.
质疑指出 Eq.16 忽略第一个寄存器是错的，因为两寄存器纠缠、|C(x)> 间无相干性，后续步骤依赖此性质。
Eq. 16。作为量子计算研究生，我们以前常玩一个游戏：比赛谁先看出一篇声称给出 NP 完全问题高效量子多项式算法的论文里的漏洞。我看了几分钟后押 Eq. 16。Eq. 15 用传统 clause oracle 计算子句：sum_x |x>|C(x)>，其中 C(x) 是输入 x 上各子句求值组成的向量。Eq. 16 声称可以忽略第一个寄存器，变成 sum_x |C(x)>。这不对：系统在两个寄存器间是纠缠的，其中一个系统的偏迹是混合态；特别地，|C(x)> 各态之间没有相干性。而下一步恰恰关键依赖这个性质。
da-bacon查看英文原文
Eq. 16. As a grad student in quantum computing we used to have a game where we would race to see who could be the first one to spot the flaw in a paper that claimed an efficient quantum polynomial time algorithm for NP-complete problems. My bet after a few minutes looking at the paper is Eq. 16. Eq. 15 is computing the clauses with a traditional clause oracle \sum_x |x>|C(x)> where C(x) is a vector of the clauses evaluated on the input x. Eq. 16 claims that one can ignore the first register and this becomes \sum_x |C(x)>. That's not correct: the system is entangled across those two registers, and the partial portion of one of those systems is a mixed state. In particular there is no coherence between the |C(x)> states. The next step relies crucially on this property.
质疑该构造属于被普遍怀疑的“量子并行枚举所有输入”，且加 dummy qubits 提升测量概率的做法可疑。
1. 给出的构造很简单，属于“并行计算所有可能输入的输出，然后提取正确或最优输入”这一类。2. 这正是人们常认为行不通的构造：即使在量子计算机上，也必须利用问题结构，不能直接把量子并行性扔上去。3. 他们 5 月已发表一篇论文，把同样技术用于图划分问题。4. 哪种情况为真？算法错了、关于量子计算机对 NP 难问题帮助不大的信念错了，还是有办法把算法翻译到经典计算机？最后一种会很棒，但前两种更可能。5. 有一点让我觉得奇怪：他们只是加几个 dummy qubits 来提升某次测量的概率。这种事也许可行，但至少违背我的直觉；这让我想起给 FFT 输入补零以获得更高频率分辨率，当然那不是真的。
danbruc查看英文原文
1. The presented construction is pretty simple and falls in the category of computing the output for all possible inputs in parallel and then extract the correct or best input. 2. This is exactly the type of construction that is often(?) believed not to work, i.e. even on a quantum computer you have to exploit the structure of the problem and can not just throw quantum parallelism at the problem. 3. They already published a paper in May [1] in which they applied the same techniques to graph partitioning problems. 4. Which option is true? The algorithm is wrong, the believe that quantum computers are of not much help for NP-hard problems was wrong, or there is a way to translate this algorithm to classical computers? The last one would be awesome but the first two seem much more likely. 5. There is one thing in the paper that struck me as a bit odd, namely that they just add a couple of dummy qubits to boost the probability of one measurement. It is certainly possible that something like that works but at least it runs counter to my intuition. It reminds me of zero-padding FFT inputs to get a result with higher frequency resolution which of course is not real. [1] http://arxiv.org/abs/1505.06284
补充用 Aaronson 的论证强调高效解 NP 问题近乎超能力，因此对论文极度怀疑并期待专家分析。
Scott Aaronson 的《Quantum Computing since Democritus》有个观点：如果你能快速求解 NP 问题，你基本就有超能力。别说什么 SAT 或旅行商，你立刻能做快速自动定理证明器之类。取决于怎么解决，你不会是在 arXiv 上读到 P=NP，而是读到某人靠股市赚了几十亿。Aaronson 形容这大概和超光速通信一样不可信。如果这篇论文是真的，那量子计算机看起来就是实现它的手段。我很怀疑。那些科幻故事里随手一挥用量子计算机获得无限算力、模拟宇宙或同时黑掉所有电脑，都是对当前量子算法能力的可笑误解（即使不管造机器的技术细节）。好吧，如果这篇论文站得住，那可能就离真相近多了！（免责声明：我不是专家。我很希望很快看到 Aaronson 的分析。）
tgb查看英文原文
One of the points of Scott Aaronson's excellent "Quantum Computing since Democritus" is that if you can quickly solve NP problems, you basically have super powers. Forget about SAT or Travelling Salesman, you can now do fast automated theorem provers and the like. Depending on how it were solved, you wouldn't read about P=NP on arxiv, you'd read about someone making billions on the stock market. Aaronson describes it as being comparably implausible to having faster than light communication. If this paper is true, then it looks to me like quantum computers would be a means of doing that. I'm skeptical. Know those sci-fi stories where they hand-wave a quantum computer to have infinite computing power? Then they simulate the universe or hack all the computers simultaneously or whatever. That's all a laughable misinterpretation of what current state-of-the-art quantum algorithms can do (even if we remove the technical details of constructing the machine). Well, if this paper holds up, then that's a whole lot closer to the truth, maybe! (Disclaimer: not an expert. I really hope to see Aaronson's analysis of this soon.)
相关资源
从这篇论文所有 HN 讨论帖的全部评论里整理出来的链接。
- 评论区提到的论文
历次讨论
- 2015Hacker News 讨论帖148 分 · 125 评
同领域还值得读
哲学家为何应关注计算复杂性
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 分钟编辑精选