PreprintarXiv licencearXiv
Improved Separations between Quantum and Classical Communication Complexity of Total Functions
Abstract
We refine Gavinsky's framework (arXiv:2608.18784) for exponential separations between quantum and randomized communication complexity of total functions and obtain larger separations: polylogarithmic quantum communication versus Ω̃(√n) randomized communication with two quantum messages, and versus Ω(n1−ε) for every fixed 0<ε<1 with more quantum messages.
Related
- EFI Pairs Without One-Way Puzzles: Oracle Separations from Communication Complexity
- On the quantum communication complexity of total functions
- Constant-round quantum advantage in communication complexity for total functions
- Quantum Advantage of Permutation-Invariant Functions in Communication Complexity
- Quantum Cryptomania with Classical Communication without One-Way Functions
BibTeX
@misc{gall2026improved,
title = {{Improved Separations between Quantum and Classical Communication Complexity of Total Functions}},
author = {François Le Gall},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.16726},
eprint = {2609.16726},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.16726},
}
RIS
TY - UNPB
TI - Improved Separations between Quantum and Classical Communication Complexity of Total Functions
AU - François Le Gall
PY - 2026
DA - 2026/10/05
PB - arXiv
DO - 10.48550/arxiv.2609.16726
UR - https://arxiv.org/abs/2609.16726
AB - We refine Gavinsky's framework (arXiv:2608.18784) for exponential separations between quantum and randomized communication complexity of total functions and obtain larger separations: polylogarithmic quantum communication versus Ω̃(√n) randomized communication with two quantum messages, and versus Ω(n^1−ε) for every fixed 0<ε<1 with more quantum messages.
ER -