We present a trichotomy theorem for the quantum query complexity of regular languages. Every regular language has quantum query complexity $\Theta(1)$, $\tilde{\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 $\tilde{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.