id: 05706134
dt: j
an: 05706134
au: Iriyama, Satoshi; Ohya, Masanori
ti: On generalized quantum Turing machine and its applications.
so: Open Syst. Inf. Dyn. 16, No. 2-3, 195-204 (2009).
py: 2009
pu: World Scientific, Singapore
la: EN
cc: 
ut: 
ci: 
li: doi:10.1142/S1230161209000141
ab: Summary: 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.
rv: