TY - JOUR
T1 - The quantum query complexity of certification
Y1 - 2009
A1 - Andris Ambainis
A1 - Andrew M. Childs
A1 - François Le Gall
A1 - Seiichiro Tani
AB - 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.
UR - http://arxiv.org/abs/0903.1291v2
J1 - Quantum Information and Computation 10
ER -