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
(),
(),
(*N*), and (*N*) for the functions AND, OR, MAJORITY, and
PARITY respectively in Section
2.6. Finally we prove
() oracle
queries are required to compute any *N*-bit nonconstant symmetric
Boolean function in Section 2.7.

- Preliminaries

- A Lemma for Proving Lower Query Bounds

- Determining the Oracle String
- Singleton Functions
- Partially Symmetric Functions
- AND, OR, MAJORITY, and PARITY

- Nonconstant Symmetric Functions