Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

A New Quantum Algorithm for NP-complete Problems

Makoto Ohya, Masanori Ohya, Igor V. Volovich

Published Sep 1, 2002• 1 citation
OpenAlex

Abstract

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.

Related papers

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/9912100•Dec 21, 1999•20 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 Optics•Oct 16, 2003•23 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 yanjiu•Jan 1, 2008•0 citations

NEW QUANTUM ALGORITHM FOR STUDYING NP-COMPLETE PROBLEMS

Masanori Ohya, Igor Vasil'evich Volovich

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.

WORLD SCIENTIFIC eBooks•Feb 1, 2008•1 citation

New quantum algorithm for studying NP-complete problems

Masanori Ohya, Igor Vasil'evich Volovich

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

•Jan 1, 2003•38 citations

A COMBINED QUANTUM ALGORITHM AND ITS COMPUTATIONAL COMPLEXITY

Satoshi Iriyama

A quantum algorithm for the general search problem is proposed by Ohya et al . in 2015. An NP-hard problem can be solved in polynomial steps with high probability by the quantum algorithm which implicates multiple quantum computation. Each quantum algorithm amplifies the success probability using the special dynamics, so called the Chaos amplifier, which is defined by the logistic map. In 2017, we showed that the Chaos amplifier and more general amplification process can be represented by the GKSL master equation in a two-qubit system. In this study, we explain our notion of combined quantum algorithm, and discuss on its computational complexity for the difficult problem.

Infinite Dimensional Analysis Quantum Probability and Related Topics•Nov 1, 2023•0 citations
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.
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.
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.
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
A quantum algorithm for the general search problem is proposed by Ohya et al . in 2015. An NP-hard problem can be solved in polynomial steps with high probability by the quantum algorithm which implicates multiple quantum computation. Each quantum algorithm amplifies the success probability using the special dynamics, so called the Chaos amplifier, which is defined by the logistic map. In 2017, we showed that the Chaos amplifier and more general amplification process can be represented by the GKSL master equation in a two-qubit system. In this study, we explain our notion of combined quantum algorithm, and discuss on its computational complexity for the difficult problem.