PreprintarXiv licencearXiv
Constant-round quantum advantage in communication complexity for total functions
Abstract
We show that there exists a total function for which there is a polynomial gap between the randomized and the constant-round quantum communication complexity. Previously, such a separation was known only for quantum protocols using polynomially many rounds.
Related
- Quantum Advantage of Permutation-Invariant Functions in Communication Complexity
- Asymptotic advantage of quantum one-way and SMP communication for total functions
- On the quantum communication complexity of total functions
- Improved Separations between Quantum and Classical Communication Complexity of Total Functions
- Exponential Quantum Advantage in Numbers-on-Forehead Communication
BibTeX
@misc{hasegawa2026constantround,
title = {{Constant-round quantum advantage in communication complexity for total functions}},
author = {Atsuya Hasegawa and François Le Gall},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2608.19787},
eprint = {2608.19787},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.19787},
}
RIS
TY - UNPB
TI - Constant-round quantum advantage in communication complexity for total functions
AU - Atsuya Hasegawa
AU - François Le Gall
PY - 2026
DA - 2026/10/12
PB - arXiv
DO - 10.48550/arxiv.2608.19787
UR - https://arxiv.org/abs/2608.19787
AB - We show that there exists a total function for which there is a polynomial gap between the randomized and the constant-round quantum communication complexity. Previously, such a separation was known only for quantum protocols using polynomially many rounds.
ER -