Exponential Quantum Advantage in Numbers-on-Forehead Communication
The paper establishes an exponential advantage for quantum communication in a three-party Numbers-on-Forehead (NOF) setting using the Interleaved Unitary Product (IUP) problem. It shows that a quantum protocol can solve this problem with only logarithmic communication, while any classical randomized protocol requires superpolynomial communication. This demonstrates an unconditional exponential separation between quantum and randomized communication for this specific partial Boolean function.