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.
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.
Computing many instances jointly can reduce communication per instance. We ask whether such savings occur in the simultaneous-message-passing (SMP) model and how they depend on quantum messages and shared resources. For every finite total function f and fixed error 0≤ε<1, we prove that the optimal worst-case communication per instance for fn converges to D∥(f)=log∣Row(f)∣+log∣Col(f)∣, where Row(f) and Col(f) are the sets of distinct rows and columns of the table (f(x,y))x,y. This holds for classical and quantum SMP without shared entanglement, with or without shared randomness. Thus, transmitting row and column indices is asymptotically optimal, even with bounded error, joint computation, and quantum messages. In particular, the exponential advantage of quantum fingerprinting for a single instance of equality without shared randomness disappears in the asymptotic rate. We also prove that the same threshold governs an exponential strong converse: every fixed worst-case communication rate below it forces the probability of computing all n outputs correctly to decay as 2−Ω(n), even on average under a fixed product input distribution. With shared randomness, the optimal expected communication rate is (1−ε)D∥(f). Entanglement shared between each sender and the referee halves both rates; arbitrary tripartite entanglement gives no further reduction. The results extend to a class of total relations and yield one-way characterizations with D∥(f) replaced by log∣Row(f)∣. Our proof reduces SMP to one-way communication and relates successful computation to sampling based on quantum min-entropy; we also give a simpler proof of the key lemma using the pretty-good measurement.
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 study the simultaneous message passing (SMP) model of communication complexity, for the case where one party is quantum and the other is classical. We show that in an SMP protocol that computes some function with the first party sending q qubits and the second sending c classical bits, the quantum message can be replaced by a randomized message of O(qc) classical bits, as well as by a deterministic message of O(q c log q) classical bits. Our proofs rely heavily on earlier results due to Scott Aaronson. In particular, our results imply that quantum-classical protocols need to send Omega(sqrt{n/log n}) bits/qubits to compute Equality on n-bit strings, and hence are not significantly better than classical-classical protocols (and are much worse than quantum-quantum protocols such as quantum fingerprinting). This essentially answers a recent question of Wim van Dam. Our results also imply, more generally, that there are no superpolynomial separations between quantum-classical and classical-classical SMP protocols for functional problems. This contrasts with the situation for relational problems, where exponential gaps between quantum-classical and classical-classical SMP protocols are known. We show that this surprising situation cannot arise in purely classical models: there, an exponential separation for a relational problem can be converted into an exponential separation for a functional problem.
We study the relative power of public randomness and quantum communication in the multiparty Simultaneous Message Passing (SMP) model. By analyzing a total Boolean function and a relational problem, we establish polynomial and exponential separations between classical public-coin protocols and quantum protocols without shared randomness or prior entanglement.
We first introduce XOR Equality, a total Boolean function in which each of k players receives an unrestricted string xj∈{0,1}n, and the referee must decide whether x1⊕⋯⊕xk=0n. For k≥8 and worst-case error at most 1/3, we prove quantum lower bounds of Ω(min{n,k2}) on total communication and Ω(min{n/k,k}) on maximum message length. A classical public-coin protocol uses two bits per player with error at most 1/4. For n=k2 and worst-case error at most 1/3, we prove that quantum protocols require maximum message length Ω(n) qubits, whereas two public-coin bits per player suffice.
We then turn to relations, for which we obtain exponential separations. Specifically, we study Multiparty Index Coordination, a k-player generalization of the two-player relation studied by Gavinsky, Kempe, Regev, and de Wolf (STOC 2006). We prove an unambiguous quantum lower bound of Ω(n1−1/k) on maximum message length, matched by a classical private-coin protocol. For any fixed error ε∈(0,1/8), we also prove a bounded-error quantum lower bound of Ω(n(k−1)/(k+1)) while we show that public-coin protocols solve the relation unambiguously with maximum message length O(logn), giving exponential separations in both regimes. The implicit constants are independent of k, and both quantum lower bounds become linear when k≥clogn for any fixed c>0.
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.
The private simultaneous messages model is a non-interactive version of the multiparty secure computation, which has been intensively studied to examine the communication cost of the secure computation. We consider its quantum counterpart, the private simultaneous quantum messages (PSQM) model, and examine the advantages of quantum communication and prior entanglement of this model. In the PSQM model, k parties P1,…,Pk initially share a common random string (or entangled states in a stronger setting), and they have private classical inputs x1,…,xk. Every Pi generates a quantum message from the private input xi and the shared random string (entangled states), and then sends it to the referee R. Receiving the messages, R computes F(x1,…,xk). Then, R learns nothing except for F(x1,…,xk) as the privacy condition. We obtain the following results for this PSQM model. (1) We demonstrate that the privacy condition inevitably increases the communication cost in the two-party PSQM model as well as in the classical case presented by Applebaum, Holenstein, Mishra, and Shayevitz. In particular, we prove a lower bound (3−o(1))n of the communication complexity in two-party PSQM protocols with a shared random string for random Boolean functions of 2n-bit input, which is larger than the trivial upper bound 2n of the communication complexity without the privacy condition. (2) We demonstrate a factor two gap between the communication complexity of PSQM protocols with shared entangled states and with shared random strings by designing a multiparty PSQM protocol with shared entangled states for a total function that extends the two-party equality function. (3) We demonstrate an exponential gap between the communication complexity of PSQM protocols with shared entangled states and with shared random strings for a two-party partial function.