  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.
