Back to Search
Start Over
On Generalized Quantum Turing Machine and Its Applications.
- Source :
- Open Systems & Information Dynamics (OSID); Sep2009, Vol. 16 Issue 2/3, p195-204, 10p
- Publication Year :
- 2009
-
Abstract
- 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. [ABSTRACT FROM AUTHOR]
- Subjects :
- ALGORITHMS
POLYNOMIALS
COMPUTABLE functions
MATHEMATICS
COMPUTATIONAL complexity
Subjects
Details
- Language :
- English
- ISSN :
- 12301612
- Volume :
- 16
- Issue :
- 2/3
- Database :
- Supplemental Index
- Journal :
- Open Systems & Information Dynamics (OSID)
- Publication Type :
- Academic Journal
- Accession number :
- 80205782
- Full Text :
- https://doi.org/10.1142/S1230161209000141