  We consider the process consisting of preparation, transmission through a
quantum channel, and subsequent measurement of quantum states. The
communication complexity of the channel is the minimal amount of classical
communication required for classically simulating it. Recently, we reduced the
computation of this quantity to a convex minimization problem with linear
constraints. Every solution of the constraints provides an upper bound on the
communication complexity. In this paper, we derive the dual maximization
problem of the original one. The feasible points of the dual constraints, which
are inequalities, give lower bounds on the communication complexity, as
illustrated with an example. The optimal values of the two problems turn out to
be equal (zero duality gap). By this property, we provide necessary and
sufficient conditions for optimality in terms of a set of equalities and
inequalities. We use these conditions and two reasonable but unproven
hypotheses to derive the lower bound $n 2^{n-1}$ for a noiseless quantum
channel with capacity equal to $n$ qubits. This lower bound can have
interesting consequences in the context of the recent debate on the reality of
the quantum state.
