arXiv:quant-ph/0312074

Estimation of Complexity for the Ohya-Masuda-Volovich SAT Algorithm

Shigeo Akashi, Satoshi Iriyama

Published Dec 9, 2003• 1 citation

Abstract

Ohya and Volovich have been proposed a new quantum computation model with chaos amplification to solve the SAT problem, which went beyond usual quantum algorithm. In this paper we study the complexity of the SAT algorithm by counting the steps of computation algorithm rigorously, which was mentioned in the paper [1,2,3,5,7]For this purpose, we refine the quantum gates treating the SAT problem step by step.

DOI: 10.48550/arxiv.quant-ph/0312074

Related papers

Rigorous Estimation of Computational Complexity for OMV SAT Algorithm

Satoshi Iriyama, Masanori Ohya

For SAT problem, which is known to be NP-complete, Ohya and Masuda found a quantum algorithm calculating a given boolean function for all truth assignments. They showed that we can decide whether this boolean function is satisfiable or not in polynomial time if a certain superposed state can be detected physically, which turns out to be related to an amplification process. Then Ohya and Volovich realized this amplification by means of chaos dynamics [4, 5]. In this paper, we study the complexity of the SAT algorithm by rigorously counting the steps of OMV algorithm discussed previously in [1, 2, 4, 5].

Open Systems & Information DynamicsJun 1, 200812 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/0405191Mar 1, 200622 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 MathematicsMar 22, 20074 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 DynamicsAug 13, 20090 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