Nonlinear Quantum Mechanics Implies Polynomial-Time Solution for<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline"><mml:mi mathvariant="italic">NP</mml:mi></mml:math>-Complete and #<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline"><mml:mi mathvariant="italic">P</mml:mi></mml:math>Problems

Abstract

If quantum states exhibit small nonlinearities during time evolution, then quantum computers can be used to solve $\mathrm{NP}$-complete and # $P$ problems in polynomial time. We provide algorithms that solve $\mathrm{NP}$-complete and # $P$ oracle problems by exploiting nonlinear quantum logic gates. Using the Weinberg model as a simple example, the explicit construction of these gates is derived from the underlying physics. Nonlinear quantum algorithms are also presented using Polchinski type nonlinearities which do not allow for superluminal communication.