Expressive Power of Quantum Pushdown Automata with Classical Stack Operations under the Perfect-Soundness Condition
-
- NAKANISHI Masaki
- Graduate School of Information Science, Nara Institute of Science and Technology
-
- HAMAGUCHI Kiyoharu
- Graduate School of Information Science and Technology, Osaka University
-
- KASHIWABARA Toshinobu
- Graduate School of Information Science and Technology, Osaka University
Search this article
Abstract
One important question for quantum computing is whether a computational gap exists between models that are allowed to use quantum effects and models that are not. Several types of quantum computation models have been proposed, including quantum finite automata and quantum pushdown automata (with a quantum pushdown stack). It has been shown that some quantum computation models are more powerful than their classical counterparts and others are not since quantum computation models are required to obey such restrictions as reversible state transitions. In this paper, we investigate the power of quantum pushdown automata whose stacks are assumed to be implemented as classical devices, and show that they are strictly more powerful than their classical counterparts under the perfect-soundness condition, where perfect-soundness means that an automaton never accepts a word that is not in the language. That is, we show that our model can simulate any probabilistic pushdown automata and also show that there is a non-context-free language which quantum pushdown automata with classical stack operations can recognize with perfect soundness.
Journal
-
- IEICE Trans. Inf. & Syst., D
-
IEICE Trans. Inf. & Syst., D 89 (3), 1120-1127, 2006-03-01
The Institute of Electronics, Information and Communication Engineers
- Tweet
Details 詳細情報について
-
- CRID
- 1572824501795450368
-
- NII Article ID
- 110004719389
-
- NII Book ID
- AA10826272
-
- ISSN
- 09168532
-
- Text Lang
- en
-
- Data Source
-
- CiNii Articles