3 citations · 3 across the 3 of their papers we have counts for
1 paper · 1 filter
Scott Aaronson, Daniel Grier, Luke Schaeffer
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). Th…