2012 Jan 31 at 12:00
RAC 2009
Robin Kothari, PhD candidate, David R. Cheriton School of Comp. Sci., Univ. Waterloo
The quantum query complexity of evaluating any read-once formula with n black-box input bits is $Theta(sqrt(n))$. However, the corresponding problem for read-many formulas (i.e., formulas in which the inputs have fanout) is not well understood. Although the optimal read-once formula evaluation algorithm can be applied to any formula, it can be suboptimal if the inputs have large fanout. We give an algorithm for evaluating any formula with n inputs, size S, and G gates using $O(min{n, sqrt{S}, n^{1/2} G^{1/4}})$ quantum queries. Furthermore, we show that this algorithm is optimal, since for any $n,S,G$ there exists a formula with n inputs, size at most $S$, and at most G gates that requires $Omega(min{n, sqrt{S}, n^{1/2} G^{1/4}})$ queries. We also show that the algorithm remains nearly optimal for circuits of any particular depth $k >= 3$, and we give a linear-size circuit of depth 2 that requires $Omega~(n^{5/9})$ queries. Applications of these results include an $Omega~(n^{19/18})$ lower bound for Boolean matrix product verification, a nearly tight characterization of the quantum query complexity of evaluating constant-depth circuits with bounded fanout, new formula gate count lower bounds for several functions including PARITY, and a construction of an $AC^0$ circuit of linear size that can only be evaluated by a formula with $Omega(n^{2-epsilon})$ gates.