next up previous contents
Next: Tree Functions Up: Lower Query Bounds in Previous: No Quantum Extension of   Contents


Boolean Functions

In this chapter we consider increasingly general classes of functions. We first examine lower bounds for tree functions in Section 4.1 and prove $ \Omega$($ \sqrt[4]{{N}}$) oracle queries are required to compute a tree function of N bits.

We define nondeterministic decision tree complexity in Section 4.2. We then prove that $ \Omega$($ \sqrt{{N}}$) oracle queries are required to compute any N bit Boolean function with nondeterministic decision tree complexity N in Section 4.3. Finally in Section 4.4 we present our most general result: $ \Omega$($ \sqrt[4]{{D(f)}}$) oracle queries are required to compute a class of Boolean functions that meet a sensitivity condition and have deterministic decision tree complexity D(f ).



Subsections
next up previous contents
Next: Tree Functions Up: Lower Query Bounds in Previous: No Quantum Extension of   Contents
Matthew Hayward Lower Query Bounds in the Quantum Oracle Model GitHub Repository