Unbounded advantage of adaptivity in entanglement-assisted communication
In the authors' words
Shared entanglement can reduce the amount of classical communication needed to perform distributed computation. This can be achieved either by first measuring the entanglement and then communicating classically, or by adapting the quantum measurement to the received message. Here, we introduce tasks that adaptive protocols can solve using just three entanglement-assisted messages, while the communication cost grows without bound when the quantum receiver is not adaptive. Consequently, no bounded amount of classical communication can reproduce all correlations generated by an entanglement-assisted ternary classical channel. We establish two complementary limitations on the relation between adaptive and non-adaptive quantum protocols. First, every adaptive protocol using a finite entanglement dimension admits a non-adaptive simulation at finite communication cost. Second, every adaptive protocol sending messages can be simulated to within error using non-adaptive messages. Our results reveal the fundamentally unbounded advantage of adaptivity in quantum communication, but also that observing very large advantages requires both high-dimensional entanglement and very precise observations.
Appeared: Tuesday, November 10. arXiv. Preprint, not yet peer-reviewed.
Authors' comment: AI generated the initial versions of all technical results presented in this work. The author's role was limited to asking the questions, understanding the answers and selecting among them, and refining their presentation to meet academic s