Improved Separations between Quantum and Classical Communication Complexity of Total Functions

We refine Gavinsky’s framework (arXiv:2608.18784) for exponential separations between quantum and randomized communication complexity of total functions and obtain larger separations: polylogarithmic quantum communication versus $\tilde{\mathrm{\Omega }}(\sqrt{n})$ randomized communication with two quantum messages, and versus $\mathrm{\Omega }(n^{1-\epsilon })$ for every fixed $0<\epsilon <1$ with more quantum messages.