PreprintarXiv licencearXiv
On the quantum communication complexity of total functions
Abstract
We present a total function with a polylogarithmic two-message quantum protocol, whereas every randomised protocol, even with arbitrarily many rounds, requires polynomial communication.
Related
- Constant-round quantum advantage in communication complexity for total functions
- Improved Separations between Quantum and Classical Communication Complexity of Total Functions
- Asymptotic advantage of quantum one-way and SMP communication for total functions
- Quantum Advantage of Permutation-Invariant Functions in Communication Complexity
- Quantum Encodings, Private Messages, and Communication Complexity
BibTeX
@misc{gavinsky2026quantum,
title = {{On the quantum communication complexity of total functions}},
author = {Dmytro Gavinsky},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2608.18784},
eprint = {2608.18784},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.18784},
}
RIS
TY - UNPB
TI - On the quantum communication complexity of total functions
AU - Dmytro Gavinsky
PY - 2026
DA - 2026/10/17
PB - arXiv
DO - 10.48550/arxiv.2608.18784
UR - https://arxiv.org/abs/2608.18784
AB - We present a total function with a polylogarithmic two-message quantum protocol, whereas every randomised protocol, even with arbitrarily many rounds, requires polynomial communication.
ER -