An exponential separation between entanglement-assisted and unassisted one-way quantum communication
Abstract
A longstanding question in quantum communication complexity is whether some task can be accomplished with a small amount of communication in the presence of entanglement, yet require much more quantum communication in the absence of entanglement. Separations of this nature were previously known for relational problems and, in the simultaneous message passing model, for partial functions. But it has remained unresolved whether any such separation exists for a total Boolean function. We resolve this question with an exponential separation in the one-way setting: we exhibit a family of total Boolean functions fn: {0,1}n × {0,1}n → {0,1} that can be computed with O(log n) bits of one-way classical communication given prior entanglement, but that require Ω(n1/3) qubits of one-way quantum communication without entanglement. Our function is a special case of the subgroup membership problem, first studied in the communication setting by Aaronson, Le Gall, Russell, and Tani.
Related
- Entanglement-of-formation potentials for feedback-assisted classical communication and randomness distillation
- Exponential onset of scalable entanglement via twist-and-turn dynamics in XY models
- Exponential separation in sensing continuous signals via squeezing
- Exponential Quantum Advantage in Numbers-on-Forehead Communication
- An exponential strong converse for private communication over degradable quantum channels
BibTeX
@misc{anselm2026exponential,
title = {{An exponential separation between entanglement-assisted and unassisted one-way quantum communication}},
author = {Ryan Anselm and Srijita Kundu and Olivier Lalonde and Ashwin Nayak},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.02099},
eprint = {2610.02099},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.02099},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - An exponential separation between entanglement-assisted and unassisted one-way quantum communication
AU - Ryan Anselm
AU - Srijita Kundu
AU - Olivier Lalonde
AU - Ashwin Nayak
PY - 2026
DA - 2026/10/05
PB - arXiv
DO - 10.48550/arxiv.2610.02099
UR - https://arxiv.org/abs/2610.02099
AB - A longstanding question in quantum communication complexity is whether some task can be accomplished with a small amount of communication in the presence of entanglement, yet require much more quantum communication in the absence of entanglement. Separations of this nature were previously known for relational problems and, in the simultaneous message passing model, for partial functions. But it has remained unresolved whether any such separation exists for a total Boolean function. We resolve this question with an exponential separation in the one-way setting: we exhibit a family of total Boolean functions f_n: {0,1}^n × {0,1}^n → {0,1} that can be computed with O(log n) bits of one-way classical communication given prior entanglement, but that require Ω(n^1/3) qubits of one-way quantum communication without entanglement. Our function is a special case of the subgroup membership problem, first studied in the communication setting by Aaronson, Le Gall, Russell, and Tani.
ER -