The Quantum Query Complexity of AC0

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 $\mathrm{\Theta }(n)$ queries to $f$. The same lower bound holds for determining whether or not a function $f$ from $[2n-2]$ to $[n]$ is surjective. These results yield a nearly linear $\mathrm{\Omega }(n\mathrm{/}\log n)$ lower bound on the quantum query complexity of $\text{cl}{AC}^0$. The best previous lower bound known for any $\text{cl}A{C}^0$ function was the $\mathrm{\Omega }((n\mathrm{/}\log n{)}^{2\mathrm{/}3})$ bound given by Aaronson and Shi’s $\mathrm{\Omega }(n^{2\mathrm{/}3})$ lower bound for the element distinctness problem.