We consider a variation of the communication complexity scenario, where the parties are supplied with an extra resource: particles in an entangled quantum state. We note that "quantum nonlocality" can be naturally expressed in the language of communication complexity. These are communication complexity problems where the "output" is embodied in the correlations between the outputs of the individual parties. Without entanglement, the parties must communicate to produce the required correlations; whereas, with entanglement, no communication is necessary to produce the correlations. In this sense, nonlocality proofs can also be viewed as communication complexity problems where the presence of quantum entanglement reduces the amount of necessary communication. We show how to transform examples of nonlocality into more traditional communication complexity problems, where the output is explicitly determined by each individual party. The resulting problems require communication with or without entanglement, but the required communication is less when entanglement is available. All these results are a noteworthy contrast to the well-known fact that entanglement cannot be used to actually simulate or compress classical communication between remote parties.
We consider a variation of the multi-party communication complexity scenario where the parties are supplied with an extra resource: particles in an entangled quantum state. We show that, although a prior quantum entanglement cannot be used to simulate a communication channel, it can reduce the communication complexity of functions in some cases. Specifically, we show that, for a particular function among three parties (each of which possesses part of the function's input), a prior quantum entanglement enables them to learn the value of the function with only three bits of communication occurring among the parties, whereas, without quantum entanglement, four bits of communication are necessary. We also show that, for a particular two-party probabilistic communication complexity problem, quantum entanglement results in less communication than is required with only classical random correlations (instead of quantum entanglement). These results are a noteworthy contrast to the well-known fact that quantum entanglement cannot be used to actually simulate communication among remote parties.
Quantum computing resources have been known to provide speed-ups in computational complexity in many algorithms. The impact of these resources in communication, however, has not attracted much attention. We investigate the impact of \nquantum entanglement on communication complexity. We provide a positive result, \nby presenting a class of multi-party communication problems wherein the presence of \na suitable quantum entanglement lowers the classical communication complexity. We \nshow that, in evaluating certains function whose parameters are distributed among \nvarious parties, the presence of prior entanglement can help in reducing the required \ncommunication. We also present an outline of realizing the required entanglement \nthrough optical photon quantum computing. We also suggest the possible impact of \nour results on network information flow problems, by showing an instance of a lower \nbound which can be broken by adding limited power to the communication model.
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.
Quantum theory is, in some sense, “non-classical.” For instance, the behavior of entangled systems (i.e., shared quantum information) under measurements cannot, in general, be explained by shared classical information. With classical communication, on the other hand, both the correlations entanglement leads to as well as quantum channels can be reproduced in principle. Here, crucial questions are whether the required communications is finite; if so, then its exact amount is related to the “degree of non-classicality” of the quantum primitive. We apply information-theoretic results such as the reverse Shannon theorem for determining the required communication in the asymptotic limit. The communication complexity of a quantum channel is the minimal amount of classical communication required for classically simulating the process of preparation, transmission through the channel, and subsequent measurement of a quantum state. At present, only little is known about this quantity. Our generic procedure allows for systematically evaluating the communication complexity of channels in any general probabilistic theory, in particular quantum theory. The procedure is constructive and provides the most efficient classical protocols. We illustrate it by evaluating the communication complexity of sending single qubits over a noiseless quantum channel with some finite sets of quantum states and measurements. As a second application, we determine the classical-communication rate required for the simulation of the behavior under measurements of entangled states. Here, the communication cost can be directly interpreted as the “non-classicality” of the correlation. A particular example is the simulation of non-maximally entangled pure qubit pairs, where we find the required communication rate to behave monotonically with the strength of the entanglement. For different measures of non-locality, such as the number of required non-local (PR) boxes, another behavior had been reported for the single-shot scenario.
This dissertation is motivated by the following fundamental questions: (a) are there any exponential gaps between quantum and classical communication complexities? (b) what is the role of entanglement in assisting quantum communications? (c) how to characterize the nonlocality of quantum operations? We study four specific problems below. 1. The communication complexity of the Hamming Distance problem. The Hamming Distance problem is for two parties to determine whether or not the Hamming distance between two n-bit strings is more than a given threshold. We prove tighter quantum lower bounds in the general two-party, interactive communication model. We also construct an efficient classical protocol in the more restricted Simultaneous Message Passing model, improving previous results. 2. The Log-Equivalence Conjecture. A major open problem in communication complexity is whether or not quantum protocols can be exponentially more efficient than classical ones for computing a total Boolean function in the two-party, interactive model. The answer is believed to be No. Razborov proved this conjecture for the most general class of functions so far. We prove this conjecture for a broader class of functions that we called block-composed functions. Our proof appears to be the first demonstration of the dual approach of the polynomial method in proving new results. 3. Classical simulations of bipartite quantum measurement. We define a new ix concept that measures the nonlocality of bipartite quantum operations. From this measure, we derive an upper bound that shows the limitation of entanglement in reducing communication costs. 4. The maximum tensor norm of bipartite superoperators. We define a maximum tensor norm to quantify the nonlocality of bipartite superoperators. We show that a bipartite physically realizable superoperator is bi-local if and only if its maximum tensor norm is 1. Furthermore, the estimation of the maximum tensor norm can also be used to prove quantum lower bounds on communication complexities.