New quantum algorithm for studying NP-complete problems (Q1422459)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | New quantum algorithm for studying NP-complete problems |
scientific article |
Statements
New quantum algorithm for studying NP-complete problems (English)
0 references
15 February 2004
0 references
It is known that the quantum computer based on quantum Turing machine or quantum circuits is not powerful enough to solve NP complete problems. It is known that it is possible to speed up NP problem solution quadratically but not exponentially. The problem is that measurements of two quantum states distinguish them with exponentially small probability if their inner product is close to 1. In this paper it is proposed to use an output of quantum computer as an input for another device instead of measurement which will overwhelmingly likely to fail. This device uses chaotic dynamic to amplify the distinguishability of the quantum states. Authors describe the quantum chaos algorithm which in combining with ordinary quantum algorithm can be powerful enough to solve the NP-complete problems in a polynomial time.
0 references
quantum computer
0 references
NP-problem
0 references