Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2611.11333

Unbounded advantage of adaptivity in entanglement-assisted communication

Armin Tavakoli

Published Nov 8, 2026• 0 citations
arXivHTMLPDF

Abstract

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 $d$ messages can be simulated to within error $\varepsilon$ using $O(d\log(1/\varepsilon))$ 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.

DOI
10.48550/arxiv.2611.11333

Related papers

Entanglement assisted communication complexity measured by distinguishability

Satyaki Manna, Ankush Pandit, Anubhav Chaturvedi +1 more

We investigate the quantum advantage that can arise in typical two-party communication scenarios, where the sender and the receiver are allowed to share prior correlations. Focusing on communication tasks constrained by the distinguishability of the sender's inputs, we demonstrate that entanglement-assisted communication with both classical and quantum message can outperform classical communication supplemented with shared randomness. We begin by developing a general framework for communication tasks with pre-shared correlations. Within this framework, we establish an equivalence among entanglement-assisted classical communication, entanglement-assisted quantum communication, and quantum communication, showing that no hierarchy exists between these three paradigms. We then investigate the scenario where the receiver has no input and prove that no advantage can arise in this case. However, an advantage in the entanglement-assisted setting emerges once additional constraints are imposed on the dimension of the communicated message. This further highlights the superiority of entanglement-assisted classical communication over standard quantum communication. Then we demonstrate several tasks where the entanglement-assisted protocol using one-bit communication proves to be advantageous over classical communication. Finally, by constructing an explicit class of communication tasks, we show that a non-maximally entangled states outperform the maximally entangled state as a pre-shared resource between the communicating parties.

quant-pharXiv:2603.19105•Mar 20, 2026•6 citations

Adaptive Advantage in Entanglement-Assisted Communications

Jef Pauwels, Stefano Pironio, Emmanuel Zambrini Cruzeiro +1 more

Entanglement is known to boost the efficiency of classical communication. In distributed computation, for instance, exploiting entanglement can reduce the number of communicated bits or increase the probability to obtain a correct answer. Entanglement-assisted classical communication protocols usually consist of two successive rounds: first, a Bell test round, in which the parties measure their local shares of the entangled state, and then a communication round, where they exchange classical messages. Here, we go beyond this standard approach and investigate adaptive uses of entanglement: we allow the receiver to wait for the arrival of the sender's message before measuring their share of the entangled state. We first show that such adaptive protocols improve the success probability in random access codes. Second, we show that once adaptive measurements are used, an entanglement-assisted bit becomes a strictly stronger resource than a qubit in prepare-and-measure scenarios. We briefly discuss the extension of these ideas to scenarios involving quantum communication and we identify resource inequalities.

arXiv:2203.05372•Physical Review Letters•Sep 14, 2022•21 citations

Non-signaling assistance in prepare-and-measure scenarios with classical communication

José Nogueira, Carlos Vieira, Lucas E. A. Porto +3 more

Extracting the full power of non-local correlations in prepare-and-measure (PM) scenarios requires precise control over the timing and structure of the receiver's measurements. Indeed, recent developments in entanglement-assisted classical communication scenarios have shown that adaptive strategies-where the receiver uses the transmitted message to guide their measurement choice-can outperform standard non-adaptive protocols. Moving beyond quantum theory, however, the ultimate limits of such advantages remain largely unexplored. In this work, we thoroughly study adaptive and non-adaptive non-signaling (NS) assistance in PM scenarios with classical communication. We provide simple characterizations of the sets of behaviors that can be realized using both non-adaptive and adaptive NS assistance in arbitrary PM scenarios. As a consequence, we show that non-adaptive NS assistance is already strong enough to reproduce quantum communication with the same message dimension: the transmission of a qudit can be simulated by a classical dit assisted non-adaptively by NS correlations. We then compare adaptive and non-adaptive NS assistance. We prove that any adaptive NS advantage can be traced back to scenarios in which the receiver has no measurement choice, ruling out the genuinely multi-setting advantages found in entanglement-assisted quantum protocols. Finally, we identify all PM scenarios where adaptive NS strategies provide a strict advantage over non-adaptive ones.

quant-pharXiv:2607.01193•Jul 2, 2026•3 citations

Codes for entanglement-assisted classical communication

Tushita Prasad, Markus Grassl

