Non-linear quantum mechanics and NP-complete problems

Question

Thanks to user Cuhrazatee (comments to my other question here) I came accross article Nonlinear quantum mechanics implies polynomial-time solution for NP-complete and #P problems by D. Abrams and S. Lloyd.

In the article, it is stated that:

The implications of nonlinear quantum mechanics on the theory of computation are profound. In particular, we show that it is generally possible to exploit nonlinear time evolution so that the classes of problems NP and #P (including oracle problems) may be solved in polynomial time.

This means that if quantum mechanics were non-linear then it would hold that $P = NP$. Authors of the article therefore say:

In concluding, we would like to note that we believe that quantum mechanics is in all likelihood exactly linear, and that the above conclusions might be viewed most profitably as further evidence that this is indeed the case.

However, I would not say that we know that $P \ne NP$ for sure as this is still unproven conjecture. Of course, it maybe that $P=NP$ and quantum mechanics to be linear at the same time. As quantum mechanics is probably the most thoroughly tested physical theory, it seems that it is linear and the article is just thought experiment similar to ones investigating what would happen if physical constants had different value or space-time metrics are altered.

Despite this, I would like to ask if above mentioned speculation has been investigated further. Any reference would be highly appreciated.

---

EDIT: Here is a related question on construction of non-linear OR gate described in the paper above.

Answer 1

Be careful - the P vs. NP problem (or even the BQP vs. NP problem) is a mathematical problem about platonic Turing machines, detached from this real world. The Abrams and Lloyd paper is an interesting observation about the physical world that we live in. Abrams and Lloyd do not posit that if QM is nonlinear then P=NP or BQP=NP; it's more subtle and they prove that if QM is nonlinear and if scalable nonlinear fault-tolerant quantum computers (FTQCs) could be built then NP problems could be solved on such a nonlinear quantum computer in polynomial time.

Many people actually turn Abrams and Lloyd on its head, and say that their result gives credence to the linearity of quantum mechanics. That is, people take primacy on the Quantum Extended Church-Turing Thesis (which posits that quantum mechanics is the end-of-the-road for computational power in this universe), and use this maxim to conclude that, because Abrams and Lloyd's hypothetical nonlinear quantum computers are in conflict with the Quantum Extended Church-Turing Thesis, then quantum mechanics must be linear. I also have had a lot of fun revisiting all of the ink Aaronson has spilled on NP problems in the physical world.

Regarding research directions, I do think Steven Weinberg actively investigated what nonlinear quantum mechanics would look like. But Abrams and Lloyd state that even small nonlinear corrections could be amplified to solve NP problems in polynomial time. Thus if we take primacy of the Quantum Extended Church-Turing Thesis then we can conclude that Weinberg's proposals are doomed to fail.

In one of Deutch's original papers (here for PDF), he asked how to program a quantum computer to actually test for the linearity of quantum mechanics - this is perhaps a fun problem to consider (but it's probably a research-level program to decide what's the best way to prove nonlinearity of QM, as hinted at by @AbdullaKhalid when I asked a similar question here).

The Travelling Salesperson Problem may not be in P but nonetheless quantum mechanics could be nonlinear and we could solve TSP efficiently in this world; factoring may not be in P but nonetheless FTQC's could be built and we could factor large numbers efficiently in this world. Many people think the former is not probable while the latter is likely true.