Title: A Quantum Query Complexity Trichotomy for Regular Languages
| Speaker: | Luke Schaeffer |
| Affiliation: | University of Waterloo |
| Room: | MC 5501 |
Abstract:
We consider the quantum query complexity of regular languages and discover a surprising trichotomy: each regular language has query complexity either Theta(1), ~Theta(sqrt(n)) or Theta(n). Briefly, the query complexity of an algorithm is the number of bits of input it needs to read. In this setting, one can prove unconditional lower bounds for problems which in some cases (especially for quantum algorithms) coincide with the upper bounds. For example, Grover's algorithm searches a list of n items with only O(sqrt(n)) quantum queries, and a query complexity argument proves this is optimal.
The regular languages are defined by regular expressions or, equivalently, recognized by finite automata. We show that each regular language is either easy (Theta(1) queries), medium (~Theta(sqrt(n)) queries, or hard (Theta(n) queries), and characterize the regular languages of each type. Interestingly, the ~Theta(sqrt(n)) languages correspond (modulo technical details) to the well-studied "star-free languages", which we use to interpret those languages as generalizations of Grover's algorithm. We provide examples where this perspective yields new quantum query algorithms.
(This is based on joint work with Scott Aaronson and Daniel Grier)