论文标题
双向量子有限自动机和sublogarithmic空间量子图灵机的运行时间的下限
Lower Bounds on the Running Time of Two-Way Quantum Finite Automata and Sublogarithmic-Space Quantum Turing Machines
论文作者
论文摘要
由Ambainis和Watrous定义的具有量子和经典状态（2QCFA）的双向有限自动机是一种量子计算的模型，其量子部分非常有限。但是，正如他们所表明的那样，2QCFA令人惊讶地强大：只有一个单位的2QCFA可以识别语言$ l_ {pal} = \ {w \ in \ {a，b \}^*：w \ text {是palindrome} \} $，带有预期的时间$ 2^^$ n of thime $ 2^{o（n是palindrome} \} $。 我们证明他们的结果基本上无法改善：2QCFA（任何大小）无法识别$ l_ {pal} $，而预期的时间为$ 2^{o（n）} $，而有界错误。据我们所知，这是一种语言的第一个示例，该语言可以在指数时间内由2QCFA识别，而不是在次指定时间中。此外，我们证明了在太空中运行的量子图灵机（QTM）$ O（\ log n）$和预期的时间$ 2^{n^{1-ω（1）}} $无法识别带有有限错误的$ l_ {pal} $;同样，这是同类的第一个下限。 更一般而言，我们在任何2QCFA或$ o（\ log n）$ - 空间QTM的运行时间内建立了一个下限，该QTM识别任何语言$ l $在$ l $的自然“硬度度量”方面。这使我们能够展示大型语言家族，在任何此类2QCFA或QTM识别器的运行时间内，我们都渐近地匹配上下界限。
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 only a single-qubit can recognize the language $L_{pal}=\{w \in \{a,b\}^*:w \text{ is a palindrome}\}$ with bounded error in expected time $2^{O(n)}$, on inputs of length $n$. We prove that their result essentially cannot be improved upon: a 2QCFA (of any size) cannot recognize $L_{pal}$ with bounded error in expected time $2^{o(n)}$. To our knowledge, this is the first example of a language that can be recognized with bounded error by a 2QCFA in exponential time but not in subexponential time. Moreover, we prove that a quantum Turing machine (QTM) running in space $o(\log n)$ and expected time $2^{n^{1-Ω(1)}}$ cannot recognize $L_{pal}$ with bounded error; again, this is the first lower bound of its kind. Far more generally, we establish a lower bound on the running time of any 2QCFA or $o(\log n)$-space QTM that recognizes any language $L$ in terms of a natural "hardness measure" of $L$. This allows us to exhibit a large family of languages for which we have asymptotically matching lower and upper bounds on the running time of any such 2QCFA or QTM recognizer.
