00937nas a2200145 4500008004100000245005000041210004600091260001500137520051500152100002100667700002300688700002300711700002000734856003700754 2009 eng d00aThe quantum query complexity of certification0 aquantum query complexity of certification c2009/03/063 a We study the quantum query complexity of finding a certificate for a
d-regular, k-level balanced NAND formula. Up to logarithmic factors, we show
that the query complexity is Theta(d^{(k+1)/2}) for 0-certificates, and
Theta(d^{k/2}) for 1-certificates. In particular, this shows that the
zero-error quantum query complexity of evaluating such formulas is
O(d^{(k+1)/2}) (again neglecting a logarithmic factor). Our lower bound relies
on the fact that the quantum adversary method obeys a direct sum theorem.
1 aAmbainis, Andris1 aChilds, Andrew, M.1 aLe Gall, François1 aTani, Seiichiro uhttp://arxiv.org/abs/0903.1291v2