next up previous contents
Next: Determining the Oracle String Up: A Lemma for Proving Previous: A Lemma for Proving   Contents


Application to Generalized XOR

To see how simple proofs can be with Lemma 2.2.1 we provide an example. Generalized XOR is the N-bit Boolean function that is 0 if and only if its input bits are all the same.

Theorem 2.2.1   $ \Omega$($ \sqrt{{N}}$) oracle queries are required to compute the generalized XOR of N bits in the bounded error setting.


\begin{proof}
% latex2html id marker 711The generalized XOR of $0^{N}$ is $0$...
...}$ is 1. The theorem follows from Lemma
\ref{lm:1xky} with $k = N$.
\end{proof}

This lower bound is asymptotically tight: Beals et al. provide O($ \sqrt{{N}}$) oracle query algorithms for computing the AND or OR of N bits in the bounded error setting [2], and the generalized XOR of N bits is just $ \overline{{AND \vee
\overline{OR}}}$. Unfortunately, Ambainis' Theorem does not always perform this well, as we demonstrate in the next two sections.


next up previous contents
Next: Determining the Oracle String Up: A Lemma for Proving Previous: A Lemma for Proving   Contents
Matthew Hayward Lower Query Bounds in the Quantum Oracle Model GitHub Repository