next up previous contents
Next: MAJORITY and PARITY Up: AND, OR, MAJORITY, and Previous: AND, OR, MAJORITY, and   Contents

AND and OR

AND is the $N$-bit Boolean function that evaluates to 1 if and only if its input is $1^{N}$, and OR is the $N$-bit Boolean function that evaluates to 0 if and only if its input is $0^{N}$.

Theorem 2.6.1   $\Omega(\sqrt{N})$ oracle queries are required to compute the AND or the OR of $N$ bits in the bounded error setting.


\begin{proof} % latex2html id marker 816Let $a = N-1$\ and $b = N$. AND evalua... ...virtually identical proof with $a = 0$\ and $b = 1$\ follows for OR. \end{proof}

Beals et al. proved that these lower bounds are asymptotically tight in the bounded error setting [2]. Observe that we could have just as easily used Theorem [*] to attain the same lower bounds, as AND and OR are singleton functions. In the classical case exactly $N$ oracle queries are required to compute AND or OR. Thus, quadratic improvement is possible in the quantum bounded error setting.


Matthew Hayward 2008-04-26