Next: Open Questions Up: Boolean Functions Previous: Nondeterministically Evasive Functions Contents

Sensitive Functions

Nearly all the functions discussed so far have been evasive (or conjectured to be so). In our final result we consider functions that are not necessarily evasive. We call a Boolean function f sensitive if for some input x, there are $\Omega$ (N(f )) Hamming neighbors y of x such that f (x) $\neq$ f (y). It is an open question whether there are any nonsensitive functions.

Theorem 4.4.1 O( $\sqrt[4]{{D(f)}}$ ) oracle queries are required to compute any sensitive function f in the bounded error setting.

$\begin{proof} % latex2html id marker 2350By Lemma \ref{lm:1xky}, $\Omega(\sqrt... ...f)\}$. Thus, $N(f) = \Omega(\sqrt{D(f)})$, and the theorem follows. \end{proof}$

Beals et al. proved $\Omega$ ( $\sqrt[6]{{D(f)}}$ ) oracle queries are required to compute any Boolean function in the bounded error setting, but they suspect that this lower bound is not tight [2]. An open question is whether there are any functions which are not sensitive. If not, then $\Omega$ ( $\sqrt[4]{{D(f)}}$ ) oracle queries are required to compute any Boolean function, which would be an improvement over what is currently known.

Next: Open Questions Up: Boolean Functions Previous: Nondeterministically Evasive Functions Contents

Matthew Hayward Lower Query Bounds in the Quantum Oracle Model GitHub Repository