In Chapter 2, we define the quantum oracle model, and present Ambainis' Theorem for proving lower bounds within this framework. We examine a shortcoming of Ambainis' Theorem, and then derive two theorems and use them to prove lower query bounds for symmetric functions.
In Chapter 3, we apply the results of Chapter 2 to the interesting and well studied case of nontrivial monotone graph properties. Finding the results wanting we appeal directly to Ambainis' Theorem to establish new lower bounds for graph connectivity and bipartiteness. Finally we show there is no quantum extension of the AanderaaKarpRosenberg conjecture in the bounded error setting.
In Chapter 4, we examine classes of functions that do not have the inherent symmetries of those in chapters 2 and 3. We provide lower query bounds for tree functions, nondeterministically evasive functions, and sensitive functions.
We conclude in Chapter 5 with a brief examination of some open questions for lower oracle query bounds in the bounded error setting, and quantum computing in general.
Many of the results in this thesis have been attained previously by other authors. We present these results again to illustrate how Ambainis' Theorem can provide relatively simpler proofs for a variety of problems. Table 1.1 summarizes our results and credits previous papers where appropriate. All results are in the quantum bounded error setting.
