NP in BQP with Nonlinearity
| dc.creator | Gossett, Phil | |
| dc.date | 1998-04-09 | |
| dc.date | 1998-04-27 | |
| dc.date.accessioned | 2026-07-07T06:14:56Z | |
| dc.date.available | 2026-07-07T06:14:56Z | |
| dc.description | 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. | |
| dc.description | 8 pages, no figures, several bugs fixed, added GR nonlinearity mechanism | |
| dc.identifier | https://arxiv.org/abs/quant-ph/9804025 | |
| dc.identifier | http://arxiv.org/abs/quant-ph/9804025 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/93650 | |
| dc.subject | Quantum Physics | |
| dc.title | NP in BQP with Nonlinearity | |
| dc.type | text |