2
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ Wouldn't it be BQP=NP? However, we still do not believe that this is the case ... $\endgroup$ Commented Apr 17 at 15:33
  • 1
    $\begingroup$ @MarkusHeinrich even still BQP=NP is a mathematical question; BQP has a perfectly formal mathematical definition absent any nonlinear gates. $\endgroup$ Commented Apr 17 at 15:39
  • $\begingroup$ @MarkusHeinrich: You are probably right as the problem should be solved on quantum computer rather than on classical one. $\endgroup$ Commented Apr 17 at 16:38

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Thanks for the answer. Just one additional question. So, if we assume that Church-Turing thesis is true then non-linear QM computer should be kind of hypercomputing concept. However, hypercomputers are considered to be unphysical, hence also non-linear QM, right? $\endgroup$ Commented Apr 17 at 16:35
  • 1
    $\begingroup$ The sentiment is correct but the language used is probably broader than I would use. I think hypercomputation as is commonly used goes beyond even what's Turing-computable. I don't think that Abrams and Lloyd showed that nonlinear quantum mechanics affords something that strong. But yes, it's fair to conclude that a reasonable way to interpret Abrams and Lloyd's result is that nonlinear quantum mechanics is unphysical - stronger than a nondeterministic machine but not so strong enough to solve the Halting problem. $\endgroup$ Commented Apr 17 at 17:06
  • $\begingroup$ Yes, you are right. It is about speed up, not expanding the universe of computable problems. I see my mistake now. So, non-linear quantum computer is still Turing machine but faster than anything else. However also unphysical. $\endgroup$ Commented Apr 17 at 17:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.