next up previous contents
Next: Nonconstant Symmetric Functions Up: AND, OR, MAJORITY, and Previous: AND and OR   Contents

MAJORITY and PARITY

It is tempting to hope that all Boolean functions, or at least all symmetric Boolean functions, realize the quadratic speedup of AND and OR. Unfortunately the functions MAJORITY and PARITY show that for some problems the speedup is at best a constant factor.

MAJORITY is the N-bit Boolean function that evaluates to 1 if and only if more than half of the input bits are 1. PARITY is the N-bit Boolean function that evaluates to 1 if and only if the input has an even Hamming weight.

Theorem 2.6.2   $ \Omega$(N) oracle queries are required to compute the MAJORITY or the PARITY of N bits in the bounded error setting.


\begin{proof} % latex2html id marker 824Let $a = \left\lfloor N/2 \right\rfloo... ...{displaymath}oracle queries are required to compute either function. \end{proof}

Since both classical and quantum algorithms can compute any function of N bits with N oracle queries, this lower bound is asymptotically tight. Beals et al. previously proved these results [2]; again, the simplicity that Ambainis' Theorem affords is the main point of interest.

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