“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”
按年被提到
19982010 · 2 次2026
Nonlinear quantum mechanics implies polynomial-time solution for NP-complete and #P problems
非线性量子力学意味着可在多项式时间内求解 NP 完全与 #P 问题
Daniel S. Abrams, Seth Lloyd · 1998
若量子力学含微小非线性,量子计算机可多项式时间解 NP 完全问题
被提及 · 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
引用它说明存在非线性量子力学变体,可在多项式时间内解决所有 NP 问题
引用Dn_Ab · 2010-08
“for example if Quantum mechanics was a nonlinear theory then we could physically solve NP complete problems [1].”
借它说明若量子力学是非线性的,就能在物理上求解 NP 完全问题
引用michael_nielsen · 2011-02
“This result was written up here: Nonlinear quantum mechanics implies polynomial-time solution for NP-complete and #P problems”
指出这个结果已被写成论文
引用foobar2020 · 2015-09
“immediately imply that we can easily solve NP-complete problems using quantum computing”
借它说明可以立刻推出用量子计算轻松求解 NP 完全问题
引用tromp · 2026-06
“The paper builds on the results of”
指出这篇论文建立在先前结果的基础上
引用SyzygyRhythm · 2026-06
“The previous paper showed that you can use any non-linearity in QM to solve NP-complete problems”
指出先前论文表明量子力学的任何非线性都能用于求解 NP 完全问题