A Quantum Query Complexity Trichotomy for Regular Languages

摘要

We present a trichotomy theorem for the quantum query complexity of regular languages. Every regular language has quantum query complexity (1) , ( n ) , or ( 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 ( n c ) for all computable c [ 1 2 1 ] . Our result implies an equivalent trichotomy for the approximate degree of regular languages, and a dichotomy---either (1) or ( 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 ( 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.