Lower Oracle Query Bounds

In this chapter we present the quantum oracle framework. We first define the quantum oracle model and oracle query complexity, then present a general theorem due to Ambainis [1]. In Section 2.2 we derive a key lemma used throughout the thesis and apply it to a simple problem. We then show that for the problem of determining the oracle string, Ambainis' Theorem can not attain an asymptotically tight lower query bound in Sections 2.3 and 2.4.

Our primary purpose is to demonstrate the power and flexibility of Ambainis' Theorem in attaining lower bounds on broad classes of Boolean functions and simplifying previous proofs. We investigate Boolean functions with partial symmetry in Section 2.5. We apply the result of that section to attain asymptotically tight lower oracle query bounds of $\Omega$($\sqrt{{N}}$), $\Omega$($\sqrt{{N}}$), $\Omega$(N), and $\Omega$(N) for the functions AND, OR, MAJORITY, and PARITY respectively in Section 2.6. Finally we prove $\Omega$($\sqrt{{N}}$) oracle queries are required to compute any N-bit nonconstant symmetric Boolean function in Section 2.7.