The Quantum Query Complexity of AC0

Paul Beame, Widad Machmouchi

We show that any quantum algorithm deciding whether an input function $f$ from $[n]$ to $[n]$ is 2-to-1 or almost 2-to-1 requires $\Theta (n)$ queries to $f$. The same lower bound holds…