On the power of quantum pushdown automata with a classical stack and 1.5-way quantum finite automata
Masaki Nakanishi, Takao Indoh, Kiyoharu Hamaguchi, Toshinobu Kashiwabara · NAIST Digital Library (Nara Institute of Science and Technology) · 2001
One of important questions on quantum computing is whether there is a computational gap between the models that is allowed to use quantum effects and the models that is not. Several types of quantum computational models have been proposed, including quantum - finite automata, quantum pushdown automata and quantum branching programs, and it has been shown that some computational models are more powerful than classical counterparts and some are not since quantum computational models are required to obey some restrictions such as reversible state transitions. In this paper, we introduce quantum pushdown automata whose stack is implemented as a classical device. We show that our quantum push-down automaton model can recognize some non-context-free languages with arbitrarily large acceptance probability and every deterministic context-free language with zero error. We also show that 1.5-way quantum nite automata can recognize the non-context-free language with probability less than 2/3.