按年被提到
19982010 · 2 次2026
物理与量子›量子计算·arXiv:quant-ph/9801041 · quant-ph

Nonlinear quantum mechanics implies polynomial-time solution for NP-complete and #P problems

非线性量子力学意味着可在多项式时间内求解 NP 完全与 #P 问题
Daniel S. Abrams, Seth Lloyd · 1998

若量子力学含微小非线性,量子计算机可多项式时间解 NP 完全问题

开始阅读 ↗PDFalphaXiv 讨论
被提及 · 5 人首次 2010-05-23 · 最近 2026-06-17
5不同的人
5活跃月份
5讨论串
247被引(OpenAlex)

论文指出,如果量子态在时间演化中存在微小非线性,量子计算机就能在多项式时间内解决 NP 完全问题。作者给出利用非线性量子逻辑门求解 NP 完全和 #P 预言问题的算法,论证几乎任何确定性的非线性量子理论都会包含这类门,并以 Weinberg 的非线性量子力学模型作了具体演示。

HN 为什么提它

HN 上的人常把它当作依据,说明若量子力学是非线性的就能物理地解 NP 完全问题,借此反推量子力学线性的意义。

奠基之作难度 4 / 5约 30 分钟经得起时间
读之前最好知道
1量子力学基础与线性演化
2计算复杂性(NP 完全、#P)
3量子计算与量子门
4Weinberg 非线性量子力学

HN 书评

推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及
引用michael_nielsen · 2010-05

“There are nonlinear variants on quantum mechanics in which all the problems in NP can be solved in polynomial time. See Nonlinear quantum mechanics implies polynomial-time solution for NP-complete and #P problems”

引用它说明存在非线性量子力学变体,可在多项式时间内解决所有 NP 问题
What’s taking so long, Mr. Babbage?原评论 ↗
引用Dn_Ab · 2010-08

“for example if Quantum mechanics was a nonlinear theory then we could physically solve NP complete problems [1].”

借它说明若量子力学是非线性的,就能在物理上求解 NP 完全问题
Ask HN: If P = NP, what does it mean?原评论 ↗
引用michael_nielsen · 2011-02

“This result was written up here: Nonlinear quantum mechanics implies polynomial-time solution for NP-complete and #P problems”

指出这个结果已被写成论文
A Deepness In The Sky原评论 ↗
引用foobar2020 · 2015-09

“immediately imply that we can easily solve NP-complete problems using quantum computing”

借它说明可以立刻推出用量子计算轻松求解 NP 完全问题
You're not irrational, you're just quantum probabilistic原评论 ↗
引用tromp · 2026-06

“The paper builds on the results of”

指出这篇论文建立在先前结果的基础上
Semiclassical Gravity Efficiently Solves NP-Complete Problems原评论 ↗
引用SyzygyRhythm · 2026-06

“The previous paper showed that you can use any non-linearity in QM to solve NP-complete problems”

指出先前论文表明量子力学的任何非线性都能用于求解 NP 完全问题
Semiclassical Gravity Efficiently Solves NP-Complete Problems原评论 ↗