Lower Bounds on the Running Time of Two-Way Quantum Finite Automata and Sublogarithmic-Space Quantum Turing Machines
Lower Bounds on the Running Time of Two-Way Quantum Finite Automata and Sublogarithmic-Space Quantum Turing Machines
复制标题
DOI：
10.4230/lipics.itcs.2021.39
复制
发表时间：
2020-03
期刊：
影响因子：
--
通讯作者：
Zachary Remscrim
中科院分区：
文献类型：
--
作者：
Zachary Remscrim
Ambainis和Watous定义的量子经典态双向有限自动机(2QCFA)是量子计算的一种模型，它的量子部分极其有限；然而，正如他们所证明的那样，2QCFA具有惊人的能力：在长度为$n$的输入上，只有一个量子比特的2QCFA可以识别语言$L_{pal}=\{w\in\a，b\*^*：W\Text{是一个回文}$，期望时间$2^O(N)}$$。我们证明了他们的结果本质上是不可改进的：任意大小的2QCFA在预期时间$2^{o(N)}$内不能识别具有有界误差的$L_{pal}$。据我们所知，这是一种语言的第一个例子，它可以在指数时间内以有界误差被2QCFA识别，但在次指数时间内不能被识别。此外，我们还证明了运行在空间$o(\logn)$和期望时间$2^{n^{1-\omega(1)}}$上的量子图灵机不能识别具有有界误差的$L_{pal}$，这也是此类机器的第一个下界。更一般地，我们建立了一个关于任何2QCFA或$o(\logn)$空间QTM的运行时间的下界，该QTM识别任何语言$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-\Omega(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.