New quantum algorithm for studying NP-complete problems

Abstract

Ordinary approach to quantum algorithm is based on quantum Turing machine or quantum circuits. It is known that this approach is not powerful enough to solve NP-complete problems. In this paper we study a new approach to quantum algorithm which is a combination of the ordinary quantum algorithm with a chaotic dynamical system. We consider the satisfiability problem as an example of NP-complete problems and argue that the problem, in principle, can be solved in polynomial time by using our new quantum algorithm.

11 pages, 1 figure

Cited by in corpus (2)

• Subspace projection method for unstructured searches with noisy quantum oracles using a signal-based quantum emulation device
• Quantum Algorithm for SAT Problem and Quantum Mutual Entropy