OpenAlex ·
Improved Separations between Quantum and Classical Communication Complexity of Total Functions
- Published
- Source
- OpenAlex
- Published in
- arXiv (Cornell University)
- DOI
- 10.48550/arxiv.2609.16726
- Original
- Read it at the publisher
- Topics
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 $\tildeΩ(\sqrt n)$ randomized communication with two quantum messages, and versus $Ω(n^{1-\varepsilon})$ for every fixed $0<\varepsilon<1$ with more quantum messages.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Artificial Intelligence
Nonlocal Magic across the Many-Body Localization Crossover
The Expressive Power of Constrained QAOA: What You Might Have MISsed
Strong converse for the quantum capacity of the pure-loss bosonic channel
Spectral Optimization for Absolutely PPT States: Purity, Entropy, and Volume Decay
Comparing magic state cultivation methods using matrix product states
Get the few papers worth your time in Artificial Intelligence every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.