Preprint
Oct 2026
Optimal and Verifiable Quantum Advantages in Communication Complexity
We establish optimal quantum-classical separations in communication complexity for search problems. We introduce a total search problem called Pelagic Fourier Fishing and show that it admits an $n$-qubit quantum one-way protocol, whereas every randomized two-way protocol requires $\Omega(2^n)$ bits of communication. We...
Ryan A. Anselm, Michelle Ding, D. Gilboa et al.
· 0 citations