A Lower Query Bound Proving Framework due to Ambainis

Ambainis [1] proved the following fundamental result:

Theorem 2.1.1 (Ambainis)   Let f be an N-bit Boolean function and let X and Y be two sets of inputs such that f (x) $\neq$ f (y) whenever x $\in$ X and y $\in$ Y. Let P $\subseteq$ X x Y be a relation between X and Y with the following properties:

1. Every element of X is related to at least m elements of Y by P.

2. Every element of Y is related to at least m' elements of X by P.

3. For all i, every element x $\in$ X is related to at most l elements y $\in$ Y such that x_i $\neq$ y_i

4. For all i, every element y $\in$ Y is related to at most l' elements x $\in$ X such that x_i $\neq$ y_i

Then

$$\Omega$$$$\left(\vphantom{\sqrt{\frac{mm^{\prime}}{ll^{\prime}}}}\right.$$$$\sqrt{{\frac{mm^{\prime}}{ll^{\prime}}}}$$$$\left.\vphantom{\sqrt{\frac{mm^{\prime}}{ll^{\prime}}}}\right)$$

oracle queries are required by any quantum algorithm to compute f in the bounded error setting.

This theorem will be the primary means of proving lower bounds in this thesis. Its appeal is twofold; first, it leads to reasonably simple proofs, and second, it unifies many existing lower bounds into a single framework.