Abstract Entanglement-assisted classical communication (EACC) aims to enhance communication systems using entanglement as an additional resource. However, there is a scarcity of explicit protocols designed for finite transmission scenarios, which presents a challenge for real-world implementation. In response, we introduce a new EACC scheme capable of correcting a fixed number of erasures/errors. It can be adjusted to the available amount of entanglement and sends classical information over a quantum channel. We establish a general framework to accomplish such a task by reducing it to a classical problem. Comparing with specific bounds, we identify optimal parameter ranges. The scheme requires only the implementation of super-dense coding which has been demonstrated successfully in experiments. Furthermore, our results show that an adaptable entanglement use confers a communication advantage. Overall, our work sheds light on how entanglement can elevate various finite-length communication protocols, opening new avenues for exploration in the field.

arXiv:2310.19774•npj Quantum Information•Jan 27, 2025•4 citations

Multiparty Zero-Error Classical Channel Coding With Entanglement

Teresa Piovesan, Giannicola Scarpa, Christian Schaffner

We study the effects of quantum entanglement on the performance of two classical zero-error communication tasks among multiple parties. Both tasks are generalizations of the two-party zero-error channel-coding problem, where a sender and a receiver want to perfectly communicate messages through a one-way classical noisy channel. If the two parties are allowed to share entanglement, there are several positive results that show the existence of channels for which they can communicate strictly more than what they could do with classical resources. In the first task, one sender wants to communicate a common message to multiple receivers. We show that if the number of receivers is greater than a certain threshold then entanglement does not allow for an improvement in the communication for any finite number of uses of the channel. On the other hand, when the number of receivers is fixed, we exhibit a class of channels for which entanglement gives an advantage. The second problem we consider features multiple collaborating senders and one receiver. Classically, cooperation among the senders might allow them to communicate on average more messages than the sum of their individual possibilities. We show that whenever a channel allows single-sender entanglement-assisted advantage, then the gain extends also to the multisender case. Furthermore, we show that entanglement allows for a peculiar amplification of information which cannot happen classically, for a fixed number of uses of the channels.

arXiv:1403.5003•IEEE Transactions on Information Theory•Dec 10, 2014•4 citations

On communication over an entanglement-assisted quantum channel

Ashwin Nayak, Julia Salzman

Shared entanglement is a resource available to parties communicating over a quantum channel, much akin to public coins in classical communication protocols. Whereas shared randomness does not help in the transmission of information, or significantly reduce the classical complexity of computing functions (as compared to private-coin protocols), shared entanglement leads to startling phenomena such as "quantum teleportation" and "superdense coding."The problem of characterising the power of prior entanglement has puzzled many researchers. In this paper, we revisit the problem of transmitting classical bits over an entanglement-assisted quantum channel. We derive a new, optimal bound on the number of quantum bits required for this task, for any given probability of error. All known lower bounds in the setting of bounded error entanglement-assisted communication are based on sophisticated information theoretic arguments. In contrast, our result is derived from first principles, using a simple linear algebraic technique.

