HackerPapers

arXiv:quant-ph/9801041quant-ph

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

Daniel S. Abrams, Seth Lloyd

Abstract

If quantum states exhibit small nonlinearities during time evolution, then quantum computers can be used to solve NP-complete problems in polynomial time. We provide algorithms that solve NP-complete and #P oracle problems by exploiting nonlinear quantum logic gates. It is argued that virtually any deterministic nonlinear quantum theory will include such gates, and the method is explicitly demonstrated using the Weinberg model of nonlinear quantum mechanics.

arXiv comments
10 pages, no figures, submitted to Phys. Rev. Lett
Journal reference
Phys.Rev.Lett. 81 (1998) 3992-3995
DOI
doi:10.1103/PhysRevLett.81.3992
Subjects
quant-phQuantum Physics

On Hacker News

Linked by 5 identifiable commenters in 6 comments across 5 threads, from May 2010 to Jun 2026.

Comments linking this paper, per year.

Discussed in comments5 threads

  1. Semiclassical Gravity Efficiently Solves NP-Complete Problems 2 comments

    • Shor doesn't solve an NP hard problem. It's even possible that factoring and discrete log are in P, while P != NP. The paper builds on the results of "Nonlinear quantum mechanics implies polynomial-time solution for NP-complete and #P problems" by Abrams and Loyd [1], from which…

      trompView on HNParent context

    • Doh! You are correct. I had been looking at a previous paper (which this new paper references). The previous paper showed that you can use any non-linearity in QM to solve NP-complete problems, and the new one shows that semi-classical gravity + QM has such a non-linearity. The…

      SyzygyRhythmView on HNParent context

  2. You're not irrational, you're just quantum probabilistic 1 comment

    • Quantum mechanics does not permit parallel states to "communicate" in any way. The theory is purely linear (i.e. acts somewhat independently on all states), except for the wavefunction collapse phenomena. Any non-linenarity would, for instance, immediately imply that we can…

      foobar2020View on HNParent context

  3. A Deepness In The Sky 1 comment

    • If you change the underlying physics, computational power can change quite a bit. The best-known example of this is that quantum computers are widely believed to be more powerful than classical computers. An even more striking example, though less well known, is that certain…

      michael_nielsenView on HNParent context

  4. Ask HN: If P = NP, what does it mean? 1 comment

    • P = NP would touch almost every field known to man: maths (e.g. it would only be matter of search to take down the remaining Clay Problems), philosophy, engineering, biology, physics. The tie to physics is particularly interesting: for example if Quantum mechanics was a…

      Dn_AbView on HNParent context

  5. What’s taking so long, Mr. Babbage? 1 comment

    • If you work in quantum computing -- which I did, full time for 13 years, and part time for a few years prior to that -- it's VERY common to run into people outside the field who believe that quantum computers can solve NP-complete problems in polynomial time. Dozens of wrong…

      michael_nielsenView on HNParent context

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.