  We propose a new method for proving lower bounds on quantum query algorithms.
Instead of a classical adversary that runs the algorithm with one input and
then modifies the input, we use a quantum adversary that runs the algorithm
with a superposition of inputs. If the algorithm works correctly, its state
becomes entangled with the superposition over inputs. We bound the number of
queries needed to achieve a sufficient entanglement and this implies a lower
bound on the number of queries for the computation.
  Using this method, we prove two new $\Omega(\sqrt{N})$ lower bounds on
computing AND of ORs and inverting a permutation and also provide more uniform
proofs for several known lower bounds which have been previously proven via
variety of different techniques.
