We prove a lower bound on the information leakage of any classical protocol computing the equality function in the simultaneous message passing (SMP) model. Our bound is valid in the finite length regime and is strong enough to demonstrate a quantum advantage in terms of information leakage for practical quantum protocols. We prove our bound by obtaining an improved finite size version of the communication bound due to Babai and Kimmel, relating randomized communication to deterministic communication in the SMP model. We then relate information leakage to randomized communication through a series of reductions. We first provide alternative characterizations for information leakage, allowing us to link it to average length communication while allowing for shared randomness (pairwise, with the referee). A Markov inequality links this with bounded length communication, and a Newman type argument allows us to go from shared to private randomness. The only reduction in which we incur more than a logarithmic additive factor is in the Markov inequality; in particular, our compression method is essentially tight for the SMP model with average length communication.
We prove a lower bound on the information leakage of any classical protocol computing the equality function in the simultaneous message passing (SMP) model. Our bound is valid in the finite length regime and is strong enough to demonstrate a quantum advantage in terms of information leakage for practical quantum protocols. We prove our bound by obtaining an improved finite size version of the communication bound due to Babai and Kimmel, relating randomized communication to deterministic communication in the SMP model. We then relate information leakage to randomized communication through a series of reductions. We first provide alternative characterizations for information leakage, allowing us to link it to average length communication while allowing for shared randomness (pairwise, with the referee). A Markov inequality links this with bounded length communication, and a Newman type argument allows us to go from shared to private randomness. The only reduction in which we incur more than a logarithmic additive factor is in the Markov inequality; in particular, our compression method is essentially tight for the SMP model with average length communication.
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.
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.
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(qc log q) classical bits.Our proofs rely heavily on earlier results due to Scott Aaronson [1,2].In particular, our results imply that quantum-classical protocols need to send Ω( 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 [7].Our results also imply, more generally, that there are no superpolynomial separations between quantumclassical 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.
This paper addresses two problems in the context of two-party communication complexity of functions. First, it concludes the line of research which can be viewed as demonstrating qualitative advantage of quantum communication in the three most common communication “layouts”: two-way interactive communication, one-way communication and simultaneous message passing (SMP). I demonstrate a functional (problem c̅E̅q̅T̅, whose communication complexity is O (log n)2) in the quantum version of the SMP and Ω̃ (√n) in the classical (randomized) version of SMP. Second, this paper contributes to understanding the power of the weakest commonly studied regime of quantum communication-SMP with quantum messages and without shared randomness (the latter restriction can be viewed as a somewhat artificial way of making the quantum model “as weak as possible”). Our function c̅E̅q̅T̅ has an efficient solution in this regime as well, which means that even lacking shared randomness, quantum SMP can be exponentially stronger than its classical counterpart with shared randomness.
In secure multiparty computation (MPC), mutually distrusting users collaborate to compute a function of their private data without revealing any additional information about their data to the other users. While it is known that information theoretically secure MPC is possible among n users having access to private randomness and are pairwise connected by secure, noiseless, and bidirectional links against the collusion of less than n/2 users (in the honest-but-curious model; the threshold is n/3 in the malicious model), relatively little is known about the communication and randomness complexity of secure computation, i.e., the amount of communication and randomness required to compute securely. In this paper, we employ information theoretic techniques to obtain lower bounds on communication and randomness complexity of secure MPC. We restrict ourselves to a concrete interactive setting involving three users under which all functions are securely computable against corruption of individual users in the honest-but-curious model. We derive lower bounds for both the perfect security case (i.e., zero-error and no leakage of information) and asymptotic security (where the probability of error and information leakage vanish as block-length goes to ∞). Our techniques include the use of a data processing inequality for residual information (i.e., the gap between mutual information and Gács-Körner common information), a new information inequality for three-user protocols, and the idea of distribution switching by which lower bounds computed under certain worst case scenarios can be shown to apply for the general case. Our lower bounds are shown to be tight for various functions of interest. In particular, we show concrete functions which have communication-ideal protocols, i.e., which achieve the minimum communication simultaneously on all links in the network. Also, we obtain the first explicit example of a function that incurs a higher communication cost than the input length, in the secure computation model of Feige et al. (26th Annual ACM Symposium on Theory of Computing, 1994), who had shown that such functions exist. We also show that our communication bounds imply tight lower bounds on the amount of randomness required by MPC protocols for many interesting functions.