  We study quantum communication protocols, in which the players' storage
starts out in a state where one qubit is in a pure state, and all other qubits
are totally mixed (i.e. in a random state), and no other storage is available
(for messages or internal computations). This restriction on the available
quantum memory has been studied extensively in the model of quantum circuits,
and it is known that classically simulating quantum circuits operating on such
memory is hard when the additive error of the simulation is exponentially small
(in the input length), under the assumption that the polynomial hierarchy does
not collapse.
  We study this setting in communication complexity. The goal is to consider
larger additive error for simulation-hardness results, and to not use unproven
assumptions.
  We define a complexity measure for this model that takes into account that
standard error reduction techniques do not work here. We define a clocked and a
semi-unclocked model, and describe efficient simulations between those.
  We characterize a one-way communication version of the model in terms of
weakly unbounded error communication complexity.
  Our main result is that there is a quantum protocol using one clean qubit
only and using $O(\log n)$ qubits of communication, such that any classical
protocol simulating the acceptance behaviour of the quantum protocol within
additive error $1/poly(n)$ needs communication $\Omega(n)$.
  We also describe a candidate problem, for which an exponential gap between
the one-clean-qubit communication complexity and the randomized complexity is
likely to hold, and hence a classical simulation of the one-clean-qubit model
within {\em constant} additive error might be hard in communication complexity.
We describe a geometrical conjecture that implies the lower bound.
