THE QUANTUM QUERY COMPLEXITY OF CERTIFICATION
We study the quantum query complexity of finding a certificate for a d-regular, k-level balanced NANDformula. We show that the query complexity is circle minus(d((k+1)/2)) for 0-certificates, and (circle minus) over tilde (d(k/2)) for 1-certificates. In particular, this shows that the zero-error quantum query complexity of evaluating such formulas is (O) over tilde (d((k+1)/2)). Our lower bound relies on the fact that the quantum adversary method obeys a direct sum theorem.
quantum query complexity certificates formula evaluation