标题： 量子有限自动机识别的具有无界误差的语言 显示英文标题

标题： Languages recognized with unbounded error by quantum finite automata

摘要： 我们证明了在无界错误设置下Kondacs-Watrous量子有限自动机的语言识别能力的以下事实：这种类型的单向自动机能够识别所有且仅能识别随机语言。当允许磁带头双向（甚至“1.5向”）移动时，能够识别的语言更多。这导致了结论，当限制为常数空间边界时，量子图灵机比概率图灵机更强大。 显示英文摘要

摘要： We prove the following facts about the language recognition power of Kondacs-Watrous quantum finite automata in the unbounded error setting: One-way automata of this kind recognize all and only the stochastic languages. When the tape head is allowed two-way (or even "1.5-way") movement, more languages become recognizable. This leads to the conclusion that quantum Turing machines are more powerful than probabilistic Turing machines when restricted to constant space bounds.