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 $\asO[]{\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 trade-offs for relational problems. The low end is:\ for any $t>2$, reducing shared entanglement from $log^tn$ to $\aso[]{log^{t-2}n}$ qubits can increase the communication required for solving a problem almost exponentially, from $\asO[]{log^tn}$ to $\asOm[]{\sqrt n}$. The high end is:\ for any $\eps>0$, reducing shared entanglement from $n^{1-\eps}\log n$ to $\aso[]{n^{1-\eps}/\log n}$ can increase the required communication from $\asO[]{n^{1-\eps}\log n}$ to $\asOm[]{n^{1-\eps/2}/\log n}$. The upper bounds are demonstrated via protocols which are \e{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.
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 \asO[]logn 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 trade-offs for relational problems. The low end is:\ for any t>2, reducing shared entanglement from logtn to \aso[]logt−2n qubits can increase the communication required for solving a problem almost exponentially, from \asO[]logtn to \asOm[]n. The high end is:\ for any \eps>0, reducing shared entanglement from n1−\epslogn to \aso[]n1−\eps/logn can increase the required communication from \asO[]n1−\epslogn to \asOm[]n1−\eps/2/logn. The upper bounds are demonstrated via protocols which are \e{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.
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 study shared randomness in the context of multi-party number-in-hand communication protocols in the simultaneous message passing model. We show that with three or more players, shared randomness exhibits new interesting properties that have no direct analogues in the two-party case.
First, we demonstrate a hierarchy of modes of shared randomness, with the usual shared randomness where all parties access the same random string as the form in the hierarchy. We show exponential separations between its levels, and some of our bounds may be of independent interest. For example, we show that the equality function can be solved by a protocol of constant length using the weakest form of shared randomness, which we call XOR-shared
Second, we show that quantum communication cannot replace shared randomness in the k-party case, where k >= 3 is any constant. We demonstrate a promise function GP_k that can be computed by a classical protocol of constant length when (the form of) shared randomness is available, but any quantum protocol without shared randomness must send n^Omega(1) qubits to compute it. Moreover, the quantum complexity of GP_k remains n^Omega(1) even if the second strongest mode of shared randomness is available. While a somewhat similar separation was already known in the two-party case, in the multi-party case our statement is qualitatively stronger:
* In the two-party case, only a relational communication problem with similar properties is known.
* In the two-party case, the gap between the two complexities of a problem can be at most exponential, as it is known that 2^(O(c)) log n qubits can always replace shared randomness in any c-bit protocol. Our bounds imply that with quantum communication alone, in general, it is not possible to simulate efficiently even a three-bit three-party classical protocol that uses shared randomness.
We study shared randomness in the context of multi-party number-in-hand communication protocols in the simultaneous message passing model. We show that with three or more players, shared randomness exhibits new interesting properties that have no direct analogues in the two-party case. First, we demonstrate a hierarchy of modes of shared randomness, with the usual shared randomness where all parties access the same random string as the strongest form in the hierarchy. We show exponential separations between its levels, and some of our bounds may be of independent interest. For example, we show that the equality function can be solved by a protocol of constant length using the weakest form of shared randomness, which we call "XOR-shared randomness." Second, we show that quantum communication cannot replace shared randomness in the k-party case, where k >= 3 is any constant. We demonstrate a promise function GP_k that can be computed by a classical protocol of constant length when (the strongest form of) shared randomness is available, but any quantum protocol without shared randomness must send n^Omega(1) qubits to compute it. Moreover, the quantum complexity of GP_k remains n^Omega(1) even if the "second strongest" mode of shared randomness is available. While a somewhat similar separation was already known in the two-party case, in the multi-party case our statement is qualitatively stronger: * In the two-party case, only a relational communication problem with similar properties is known. * In the two-party case, the gap between the two complexities of a problem can be at most exponential, as it is known that 2^(O(c)) log n qubits can always replace shared randomness in any c-bit protocol. Our bounds imply that with quantum communication alone, in general, it is not possible to simulate efficiently even a three-bit three-party classical protocol that uses shared randomness.
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.
We investigate the randomized and quantum communication complexities of the well-studied Equality function with small error probability ε, getting optimal constant factors in the leading terms in a number of different models. In the randomized model, 1) we give a general technique to convert public-coin protocols to private-coin protocols by incurring a small multiplicative error, at a small additive cost. This is an improvement over Newman's theorem [Inf. Proc. Let.'91] in the dependence on the error parameter. 2) Using this we obtain a (log(n/ε2)+4)-cost private-coin communication protocol that computes the n-bit Equality function, to error ε. This improves upon the log(n/ε3)+O(1) upper bound implied by Newman's theorem, and matches the best known lower bound, which follows from Alon [Comb. Prob. Comput.'09], up to an additive loglog(1/ε)+O(1). In the quantum model, 1) we exhibit a one-way protocol of cost log(n/ε)+4, that uses only pure states and computes the n-bit Equality function to error ε. This bound was implicitly already shown by Nayak [PhD thesis'99]. 2) We show that any ε-error one-way protocol for n-bit Equality that uses only pure states communicates at least log(n/ε)−loglog(1/ε)−O(1) qubits. 3) We exhibit a one-way protocol of cost log(n/ε)+3, that uses mixed states and computes the n-bit Equality function to error ε. This is also tight up to an additive loglog(1/ε)+O(1), which follows from Alon's result. 4) We study the number of EPR pairs required to be shared in an entanglement-assisted one-way protocol. Our upper bounds also yield upper bounds on the approximate rank and related measures of the Identity matrix.
We study shared randomness in the context of multi-party number-in-hand communication protocols in the simultaneous message passing model. We show that with three or more players, shared randomness exhibits new interesting properties that have no direct analogues in the two-party case. First, we demonstrate a hierarchy of modes of shared randomness, with the usual shared randomness where all parties access the same random string as the strongest form in the hierarchy. We show exponential separations between its levels, and some of our bounds may be of independent interest. For example, we show that the equality function can be solved by a protocol of constant length using the weakest form of shared randomness, which we call XOR-shared randomness. Second, we show that quantum communication cannot replace shared randomness in the k-party case, where k ≥ 3 is any constant. We demonstrate a promise function GPkthat can be computed by a classical protocol of constant length when (the strongest form of) shared randomness is available, but any quantum protocol without shared randomness must send nΩ(1)qubits to compute it. Moreover, the quantum complexity of GPk remains nΩ(1)even if the “second strongest” mode of shared randomness is available. While a somewhat similar separation was already known in the two-party case, in the multi-party case our statement is qualitatively stronger: · In the two-party case, only a relational communication problem with similar properties is known. · In the two-party case, the gap between the two complexities of a problem can be at most exponential, as it is known that 2O(c)log n qubits can always replace shared randomness in any c-bit protocol. Our bounds imply that with quantum communication alone, in general, it is not possible to simulate efficiently even a three-bit three-party classical protocol that uses shared randomness.