Communication complexity of quantum channels

The process of state preparation, its transmission and subsequent measurement can be classically simulated through the communication of some amount of classical information. Recently, we proved that the minimal communication cost is the minimum of a convex functional over a space of suitable probability distributions. It is now proved that this optimization problem is the dual of a geometric programming maximization problem, which displays some appealing properties. First, the number of variables grows linearly with the input size. Second, the objective function is linear in the input parameters and the variables. Finally, the constraints do not depend on the input parameters. These properties imply that, once a feasible point is found, the computation of a lower bound for any two-party quantum communication problem is linearly complex. We illustrate the method by analytically deriving some non-trivial lower bounds. Finally, we conjecture the lower bound n 2^n for a noiseless channel with capacity of n qubits. This lower bound would have interesting consequences in the context of the recent debate on the reality of the quantum state.