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

International Symposium on Applied Sciences in Biomedical and Communication Technologies

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

Satoshi Iriyama, Masanori Ohya

Published Nov 1, 2010• 1 citation
Publisher

Abstract

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.

DOI
10.1109/isabel.2010.5702873

Related papers

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, 2010•0 citations

On Generalized Quantum Turing Machine and Its Applications

Satoshi Iriyama, Masanori Ohya

Ohya and Volovich discussed a quantum algorithm for the SAT problem with a chaos amplification process (OMV SAT algorithm) and showed that the number of steps it performed was polynomial in input size. In this paper, we define a generalized quantum Turing machine (GQTM) and related computational complexity. Then we show that there exists a GQTM which recognizes the SAT problem in polynomial time. Moreover, we discuss the problem of finding the quantum algorithm for a partial recursive function.

Open Systems & Information Dynamics•Aug 13, 2009•0 citations

GENERALIZED QUANTUM TURING MACHINE AND ITS APPLICATION TO THE SAT CHAOS ALGORITHM

Satoshi Iriyama, Masanori Ohya, Igor Vasil'evich Volovich

Ohya and Volovich have proposed a new quantum computation model with chaotic amplification to solve the SAT problem, which went beyond usual quantum algorithm. In this paper, we generalize quantum Turing machine, and we show in this general quantum Turing machine (GQTM) that we can treat the Ohya-Volovich (OV) SAT algorithm.

arXiv:quant-ph/0405191•Mar 1, 2006•22 citations

On generalized quantum turing machine and its language classes

Satoshi Iriyama, Masanori Ohya

Abstract: Ohya and Volovich have proposed a new quantum computation model with chaotic amplification to solve the SAT problem, which went beyond usual quantum algorithm. In this paper, we generalize quantum Turing machine by rewriting usual quantum Turing machine in terms of channel transformation. Moreover, we define some computational classes of generalized quantum Turing machine and show that we can treat the Ohya-Volovich (OV) SAT algorithm.

International Conference on Applied Mathematics•Mar 22, 2007•4 citations

Language Classes Defined by Generalized Quantum Turing Machine

Satoshi Iriyama, Masanori Ohya

Ohya and Volovich proposed a quantum algorithm with chaotic amplification to solve the SAT problem, which went beyond the notion of the usual quantum algorithm. In this paper, we generalize quantum Turing machines by rewriting the usual quantum Turing automaton in terms of a channel transformation. Moreover, we define some computational classes of generalized quantum Turing machines and show that we can describe the Ohya-Volovich (OV) SAT algorithm with completely positive channels.

Open Systems & Information Dynamics•Dec 1, 2008•14 citations

Efficient Quantum Algorithm for NPC and EXPTIME Problems

Satoshi Iriyama, M. Ohya, Andrei Yu. Khrennikov +3 more

We have studied a quantum algorithm for several years, and developed some applications for difficult problems, NPC problems and NP intermidiate problems. In order to discuss the computational complexity of quantum algorithm, we defined a generalized quantum Turing machine using a density operator on a Hilbert space and quantum channels on it. Since the properity of quantum channel, this mathematical model can describe not only unitary process of quantum algorithm but also measurement process and non‐linear dynamical process. Then we can calculate the computational complexity of quantum algorithm more regorously.In this paper, we review our results, and discuss why quantum algorithms are more effective than classical ones. Moreover, we propose a quantum algorotihm for EXPTIME problem.

AIP conference proceedings•Jan 1, 2011•0 citations
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.
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.
We have studied a quantum algorithm for several years, and developed some applications for difficult problems, NPC problems and NP intermidiate problems. In order to discuss the computational complexity of quantum algorithm, we defined a generalized quantum Turing machine using a density operator on a Hilbert space and quantum channels on it. Since the properity of quantum channel, this mathematical model can describe not only unitary process of quantum algorithm but also measurement process and non‐linear dynamical process. Then we can calculate the computational complexity of quantum algorithm more regorously.In this paper, we review our results, and discuss why quantum algorithms are more effective than classical ones. Moreover, we propose a quantum algorotihm for EXPTIME problem.