  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 conjecture of Klauck and Lim. In contrast, all prior quantum versus
classical communication separations required at least $\Omega(\log N)$ clean
qubits. The function demonstrating our separation also has an efficient
protocol in the quantum-simultaneous-with-entanglement model of cost $O(\log N
)$. We thus recover the state-of-the-art separations between quantum and
classical communication complexity. Our proof is based on a recent
hypercontractivity inequality introduced by Ellis, Kindler, Lifshitz, and
Minzer, in conjunction with tools from the representation theory of compact Lie
groups.
