A Quantum Query Complexity Trichotomy for Regular Languages.

Scott Aaronson, Daniel Grier, Luke Schaeffer

Browse the full FOCS paper archive.