Quantum versus Classical Pushdown Automata in Exact Computation
Quantum versus Classical Pushdown Automata in Exact Computation
复制标题
DOI：
10.2197/ipsjdc.1.426
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
Y. Murakami;M. Nakanishi;S. Yamashita;Katsumasa Watanabe
中科院分区：
文献类型：
--
作者：
Y. Murakami;M. Nakanishi;S. Yamashita;Katsumasa Watanabe
尽管量子计算对于解决某些问题很有用，但在某些情况下，经典计算更强大。因此，基于自动机这样一个简单的计算模型来比较量子计算和经典计算的能力是很有意义的。Golovkins在2000年定义了量子下推自动机，证明了量子下推自动机所识别的语言类包含有限自动机所识别的语言类。然而，没有人知道量子下推自动机和经典下推自动机的可解性之间的全部关系。作为一个部分，我们证明了一个命题，量子下推自动机可以确定性地解决某些问题，不能解决任何确定性下推自动机。
Even though quantum computation is useful for solving certain problems, classical computation is more powerful in some cases. Thus, it is significant to compare the abilities of quantum computation and its classical counterpart, based on such a simple computation model as automata. In this paper we focus on the quantum pushdown automata which were defined by Golovkins in 2000, who showed that the class of languages recognized by quantum pushdown automata properly contains the class of languages recognized by finite automata. However, no one knows the entire relationship between the recognitive abilities of quantum and classical pushdown automata. As a part, we show a proposition that quantum pushdown automata can deterministically solve a certain problem that cannot be solved by any deterministic pushdown automata.