  In this article we establish new bounds on the quantum communication
complexity of distributed problems. Specifically, we consider the amount of
communication that is required to transform a bipartite state into another,
typically more entangled, state. We obtain lower bounds in this setting by
studying the Renyi entropy of the marginal density matrices of the distributed
system.
  The communication bounds on quantum state transformations also imply lower
bounds for the model of communication complexity where the task consists of the
the distributed evaluation of a function f(x,y). Our approach encapsulates
several known lower bound methods that use the log-rank or the von Neumann
entropy of the density matrices involved. The technique is also effective for
proving lower bounds on problems involving a promise or for which the "hard"
distributions of inputs are correlated. As examples, we show how to prove a
nearly tight bound on the bounded-error quantum communication complexity of the
inner product function in the presence of unlimited amounts of EPR-type
entanglement and a similarly strong bound on the complexity of the shifted
quadratic character problem.
