  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.
