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 \times 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(\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.