标题： 量子查询复杂性的正则语言三重性 显示英文标题

标题： A Quantum Query Complexity Trichotomy for Regular Languages

摘要： 我们提出了一个关于正则语言量子查询复杂性的三重定理。 每个正则语言的量子查询复杂度为 Theta(1)、~Theta(sqrt n) 或 Theta(n)。 正则语言的极端一致性使其无法具有其他渐近复杂度。 这与甚至上下文无关语言形成对比，我们证明它们可以具有查询复杂度 Theta(n^c)，其中 c 是 [1/2,1] 中的所有可计算值。 我们的结果意味着正则语言的近似度存在等效的三重定理，并且对于敏感度、块敏感度、证书复杂度、确定性查询复杂度和随机查询复杂度，存在二重定理——要么是 Theta(1)，要么是 Theta(n)。 分类定理的核心是一个显式的量子算法，该算法可以在 ~O(sqrt n) 时间内决定任何无星语言的成员资格。 这一被广泛研究的正则语言家族有许多有趣的特性，例如，作为可以在自然数的小于关系上用一阶逻辑表达的句子的语言。 因此，不仅无星语言可以表示如 OR 这样的函数，还可以表示如“存在一对 2，使得它们之间的所有内容都是 0”这样的函数。 因此，我们将无星语言的算法视为对 Grover 算法的非平凡推广，它将量子二次加速扩展到比以前已知更广泛的字符串处理算法范围。 我们展示了各种应用——针对动态常数深度布尔公式的新的量子算法、平衡括号嵌套常数层深、二进制加法、受限的单词拆分问题以及窄网格中的路径发现——所有这些都是我们分类定理的直接结果。 显示英文摘要

摘要： We present a trichotomy theorem for the quantum query complexity of regular languages. Every regular language has quantum query complexity Theta(1), ~Theta(sqrt n), or Theta(n). The extreme uniformity of regular languages prevents them from taking any other asymptotic complexity. This is in contrast to even the context-free languages, which we show can have query complexity Theta(n^c) for all computable c in [1/2,1]. Our result implies an equivalent trichotomy for the approximate degree of regular languages, and a dichotomy---either Theta(1) or Theta(n)---for sensitivity, block sensitivity, certificate complexity, deterministic query complexity, and randomized query complexity. The heart of the classification theorem is an explicit quantum algorithm which decides membership in any star-free language in ~O(sqrt n) time. This well-studied family of the regular languages admits many interesting characterizations, for instance, as those languages expressible as sentences in first-order logic over the natural numbers with the less-than relation. Therefore, not only do the star-free languages capture functions such as OR, they can also express functions such as "there exist a pair of 2's such that everything between them is a 0." Thus, we view the algorithm for star-free languages as a nontrivial generalization of Grover's algorithm which extends the quantum quadratic speedup to a much wider range of string-processing algorithms than was previously known. We show a variety of applications---new quantum algorithms for dynamic constant-depth Boolean formulas, balanced parentheses nested constantly many levels deep, binary addition, a restricted word break problem, and path-discovery in narrow grids---all obtained as immediate consequences of our classification theorem.