Nonlinear Quantum Mechanics Implies Polynomial-Time Solution forNP-Complete and #PProblems

1998/01/21 by Daniel S. Abrams, Seth Lloyd · 16 citations
Computer Science · Physics and Astronomy · #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum-Dot Cellular Automata #quant-ph

paper · pdf · doi:10.1103/physrevlett.81.3992

published as Phys.Rev.Lett. 81 (1998) 3992-3995 · 10 pages, no figures, submitted to Phys. Rev. Lett

arxiv created 1998/01/21 · openalex publication_date 1998/11/02 · arxiv updated 2009/12/01 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/28

Abstract

If quantum states exhibit small nonlinearities during time evolution, then quantum computers can be used to solve NP-complete and # P problems in polynomial time. We provide algorithms that solve 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.

Citations

• Test of the linearity of quantum mechanics by rf spectroscopy of theBe+<mml:mprescripts/>9ground state
• Testing quantum mechanics
• Simulating physics with computers

Cited by

• Informal Resource Letter - Nonlinear quantum mechanics on arXiv up to August 2004
• Linear assignment maps for correlated system-environment states
• Quantum computing, postselection, and probabilistic polynomial-time
• Guest Column: NP-complete problems and physical reality
• The Nature of Computation
• LocalPTSymmetry Violates the No-Signaling Principle
• Nonlinear Quantum Mechanics at the Planck Scale
• Optimization by a quantum reinforcement algorithm
• Limits on Efficient Computation in the Physical World
• The nonlinear directional coupler: an analytic solution
• On the role of entanglement in quantum-computational speed-up
• Testing foundations of quantum mechanics with photons
• Space-Bounded Church-Turing Thesis and Computational Tractability of Closed Systems
• Quantum search with interacting Bose-Einstein condensates
• Neural Networks Architecture Evaluation in a Quantum Computer
• Darboux integration of