NP in BQP with Nonlinearity

Abstract

If one modifies the laws of Quantum Mechanics to allow nonlinear evolution of quantum states, this paper shows that NP-complete problems would be efficiently solvable in polynomial time with bounded probability (NP in BQP). With that (admittedly very unlikely) assumption, this is demonstrated by describing a polynomially large network of quantum gates that solves the 3SAT problem with bounded probability in polynomial time. As in a previous paper by Abrams and Lloyd (but by a somewhat simpler argument), allowing nonlinearity in the laws of Quantum Mechanics would prove the "weak Church-Turing thesis" to be false. General Relativity is suggested as a possible mechanism to supply the necessary nonlinearity.

arXiv comment8 pages, no figures, several bugs fixed, added GR nonlinearity mechanism

References in corpus (13)

• Elementary gates for quantum computation
• Strengths and Weaknesses of Quantum Computing
• Quantum Algorithms Revisited
• Grover's quantum searching algorithm is optimal
• Nonlinear quantum mechanics implies polynomial-time solution for NP-complete and #P problems
• Experimental demonstration of quantum correlations over more than 10 km
• Quantum Computing: Pro and Con
• Computable functions, quantum measurements, and quantum dynamics
• The Church-Turing thesis as a guiding principle for physics
• Experimental limit on the blue shift of the frequency of light implied by a q-nonlinearity
• The lambda-q calculus can efficiently simulate quantum computers
• Quantum Computer Can Not Speed Up Iterated Applications of a Black Box
• Speedup in quantum computation is associated with attenuation of processing probability