We show optimal Direct Sum result for the one-way entanglement-assisted quantum communication complexity for any relation f subset of X x Y x Z. We show: Q^{1,pub}(f^m) = Omega(m Q^{1,pub}(f)), where Q^{1,pub}(f), represents the one-way entanglement-assisted quantum communication complexity of f with error at most 1/3 and f^m represents m-copies of f. Similarly for the one-way public-coin classical communication complexity we show: R^{1,pub}(f^m) = Omega(m R^{1,pub}(f)), where R^{1,pub}(f), represents the one-way public-coin classical communication complexity of f with error at most 1/3. We show similar optimal Direct Sum results for the Simultaneous Message Passing quantum and classical models. For two-way protocols we present optimal Privacy Trade-off results leading to a Weak Direct Sum result for such protocols. We show our Direct Sum and Privacy Trade-off results via message compression arguments which also imply a new round elimination lemma in quantum communication. This allows us to extend classical lower bounds on the cell probe complexity of some data structure problems, e.g. Approximate Nearest Neighbor Searching on the Hamming cube {0,1}^n and Predecessor Search to the quantum setting. In a separate result we show that Newman's technique of reducing the number of public-coins in a classical protocol cannot be lifted to the quantum setting. We do this by defining a general notion of black-box reduction of prior entanglement that subsumes Newman's technique. We prove that such a black-box reduction is impossible for quantum protocols. In the final result in the theme of message compression, we provide an upper bound on the problem of Exact Remote State Preparation.
We show optimal Direct Sum result for the one-way entanglement-assisted quantum communication complexity for any relation f subset of X x Y x Z. We show: Q^{1,pub}(f^m) = Omega(m Q^{1,pub}(f)), where Q^{1,pub}(f), represents the one-way entanglement-assisted quantum communication complexity of f with error at most 1/3 and f^m represents m-copies of f. Similarly for the one-way public-coin classical communication complexity we show: R^{1,pub}(f^m) = Omega(m R^{1,pub}(f)), where R^{1,pub}(f), represents the one-way public-coin classical communication complexity of f with error at most 1/3. We show similar optimal Direct Sum results for the Simultaneous Message Passing quantum and classical models. For two-way protocols we present optimal Privacy Trade-off results leading to a Weak Direct Sum result for such protocols. We show our Direct Sum and Privacy Trade-off results via message compression arguments which also imply a new round elimination lemma in quantum communication. This allows us to extend classical lower bounds on the cell probe complexity of some data structure problems, e.g. Approximate Nearest Neighbor Searching on the Hamming cube {0,1}^n and Predecessor Search to the quantum setting. In a separate result we show that Newman's technique of reducing the number of public-coins in a classical protocol cannot be lifted to the quantum setting. We do this by defining a general notion of black-box reduction of prior entanglement that subsumes Newman's technique. We prove that such a black-box reduction is impossible for quantum protocols. In the final result in the theme of message compression, we provide an upper bound on the problem of Exact Remote State Preparation.
We show optimal Direct Sum result for the one-way entanglement-assisted quantum com- munication complexity for any relation fX × Y × Z. We show: Q 1,pub (f ⊕m ) = (m · Q 1,pub (f)), where Q 1,pub (f), represents the one-way entanglement-assisted quantum communication complexity of f with error at most 1/3 and f ⊕m represents m-copies of f. Similarly for the one-way public-coin classical communication complexity we show: R 1,pub (f ⊕m ) = (m · R 1,pub (f)), where R 1,pub (f), represents the one-way public-coin classical communication complexity of f with error at most 1/3. We show similar optimal Direct Sum results for the Simultaneous Message Passing (SMP) quantum and classical models. For two-party two-way protocols we present optimal Privacy Trade-off results leading to a Weak Direct Sum result for such protocols. We show our Direct Sum and Privacy Trade-off results via message compression arguments. These arguments also imply a new round elimination lemma in quantum communication, which allows us to extend classical lower bounds on the cell probe complexity of some data structure problems, e.g. Approximate Nearest Neighbor Searching (ANN) on the Hamming cube {0,1} n and Predecessor Search to the quantum setting. In a separate result we show that Newman's (New91) technique of reducing the number of public-coins in a classical protocol cannot be lifted to the quantum setting. We do this by defining a general notion of black-box reduction of prior entanglement that subsumes Newman's technique. We prove that such a black-box reduction is impossible for quantum protocols by exhibiting a particular one-round quantum protocol for the Equality function where the black-box technique fails to reduce the amount of prior entanglement by more than a constant factor.
Consider a two-party quantum communication protocol for computing some function f : {0, 1}/sup n/ /spl times/ {0, 1}/sup n/ /spl rarr/ Z. We show that the first message of P can be compressed to 0(k) classical bits using prior entanglement if it carries at most k bits of information about the sender's input. This implies a general direct sum result for one-round and simultaneous quantum protocols. It also implies a new round elimination lemma in quantum communication, which allows us to extend recent classical lower bounds on the cell probe complexity of some data structure problems, e.g. approximate nearest neighbor searching on the Hamming cube {0, 1}/sup n/, to the quantum setting. We then show an optimal tradeoff between the privacy losses of Alice and Bob in computing f in terms of the one-round quantum communication complexity of f with prior entanglement. This tradeoff is independent of the number of rounds of communication. The above message compression and privacy tradeoff results use a lot of qubits of prior entanglement, leading one to wonder how much prior entanglement is really required by a quantum protocol. We show that Newman's [1991] technique of reducing the number of public coins in a classical protocol cannot be lifted to the quantum setting. We do this by defining a general notion of black-box reduction of prior entanglement that subsumes Newman's technique. Intuitively, a black-box reduction does not change the unitary transforms of Alice and Bob; it only decreases the amount of entanglement of the prior entangled state. We prove that such a black-box reduction is impossible for quantum protocols by exhibiting a particular one-round quantum protocol for the equality function where the black-box technique fails to reduce the amount of prior entanglement by more than a constant factor.
Consider the following Simultaneous Message Passing (SMP) model for computing a relation f subset of X x Y x Z. In this model Alice, on input x in X and Bob, on input y in Y, send one message each to a third party Referee who then outputs a z in Z such that (x,y,z) in f. We first show optimal 'Direct sum' results for all relations f in this model, both in the quantum and classical settings, in the situation where we allow shared resources (shared entanglement in quantum protocols and public coins in classical protocols) between Alice and Referee and Bob and Referee and no shared resource between Alice and Bob. This implies that, in this model, the communication required to compute k simultaneous instances of f, with constant success overall, is at least k-times the communication required to compute one instance with constant success. This in particular implies an earlier Direct sum result, shown by Chakrabarti, Shi, Wirth and Yao, 2001, for the Equality function (and a class of other so-called robust functions), in the classical smp model with no shared resources between any parties. Furthermore we investigate the gap between the smp model and the one-way model in communication complexity and exhibit a partial function that is exponentially more expensive in the former if quantum communication with entanglement is allowed, compared to the latter even in the deterministic case.
We prove a direct sum theorem for bounded round entanglement-assisted quantum communication complexity. To do so, we use the fully quantum definition for information cost and complexity that we recently introduced, and use both the fact that information is a lower bound on the communication, and the fact that a direct sum property holds for quantum information complexity. We then give a protocol for compressing a single copy of a protocol down to its quantum information cost, up to terms depending on the number of rounds and the allowed increase in error. Two important tools to derive this protocol are a smooth conditional min-entropy bound for a one-shot quantum state redistribution protocol, and the quantum substate theorem of Jain, Radhakrishnan and Sen (FOCS'02) to transform this bound into a von Neumann conditional entropy bound. This result further establishes the newly introduced notions of quantum information cost and complexity as the correct quantum generalisations of the classical ones in the standard communication complexity setting. Finding such a quantum generalization of information complexity was one of the open problem recently raised by Braverman (STOC'12).
Consider the following simultaneous message passing (SMP) model for computing a relation f sube X times Y times Z. In this model Alice, on input x isin X and Bob, on input y isin Y, send one message each to a third party Referee who then outputs a z isin Z such that (x, y, z) isin f. We first show optimal direct sum results for all relations / in this model, both in the quantum and classical settings, in the situation where we allow shared resources (shared entanglement in quantum protocols and public coins in classical protocols) between Alice and Referee and Bob and Referee and no shared resource between Alice and Bob. This implies that, in this model, the communication required to compute k simultaneous instances of /, with constant success overall, is at least k-times the communication required to compute one instance with constant success. This in particular implies an earlier direct sum result, shown by Chakrabarti, Shi, Wirth and Yao [CSWY01] for the equality function (and a class of other so-called robust functions), in the classical SMP model with no shared resources between any parties. Furthermore we investigate the gap between the SMP model and the one-way model in communication complexity and exhibit a partial function that is exponentially more expensive in the former if quantum communication with entanglement is allowed, compared to the latter even in the deterministic case.
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.