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

被引：139

作者：

Abrams, DS ^{[1
]}

Lloyd, S

机构：

[1] MIT, Dept Phys, Cambridge, MA 02139 USA

[2] Arbeloff Lab Informat Sci & Technol, Dept Engn Mech, Cambridge, MA 02139 USA

来源：

PHYSICAL REVIEW LETTERS | 1998年 / 81卷 / 18期

关键词：

D O I：

10.1103/PhysRevLett.81.3992

中图分类号：

O4 [物理学];

学科分类号：

0702 ;

摘要：

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. [S0031 -9007(98)07489-4].

引用

页码：3992 / 3995

页数：4

共 20 条

[1] Simulations of many-body Fermi systems on a universal quantum computer [J].