Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR26-336 | 5th November 2026 02:48

Asymptotic advantage of quantum one-way and SMP communication for total functions

RSS-Feed




TR26-336
Authors: Dmytro Gavinsky
Publication: 22nd November 2026 15:38
Downloads: 18
Keywords: 


Abstract:

We exhibit a total Boolean function on n input bits whose bounded-error quantum simultaneous-message (and hence one-way) communication complexity is in O(?n), whereas its randomised one-way (and hence simultaneous-message) communication complexity is in ?(n).
The same function admits a classical simultaneous-message protocol of cost O(?n) when the players share O(?n) EPR pairs.



ISSN 1433-8092 | Imprint