Lower bounds for both classical and quantum algorithms have been
attained in the past by analyzing the behavior of the algorithm in the
face of an adversary. Ambainis uses a *quantum adversary* as the
basis for his lower bound theorem; instead of running a quantum
algorithm against one input, it is run against a superposition of
inputs. The formulation of the quantum adversary and the
justification for why a lower bound in the quantum adversary model is
also a lower bound in the standard oracle query model below are
adapted and somewhat simplified from Ambainis' paper
[1].

Ambainis observed that any standard oracle query algorithm *A* that
operates only on a single input is also correct in the quantum
adversary model. Consider a standard oracle query algorithm *A* that
uses *T* queries and succeeds with probability *p*. We assume our
quantum memory register begins in the
0 state.
For every input
*x* {0, 1}^{N}, the algorithm transforms the
initial state
0 *x*
into the final state

| 0 *x*

to the final state

This argument gives us a lower bound in the standard oracle query
model as well. If *T* queries are required of a quantum adversary
algorithm to establish a correct end state with probability *p*, then
no standard oracle query algorithm *A* can compute *f* with bounded
probability *p* in *t* < *T* queries.

This quantum adversary method provides a framework for proving a great diversity of lower bounds. Indeed, nearly every lower bound in this thesis is proved directly or indirectly using Theorem 2.1.1. As useful as the theorem is, it does have limitations, one of which is discussed in Section 2.4.