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

标题： 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 applications to problems such as evaluating dynamic constant-depth Boolean formulas and recognizing balanced parentheses nested constantly many levels deep.