New quantum algorithm for studying NP-complete problems

Masanori Ohya, Igor Vasil'evich Volovich

Published Jan 1, 2003• 37 citations

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. keywords: Quantum Algorithm, NP-complete problem, Chaotic Dynamics 1

Related papers

A New Quantum Algorithm for NP-complete Problems

Makoto Ohya, Masanori Ohya, Igor V. Volovich

Jan 1, 20021 citation

Quantum Computing, NP-complete Problems and Chaotic Dynamics

Masanori Ohya, Igor Vasil'evich Volovich

An approach to the solution of NP-complete problems based on quantum computing and chaotic dynamics is proposed. We consider the satisfiability problem and argue that the problem, in principle, can be solved in polynomial time if we combine the quantum computer with the chaotic dynamics amplifier based on the logistic map. We discuss a possible implementation of such a chaotic quantum computation by using the atomic quantum computer with quantum gates described by the Hartree-Fock equations. In this case, in principle, one can build not only standard linear quantum gates but also nonlinear gates and moreover they obey to Fermi statistics. This new type of entaglement related with Fermi statistics can be interesting also for quantum communication theory.

arXiv:quant-ph/9912100Dec 21, 199916 citations

Novel method to solve Hamilton loop problem

Jun Meng

Hamilton loop problem belongs to NP-complete problems.This paper proposed an approach to it based on quantum computation and chaotic dynamics.Firstly,using a Boolean polynomial analyzed the Hamilton loop problem.Secondly,constructed a novel model based on quantum computation and chaotic dynamics which using a chaotic dynamics amplifier amplified the initial value in polynomial time.Considered the Hamilton loop problem and argued that the problem,in principle,it could be solved in polynomial time if the quantum computer was combined with the chaotic dynamics amplifier based on the logistic map.

Jisuanji yingyong yanjiuJan 1, 20080 citations

Quantum computing and the chaotic amplifier

Masanori Ohya, Igor Vasil'evich Volovich

A new model for computations is considered which combines the quantum computer with the chaotic dynamics amplifier, based on the logistic map. We discuss the satisfiability problem and argue that the problem can, in principle, be solved in polynomial time if one uses the new model for computations.

Journal of Optics B Quantum and Semiclassical OpticsOct 16, 200323 citations

Generalized quantum Turing machine and its use to find an algorithm solving NP-Complete problem

Satoshi Iriyama, Masanori Ohya

Ohya and Volovich found the quantum algorithm with a chaos dynamics, called the OV SAT algorithm which enabled to solve NP-Complete problem in polynomial time. It is proved that the unitary operator of the quantum algorithm can be constructed by a product of so called fundamental gates. To discuss the computational complexity rigorously, we introduced a generalized quantum Turing machine(GQTM) where the computational process is given by quantum channels including a dispative dynamics and the configuration is represented by density operators. In this paper, we explain the GQTM and the OV SAT algorithm, then we discuss the computational complexity of OV SAT algorithm. Finally, we introduce some resent results and topics by use of GQTM.

International Symposium on Applied Sciences in Biomedical and Communication TechnologiesNov 1, 20101 citation

Generalized Quantum Turing Machine and Its Use to Find an Algorithm Solving NP-Complete Problem (Invited Paper)

Satoshi Iriyama, Masanori Ohya

Ohya and Volovich found the quantum algorithm with a chaos dynamics, called the OV SAT algorithm which enabled to solve NP-Complete problem in polynomial time. It is proved that the unitary operator of the quantum algorithm can be constructed by a product of so called fundamental gates. To discuss the computational complexity rigorously, we intro- duced a generalized quantum Turing machine(GQTM) where the computational process is given by quantum channels including a dispative dynamics and the configuration is represented by density operators. In this paper, we explain the GQTM and the OV SAT algorithm, then we discuss the computational complexity of OV SAT algorithm. Finally, we introduce some resent results and topics by use of GQTM.

Jan 1, 20100 citations