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 1N, and OR is the N-bit Boolean function that evaluates to 0 if and only if its input is 0N.

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 812Let $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 2.4.1 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.

next up previous contents
Next: MAJORITY and PARITY Up: AND, OR, MAJORITY, and Previous: AND, OR, MAJORITY, and   Contents
Matthew Hayward Lower Query Bounds in the Quantum Oracle Model GitHub Repository