activity
20112021
most citedExponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits

37 citations · 39 across the 6 of their papers we have counts for

collaborators
Showing 2018Show all

1 paper · 1 filter

quant-ph2018

A Quantum Query Complexity Trichotomy for Regular Languages

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…