The quantum query complexity of certification
Andris Ambainis, Andrew M. Childs, François Le Gall, Seiichiro Tani · Quantum Information and Computation · 2010
We study the quantum query complexity of finding a certificate for a d-regular, k-level balanced and formula. We show that the query complexity is $\tilde\Theta(d^{(k+1)/2})$ for 0-certificates, and $\tilde\Theta(d^{k/2})$ for 1-certificates. In particular, this shows that the zero-error quantum query complexity of evaluating such formulas is $\tilde O(d^{(k+1)/2})$. Our lower bound relies on the fact that the quantum adversary method obeys a direct sum theorem.