We study the one-clean-qubit model of quantum communication where one qubit is in a pure state and all other qubits are maximally mixed. We demonstrate a partial function that has a quantum protocol of cost O(\log N) in this model, however, every interactive randomized protocol has cost \Omega(\sqrt{N}), settling a ... more >>>