I show that a simple multiparty communication task can be performed more efficiently with quantum communication than with classical communication, even with low detection efficiency $\ensuremath{\eta}.$ The task is a communication complexity problem in which distant parties need to compute a function of the distributed inputs, while minimizing the amount of communication between them. A realistic quantum optical setup is suggested that can demonstrate a five-party quantum protocol with higher-than-classical performance, provided \ensuremath{\eta}>0.33.
I show that a simple multiparty communication task can be performed more efficiently with quantum communication than with classical communication, even with low detection efficiency \ensuremathη. The task is a communication complexity problem in which distant parties need to compute a function of the distributed inputs, while minimizing the amount of communication between them. A realistic quantum optical setup is suggested that can demonstrate a five-party quantum protocol with higher-than-classical performance, provided \ensuremath{\eta}>0.33.
Quantum entanglement cannot be used to achieve direct communication between remote parties, but it can reduce the communication needed for some problems. Let each of k parties hold some partial input data to some fixed k-variable function f. The communication complexity of f is the minimum number of classical bits required to be broadcasted for every party to know the value of f on their inputs. We construct a function G such that for the one-round communication model and three parties, G can be computed with n+1 bits of communication when the parties share prior entanglement. We then show that without entangled particles, the one-round communication complexity of G is (3/2)n+1. Next we generalize this function to a function F. We show that if the parties share prior quantum entanglement, then the communication complexity of F is exactly k. We also show that, if no entangled particles are provided, then the communication complexity of F is roughly klog2k. These two results prove communication complexity separations better than a constant number of bits.
Communication complexity is the amount of communication needed to compute a function when the function inputs are distributed over multiple parties. In its simplest form, one-way communication complexity, Alice and Bob compute a function f(x,y) , where x is given to Alice and y is given to Bob, and only one message from Alice to Bob is allowed. A fundamental question in quantum information is the relationship between one-way quantum and classical communication complexities, i.e., how much shorter the message can be if Alice is sending a quantum state instead of bit strings? We make some progress towards this question with the following results.Let f:X×Y→Z∪{⊥} be a partial function and μ be a distribution with support contained in f−1(Z) . Denote d=|Z| . Let Rϵ1,μ(f) be the classical one-way communication complexity of f ; Qϵ1,μ(f) be the quantum one-way communication complexity of f and Qϵ1,μ,∗(f) be the entanglement-assisted quantum one-way communication complexity of f , each with distributional error (average error over μ ) at most ϵ . We show:1) If μ is a product distribution, η>0 and 0≤ϵ≤1−1/d , then, R2ϵ−dϵ2/(d−1)+η1,μ(f)≤2Qϵ1,μ,∗(f)+O(loglog(1/η)). 2)If μ is a non-product distribution and Z={0,1} , then ∀ϵ,η>0 such that ϵ/η+η<0.5 , R3η1,μ(f)=O(Qϵ1,μ(f)⋅CS(f)/η3), where CS(f)=maxyminz&am
A two-party quantum communication process with classical inputs and outcomes can be simulated by replacing the quantum channel with a classical one. The minimal amount of classical communication required to reproduce the statistics of the quantum process is called its communication complexity. In the case of many instances simulated in parallel, the minimal communication cost per instance is called the asymptotic communication complexity. Previously, we reduced the computation of the asymptotic communication complexity to a convex minimization problem. In most cases, the objective function does not have an explicit analytic form, as the function is defined as the maximum over an infinite set of convex functions. Therefore, the overall problem takes the form of a minimax problem and cannot directly be solved by standard optimization methods. In this paper, we introduce a simple algorithm to compute the asymptotic communication complexity. For some special cases with an analytic objective function one can employ available convex-optimization libraries. In the tested cases our method turned out to be notably faster. Finally, using our method we obtain 1.238 bits as a lower bound on the asymptotic communication complexity of a noiseless quantum channel with the capacity of 1 qubit. This improves the previous bound of 1.208 bits.
In communication complexity, a number of distant parties have the task of calculating a distributed function of their inputs, while minimizing the amount of communication between them. It is known that with quantum resources, such as entanglement and quantum channels, one can obtain significant reductions in the communication complexity of some tasks. In this work, we study the role of the quantum superposition of the direction of communication as a resource for communication complexity. We present a tripartite communication task for which such a superposition allows for an exponential saving in communication, compared to one-way quantum (or classical) communication; the advantage also holds when we allow for protocols with bounded error probability.
We consider a quantum and a classical version of a multi-party function computation problem with n players, where players 2,…,n need to communicate appropriate information to player 1 so that a “generalized” inner product function with an appropriate promise can be calculated. In the quantum version of the protocol, the players have access to entangled qudits but the communication is still classical. The communication complexity of a given protocol is the total number of classical bits that need to be communicated. When n is prime, and for our chosen function, we exhibit a quantum protocol (with complexity (n−1)(logn) bits) and a classical protocol (with complexity ((n−1)2(logn2) bits)). Furthermore, we present an integer linear programming formulation for determining a lower bound on the classical communication complexity. This demonstrates that our quantum protocol is strictly better than classical protocols.
We prove that by communicating $N\ensuremath{-}1$ times a single qubit, instead of $N\ensuremath{-}1$ classical bits, the success probability for solving some N partner communication complexity tasks is strongly enhanced. The superiority, as measured by the quantum-to-classical fidelity ratio, of the quantum scheme grows exponentially with N. We report an experimental implementation of these tasks for N=5. Even without correcting for any inefficiencies of the state-of-the-art setup, our multiparty quantum protocol still outperforms the best classical protocols.