ACM Symposium on Theory of Computing (STOC)•Jan 1, 2002•28 citations
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 ddd messages can be simulated to within error ε\varepsilonε using O(dlog⁡(1/ε))O(d\log(1/\varepsilon))O(dlog(1/ε)) 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.
We investigate the quantum advantage that can arise in typical two-party communication scenarios, where the sender and the receiver are allowed to share prior correlations. Focusing on communication tasks constrained by the distinguishability of the sender's inputs, we demonstrate that entanglement-assisted communication with both classical and quantum message can outperform classical communication supplemented with shared randomness. We begin by developing a general framework for communication tasks with pre-shared correlations. Within this framework, we establish an equivalence among entanglement-assisted classical communication, entanglement-assisted quantum communication, and quantum communication, showing that no hierarchy exists between these three paradigms. We then investigate the scenario where the receiver has no input and prove that no advantage can arise in this case. However, an advantage in the entanglement-assisted setting emerges once additional constraints are imposed on the dimension of the communicated message. This further highlights the superiority of entanglement-assisted classical communication over standard quantum communication. Then we demonstrate several tasks where the entanglement-assisted protocol using one-bit communication proves to be advantageous over classical communication. Finally, by constructing an explicit class of communication tasks, we show that a non-maximally entangled states outperform the maximally entangled state as a pre-shared resource between the communicating parties.
Entanglement is known to boost the efficiency of classical communication. In distributed computation, for instance, exploiting entanglement can reduce the number of communicated bits or increase the probability to obtain a correct answer. Entanglement-assisted classical communication protocols usually consist of two successive rounds: first, a Bell test round, in which the parties measure their local shares of the entangled state, and then a communication round, where they exchange classical messages. Here, we go beyond this standard approach and investigate adaptive uses of entanglement: we allow the receiver to wait for the arrival of the sender's message before measuring their share of the entangled state. We first show that such adaptive protocols improve the success probability in random access codes. Second, we show that once adaptive measurements are used, an entanglement-assisted bit becomes a strictly stronger resource than a qubit in prepare-and-measure scenarios. We briefly discuss the extension of these ideas to scenarios involving quantum communication and we identify resource inequalities.
Extracting the full power of non-local correlations in prepare-and-measure (PM) scenarios requires precise control over the timing and structure of the receiver's measurements. Indeed, recent developments in entanglement-assisted classical communication scenarios have shown that adaptive strategies-where the receiver uses the transmitted message to guide their measurement choice-can outperform standard non-adaptive protocols. Moving beyond quantum theory, however, the ultimate limits of such advantages remain largely unexplored. In this work, we thoroughly study adaptive and non-adaptive non-signaling (NS) assistance in PM scenarios with classical communication. We provide simple characterizations of the sets of behaviors that can be realized using both non-adaptive and adaptive NS assistance in arbitrary PM scenarios. As a consequence, we show that non-adaptive NS assistance is already strong enough to reproduce quantum communication with the same message dimension: the transmission of a qudit can be simulated by a classical dit assisted non-adaptively by NS correlations. We then compare adaptive and non-adaptive NS assistance. We prove that any adaptive NS advantage can be traced back to scenarios in which the receiver has no measurement choice, ruling out the genuinely multi-setting advantages found in entanglement-assisted quantum protocols. Finally, we identify all PM scenarios where adaptive NS strategies provide a strict advantage over non-adaptive ones.
Abstract Entanglement-assisted classical communication (EACC) aims to enhance communication systems using entanglement as an additional resource. However, there is a scarcity of explicit protocols designed for finite transmission scenarios, which presents a challenge for real-world implementation. In response, we introduce a new EACC scheme capable of correcting a fixed number of erasures/errors. It can be adjusted to the available amount of entanglement and sends classical information over a quantum channel. We establish a general framework to accomplish such a task by reducing it to a classical problem. Comparing with specific bounds, we identify optimal parameter ranges. The scheme requires only the implementation of super-dense coding which has been demonstrated successfully in experiments. Furthermore, our results show that an adaptable entanglement use confers a communication advantage. Overall, our work sheds light on how entanglement can elevate various finite-length communication protocols, opening new avenues for exploration in the field.
We study the effects of quantum entanglement on the performance of two classical zero-error communication tasks among multiple parties. Both tasks are generalizations of the two-party zero-error channel-coding problem, where a sender and a receiver want to perfectly communicate messages through a one-way classical noisy channel. If the two parties are allowed to share entanglement, there are several positive results that show the existence of channels for which they can communicate strictly more than what they could do with classical resources. In the first task, one sender wants to communicate a common message to multiple receivers. We show that if the number of receivers is greater than a certain threshold then entanglement does not allow for an improvement in the communication for any finite number of uses of the channel. On the other hand, when the number of receivers is fixed, we exhibit a class of channels for which entanglement gives an advantage. The second problem we consider features multiple collaborating senders and one receiver. Classically, cooperation among the senders might allow them to communicate on average more messages than the sum of their individual possibilities. We show that whenever a channel allows single-sender entanglement-assisted advantage, then the gain extends also to the multisender case. Furthermore, we show that entanglement allows for a peculiar amplification of information which cannot happen classically, for a fixed number of uses of the channels.
Shared entanglement is a resource available to parties communicating over a quantum channel, much akin to public coins in classical communication protocols. Whereas shared randomness does not help in the transmission of information, or significantly reduce the classical complexity of computing functions (as compared to private-coin protocols), shared entanglement leads to startling phenomena such as "quantum teleportation" and "superdense coding."The problem of characterising the power of prior entanglement has puzzled many researchers. In this paper, we revisit the problem of transmitting classical bits over an entanglement-assisted quantum channel. We derive a new, optimal bound on the number of quantum bits required for this task, for any given probability of error. All known lower bounds in the setting of bounded error entanglement-assisted communication are based on sophisticated information theoretic arguments. In contrast, our result is derived from first principles, using a simple linear algebraic technique.