Skip to content
DraconiticResearch
Search Sources API
190,860 studies31 sourcesUpdated 49 min ago
PreprintarXiv licencearXiv

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

  • Dmytro Gavinsky
Open at sourcePDFDOICite

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(\sqrt 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(\sqrt n) when the players share O(\sqrt n) EPR pairs.

Related

  1. Constant-round quantum advantage in communication complexity for total functions
    Atsuya Hasegawa, François Le Gall
    arXivPreprintarXiv licenceFull textQuantum physics & quantum informationarXiv
  2. On the quantum communication complexity of total functions
    Dmytro Gavinsky
    arXivPreprintarXiv licenceFull textQuantum physics & quantum informationarXiv
  3. Quantum Advantage of Permutation-Invariant Functions in Communication Complexity
    Yunqi Huang, Zekun Ye
    arXivPreprintCC BY 4.0Full textQuantum physics & quantum informationarXiv
  4. Improved Separations between Quantum and Classical Communication Complexity of Total Functions
    François Le Gall
    arXivPreprintarXiv licenceFull textQuantum physics & quantum informationarXiv
  5. Quantum Quasi-Monte Carlo: a window for pre-asymptotic quantum advantage
    Paolo Recchia, Zhan Yu, Kelvin Koor +1
    arXivPreprintCC BY-NC-SA 4.0Full textComputational physicsQuantum physics & quantum informationarXiv

Cite

BibTeXRIS
BibTeX
@misc{gavinsky2026asymptotic,
  title = {{Asymptotic advantage of quantum one-way and SMP communication for total functions}},
  author = {Dmytro Gavinsky},
  howpublished = {arXiv},
  year = {2026},
  month = nov,
  doi = {10.48550/arxiv.2611.07318},
  eprint = {2611.07318},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.07318},
}
RIS
TY  - UNPB
TI  - Asymptotic advantage of quantum one-way and SMP communication for total functions
AU  - Dmytro Gavinsky
PY  - 2026
DA  - 2026/11/05
PB  - arXiv
DO  - 10.48550/arxiv.2611.07318
UR  - https://arxiv.org/abs/2611.07318
AB  - 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(\sqrt 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(\sqrt n) when the players share O(\sqrt n) EPR pairs.
ER  -