Quantum algorithm for EXPTIME problem and Computational Complexity (量子科学における双対性とスケール)
スポンサーリンク
概要
- 論文の詳細を見る
We have studied a computational complexity of quantum algorithm for several years. A mathematical model of quantum algorithm, which is called a generalized quantum Turing machine(GQTM), is introduced by Ohya et al., and we discussed the relation-ships of language classes denned by it. In this paper, we construct a quantum algorithm for the Pebble Game problem, which belongs to the class EXPTIME(i.e., it requires an exponential size of resources to solve), and discuss the computational complexity of it.
- 2012-02-20
著者
-
Ohya M.
Department Of Information Sciences Tokyo University Of Science
-
Iriyama S.
Department of Information Sciences, Tokyo University of Science
-
Iriyama S.
Department Of Information Sciences Tokyo University Of Science