next up previous contents
Next: Partially Symmetric Functions Up: Lower Oracle Query Bounds Previous: Determining the Oracle String   Contents


Singleton Functions

An N-bit Boolean function that evaluates to 1 for exactly one input is a singleton function. We will show that for any N-bit singleton function Ambainis' Theorem can always attain a lower query bound of $ \Omega$($ \sqrt{{N}}$), but no better.

The proof of the $ \Omega$($ \sqrt{{N}}$) lower query bound for determining the oracle string in Theorem 2.3.1 can equally well be applied to any singleton function.

Corollary 2.4.1   $ \Omega$($ \sqrt{{N}}$) oracle queries are required to compute any N-bit singleton function in the bounded error setting.

Theorem 2.4.1   $ \Omega$($ \sqrt{{N}}$) is the best lower bound on the number of oracle queries required to compute an N-bit singleton function that can be attained from Theorem 2.1.1.


\begin{proof}
% latex2html id marker 752We will consider every possible choice...
...l = 1$, and by the
pigeonhole principle $m/\max_{i}\{Y_{i}\} \le N$.
\end{proof}

This result coupled with the N/2 lower bound for the singleton function of determining the oracle string leads immediately the the following corollary.

Corollary 2.4.2   There exist functions for which Ambainis' Theorem 2.1.1 can not attain asymptotically tight lower bounds.

Despite this limitation, the theorem can still prove lower bounds for many Boolean functions. From this point forward all our lower bounds are directly or indirectly attained through Ambainis' Theorem.


next up previous contents
Next: Partially Symmetric Functions Up: Lower Oracle Query Bounds Previous: Determining the Oracle String   Contents
Matthew Hayward Lower Query Bounds in the Quantum Oracle Model GitHub Repository