Nonlinear quantum mechanics implies polynomial-time solution for NP-complete and #P problems

Preprint

21 January 1998

preprint
Published by arXiv in arXiv

https://doi.org/10.48550/arXiv.quant-ph/9801041

Abstract

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.

Keywords

NONLINEAR QUANTUM MECHANICS
IMPLIES POLYNOMIAL
QUANTUM MECHANICS
MECHANICS IMPLIES
POLYNOMIAL TIME
NP COMPLETE
EVOLUTION
SOLVE NP

All Related Versions

Version 1, 1998-01-21, ArXiv
Published version: Physical Review Letters, 81 (18), 3992.

This publication has 0 references indexed in Scilit: