Shared entanglement is a resource available to parties communicating over a quantum channel, much akin to public coins in classical communication protocols: the two parties may be given some number of quantum bits jointly prepared in a fixed superposition, prior to communicating with each other. The quantum channel is then said to be "entanglement-assisted." Shared randomness does not help in the transmission of information from one party to another. Moreover, it does not significantly reduce the classical complexity of computing functions vis-a-vis private-coin protocols. On the other hand, prior entanglement leads to startling phenomena such as "quantum teleportation" and "superdense coding." The problem of characterising the power of prior entanglement has baffled many researchers, especially in the setting of bounded-error protocols. It is open whether it leads to more than a factor of two savings (using superdense coding) or more than an additive O(log) savings (when used to create shared randomness). Few lower bounds are known for communication problems in this setting, and are all derived using sophisticated information theoretic techniques. In this paper, we focus on the most basic problem in the setting of communication over an entanglement-assisted quantum channel, that of communicating classical bits from one party to another. We derive optimal bounds on the number of quantum bits required for this task, for any given probability of error.
Shared entanglement is a resource available to parties communicating over a quantum channel, much akin to public coins in classical communication protocols: the two parties may be given some number of quantum bits jointly prepared in a fixed superposition, prior to communicating with each other. The quantum channel is then said to be "entanglement-assisted." Shared randomness does not help in the transmission of information from one party to another. Moreover, it does not significantly reduce the classical complexity of computing functions vis-a-vis private-coin protocols. On the other hand, prior entanglement leads to startling phenomena such as "quantum teleportation" and "superdense coding." The problem of characterising the power of prior entanglement has baffled many researchers, especially in the setting of bounded-error protocols. It is open whether it leads to more than a factor of two savings (using superdense coding) or more than an additive O(log) savings (when used to create shared randomness). Few lower bounds are known for communication problems in this setting, and are all derived using sophisticated information theoretic techniques. In this paper, we focus on the most basic problem in the setting of communication over an entanglement-assisted quantum channel, that of communicating classical bits from one party to another. We derive optimal bounds on the number of quantum bits required for this task, for any given probability of error.
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.
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.
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.
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.
Despite the apparent similarity between shared randomness and shared entanglement in the context of Communication Complexity, our understanding of the latter is not as good as of the former. In particular, there is no known "entanglement analogue" for the famous theorem by Newman, saying that the number of shared random bits required for solving any communication problem can be at most logarithmic in the input length (i.e., using more than O(log n) shared random bits would not reduce the complexity of an optimal solution). In this paper we prove that the same is not true for entanglement. We establish a wide range of tight (up to a polylogarithmic factor) entanglement vs. communication tradeoffs for relational problems. The low end is: for any t>2, reducing shared entanglement from log^t(n) to o(log^{t-2}(n)) qubits can increase the communication required for solving a problem almost exponentially, from O(log^t(n)) to Ω(\sqrt n). The high end is: for any \eps>0, reducing shared entanglement from n^{1-\eps}log(n) to o(n^{1-\eps}/log(n)) can increase the required communication from O(n^{1-\eps}log(n)) to Ω(n^{1-\eps/2}/log(n)). The upper bounds are demonstrated via protocols which are exact and work in the \e{simultaneous message passing model}, while the lower bounds hold for \e{bounded-error protocols}, even in the more powerful \e{model of 1-way communication}. Our protocols use shared EPR pairs while the lower bounds apply to any sort of prior entanglement. We base the lower bounds on a strong direct product theorem for communication complexity of a certain class of relational problems. We believe that the theorem might have applications outside the scope of this work.
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.