  The quantum adversary method is a versatile method for proving lower bounds
on quantum algorithms. It yields tight bounds for many computational problems,
is robust in having many equivalent formulations, and has natural connections
to classical lower bounds. A further nice property of the adversary method is
that it behaves very well with respect to composition of functions. We
generalize the adversary method to include costs--each bit of the input can be
given an arbitrary positive cost representing the difficulty of querying that
bit. We use this generalization to exactly capture the adversary bound of a
composite function in terms of the adversary bounds of its component functions.
Our results generalize and unify previously known composition properties of
adversary methods, and yield as a simple corollary the Omega(sqrt{n}) bound of
Barnum and Saks on the quantum query complexity of read-once functions.
