  We derive lower bounds for tradeoffs between the communication C and space S
for communicating circuits. The first such bound applies to quantum circuits.
If for any function f with image Z the multicolor discrepancy of the
communication matrix of f is 1/2^d, then any bounded error quantum protocol
with space S, in which Alice receives some l inputs, Bob r inputs, and they
compute f(x_i,y_j) for the lr pairs of inputs (x_i,y_j) needs communication
C=\Omega(lrd \log |Z|/S). In particular, n\times n-matrix multiplication over a
finite field F requires C=\Theta(n^3\log^2 |F|/S). We then turn to randomized
bounded error protocols, and derive the bound C=\Omega(n^3/S^2) for Boolean
matrix multiplication, utilizing a new direct product result for the one-sided
rectangle lower bound on randomized communication complexity. This implies a
separation between quantum and randomized protocols.
