Quantum vs. Classical Pushdown Automata in Exact Computation

Yumiko Murakami (0251121)

Since some quantum algorithms were introduced by Shor or by Grover, much attention has been given to the field of quantum computation. The quantum computation is so useful for solving certain problems, however, the classical computation is more powerful in some cases. Thus, it is significant to compare the ability of quantum computation with the ability of classical counterpart, based on simple computation models, like automata. In this paper, we focus on the quantum pushdown automata, QPAs, which was defined by Golovkins in 2000. It is shown that the class of languages recognized by QPAs contains the class of languages recognized by finite automata. However, no one knows the relationships between the cognitive ablity of QPAs and the classical counterparts. We make a proposition in this paper, the QPAs that deterministically solve a certain problem, which cannot be solved by deterministic pushdown automata.