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

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 earlier paper: https://arxiv.org/pdf/quant-ph/9801041

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 I quote: > The last qubit now contains all the information that we need; however, for small s, a measurement of the last qubit will almost always return |0>, yielding no information. > We wish to distinguish between the cases s=0 and s>0. > Step 4. Repeatedly apply the nonlinear operation to drive the states representing these two cases apart at an exponential rate: eventually, at a time determined by a polynomial function of the number of qubits n, the number of solutions s, and the rate of spreading (Lyapunov exponent) λ, the two cases will become macroscopically distinguishable. [1] https://arxiv.org/abs/quant-ph/9801041

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 easily solve NP-complete problems using quantum computing: http://arxiv.org/abs/quant-ph/9801041 So QM is probably a poor model for explaining human indecisiveness and irrationality. Much better is that it is simply the thing that evolution has come up with that can a) fit in our brains and b) yields proper results.

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 nonlinear theory then we could physically solve NP complete problems [1]. Note the implication, this is not to say p = np => QM nonlinear. The utopian consequences of p = np are discussed very engagingly by Scott Aaronson here [2]. I suggest you also check out his blog as well - his writing style is clear and fun. Plus there was a recent discussion there that linked complexity theory to foundational physics. [1] http://arxiv.org/abs/quant-ph/9801041 [2] http://www.scottaaronson.com/papers/npcomplete.pdf

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 papers have been written claiming just that, and the claim also appears frequently (often implicitly) in popular journalism. The blog's subtitle is just acknowledgment of that fact. Incidentally, P and NP certainly do have to do with the hardware. There are nonlinear variants on quantum mechanics in which all the problems in NP can be solved in polynomial time. See http://arxiv.org/abs/quant-ph/9801041 These variants are, however, unlikely to describe the way the world works.