论文标题
单个量子的功能：双向量子有限自动机和单词问题
The Power of a Single Qubit: Two-way Quantum Finite Automata and the Word Problem
论文作者
论文摘要
由Ambainis和Watrous定义的具有量子和经典状态（2QCFA）的双向有限自动机是一种量子计算的模型，其量子部分非常有限。但是，正如他们所显示的，2QCFA令人惊讶地强大：一个带有单个量子的2qcfa可以通过有限的错误识别语言$ l_ {eq} = \ {a^m b^m：m \ in \ in \ in \ mathbb {n} \ {a，b \}^*：w \ text {是预期的指数时间中的palindrome} \} $。 我们通过证明他们可以识别许多群体的问题来进一步证明2QCFA的力量。尤其是2QCFA，具有单个值和代数数转换幅度，可以通过有限的误差识别任何有限生成的在预期多项式时间中几乎有限生成的Abelian组的单词问题，以及在预期的指数时间内的大量线性群体的单词问题。后一类（正确）包括所有具有无上下文单词问题的组。我们还展示了2QCFA的结果，并具有恒定数量的量子位。 作为推论，我们通过证明$ l_ {eq} $可以通过具有更好参数的2QCFA识别$ l_ {eq} $来直接改进原始的Ambainis和Watrous结果。作为进一步的推论，我们表明2QCFA可以在预期的多项式时间内识别某些非文化语言。 在同伴论文中，我们证明了匹配的下限，从而表明，在预期的$ \ mathit {subpentential} $ time中，由2QCFA识别的语言类别可识别为有限的错误，将其正确包含在语言类中，这些语言中的语言中的一系列语言中，可以通过预期的$ \ mathient $ \ mathient {oparential} $ \ mathient {operainential} $ \ aperient。
The two-way finite automaton with quantum and classical states (2QCFA), defined by Ambainis and Watrous, is a model of quantum computation whose quantum part is extremely limited; however, as they showed, 2QCFA are surprisingly powerful: a 2QCFA, with a single qubit, can recognize, with bounded error, the language $L_{eq}=\{a^m b^m :m \in \mathbb{N}\}$ in expected polynomial time and the language $L_{pal}=\{w \in \{a,b\}^*:w \text{ is a palindrome}\}$ in expected exponential time. We further demonstrate the power of 2QCFA by showing that they can recognize the word problems of many groups. In particular 2QCFA, with a single qubit and algebraic number transition amplitudes, can recognize, with bounded error, the word problem of any finitely generated virtually abelian group in expected polynomial time, as well as the word problems of a large class of linear groups in expected exponential time. This latter class (properly) includes all groups with context-free word problem. We also exhibit results for 2QCFA with any constant number of qubits. As a corollary, we obtain a direct improvement on the original Ambainis and Watrous result by showing that $L_{eq}$ can be recognized by a 2QCFA with better parameters. As a further corollary, we show that 2QCFA can recognize certain non-context-free languages in expected polynomial time. In a companion paper, we prove matching lower bounds, thereby showing that the class of languages recognizable with bounded error by a 2QCFA in expected $\mathit{subexponential}$ time is properly contained in the class of languages recognizable with bounded error by a 2QCFA in expected $\mathit{exponential}$ time.
