  We prove a very general lower bound technique for quantum and randomized
query complexity, that is easy to prove as well as to apply. To achieve this,
we introduce the use of Kolmogorov complexity to query complexity. Our
technique generalizes the weighted, unweighted methods of Ambainis, and the
spectral method of Barnum, Saks and Szegedy. As an immediate consequence of our
main theorem, adversary methods can only prove lower bounds for boolean
functions $f$ in $O(\min(\sqrt{n C_0(f)},\sqrt{n C_1(f)}))$, where $C_0, C_1$
is the certificate complexity, and $n$ is the size of the input. We also derive
a general form of the ad hoc weighted method used by Hoyer, Neerbek and Shi to
give a quantum lower bound on ordered search and sorting.
