New quantum algorithm for studying NP-complete problems (Q1422459): Difference between revisions

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.