Unbounded-error One-way Classical and Quantum Communication Complexity

Kazuo Iwama, Harumichi Nishimura, Rudy Raymond +1

This paper studies the gap between quantum one-way communication complexity $Q(f)$ and its classical counterpart $C(f)$, under the {\em unbounded-error} setting, i.e., it is enough…