  By how much must the communication complexity of a function increase if we
demand that the parties not only correctly compute the function but also return
all registers (other than the one containing the answer) to their initial
states at the end of the communication protocol? Protocols that achieve this
are referred to as clean and the associated cost as the clean communication
complexity. Here we present clean protocols for calculating the Inner Product
of two $n$-bit strings, showing that (in the absence of pre-shared
entanglement) at most $n+3$ qubits or $n+O(\sqrt{n})$ bits of communication are
required. The quantum protocol provides inspiration for obtaining the optimal
method to implement distributed CNOT gates in parallel whilst minimizing the
amount of quantum communication. For more general functions, we show that
nearly all Boolean functions require close to $2n$ bits of classical
communication to compute and close to $n$ qubits if the parties have access to
pre-shared entanglement. Both of these values are maximal for their respective
paradigms.
