We investigate the randomized and quantum communication complexities of the well-studied Equality function with small error probability ε, getting the optimal constant factors in the leading terms in various different models. The following are our results in the randomized model: - We give a general technique to convert public-coin protocols to private-coin protocols by incurring a small multiplicative error at a small additive cost. This is an improvement over Newman’s theorem [Inf. Proc. Let.'91] in the dependence on the error parameter. - As a consequence we obtain a (log(n/ε²) + 4)-cost private-coin communication protocol that computes the n-bit Equality function, to error ε. This improves upon the log(n/ε³) + O(1) upper bound implied by Newman’s theorem, and matches the best known lower bound, which follows from Alon [Comb. Prob. Comput.'09], up to an additive log log(1/ε) + O(1). The following are our results in various quantum models: - We exhibit a one-way protocol with log(n/ε) + 4 qubits of communication for the n-bit Equality function, to error ε, that uses only pure states. This bound was implicitly already shown by Nayak [PhD thesis'99]. - We give a near-matching lower bound: any ε-error one-way protocol for n-bit Equality that uses only pure states communicates at least log(n/ε) - log log(1/ε) - O(1) qubits. - We exhibit a one-way protocol with log(√n/ε) + 3 qubits of communication that uses mixed states. This is tight up to additive log log(1/ε) + O(1), which follows from Alon’s result. - We exhibit a one-way entanglement-assisted protocol achieving error probability ε with ⌈log(1/ε)⌉ + 1 classical bits of communication and ⌈log(√n/ε)⌉ + 4 shared EPR-pairs between Alice and Bob. This matches the communication cost of the classical public coin protocol achieving the same error probability while improving upon the amount of prior entanglement that is needed for this protocol, which is ⌈log(n/ε)⌉ + O(1) shared EPR-pairs. Our upper bounds also yield upper bounds on the approximate rank, approximate nonnegative-rank, and approximate psd-rank of the Identity matrix. As a consequence we also obtain improved upper bounds on these measures for a function that was recently used to refute the randomized and quantum versions of the log-rank conjecture (Chattopadhyay, Mande and Sherif [J. ACM'20], Sinha and de Wolf [FOCS'19], Anshu, Boddu and Touchette [FOCS'19]).
We investigate the randomized and quantum communication complexities of the well-studied Equality function with small error probability ε, getting the optimal constant factors in the leading terms in various different models. The following are our results in the randomized model: - We give a general technique to convert public-coin protocols to private-coin protocols by incurring a small multiplicative error at a small additive cost. This is an improvement over Newman’s theorem [Inf. Proc. Let.'91] in the dependence on the error parameter. - As a consequence we obtain a (log(n/ε²) + 4)-cost private-coin communication protocol that computes the n-bit Equality function, to error ε. This improves upon the log(n/ε³) + O(1) upper bound implied by Newman’s theorem, and matches the best known lower bound, which follows from Alon [Comb. Prob. Comput.'09], up to an additive log log(1/ε) + O(1). The following are our results in various quantum models: - We exhibit a one-way protocol with log(n/ε) + 4 qubits of communication for the n-bit Equality function, to error ε, that uses only pure states. This bound was implicitly already shown by Nayak [PhD thesis'99]. - We give a near-matching lower bound: any ε-error one-way protocol for n-bit Equality that uses only pure states communicates at least log(n/ε) - log log(1/ε) - O(1) qubits. - We exhibit a one-way protocol with log(√n/ε) + 3 qubits of communication that uses mixed states. This is tight up to additive log log(1/ε) + O(1), which follows from Alon’s result. - We exhibit a one-way entanglement-assisted protocol achieving error probability ε with ⌈log(1/ε)⌉ + 1 classical bits of communication and ⌈log(√n/ε)⌉ + 4 shared EPR-pairs between Alice and Bob. This matches the communication cost of the classical public coin protocol achieving the same error probability while improving upon the amount of prior entanglement that is needed for this protocol, which is ⌈log(n/ε)⌉ + O(1) shared EPR-pairs. Our upper bounds also yield upper bounds on the approximate rank, approximate nonnegative-rank, and approximate psd-rank of the Identity matrix. As a consequence we also obtain improved upper bounds on these measures for a function that was recently used to refute the randomized and quantum versions of the log-rank conjecture (Chattopadhyay, Mande and Sherif [J. ACM'20], Sinha and de Wolf [FOCS'19], Anshu, Boddu and Touchette [FOCS'19]).
We investigate the randomized and quantum communication complexities of the well-studied Equality function with small error probability ε, getting optimal constant factors in the leading terms in a number of different models. In the randomized model, 1) we give a general technique to convert public-coin protocols to private-coin protocols by incurring a small multiplicative error, at a small additive cost. This is an improvement over Newman's theorem [Inf. Proc. Let.'91] in the dependence on the error parameter. 2) Using this we obtain a (log(n/ε2)+4)-cost private-coin communication protocol that computes the n-bit Equality function, to error ε. This improves upon the log(n/ε3)+O(1) upper bound implied by Newman's theorem, and matches the best known lower bound, which follows from Alon [Comb. Prob. Comput.'09], up to an additive loglog(1/ε)+O(1). In the quantum model, 1) we exhibit a one-way protocol of cost log(n/ε)+4, that uses only pure states and computes the n-bit Equality function to error ε. This bound was implicitly already shown by Nayak [PhD thesis'99]. 2) We show that any ε-error one-way protocol for n-bit Equality that uses only pure states communicates at least log(n/ε)−loglog(1/ε)−O(1) qubits. 3) We exhibit a one-way protocol of cost log(n/ε)+3, that uses mixed states and computes the n-bit Equality function to error ε. This is also tight up to an additive loglog(1/ε)+O(1), which follows from Alon's result. 4) We study the number of EPR pairs required to be shared in an entanglement-assisted one-way protocol. Our upper bounds also yield upper bounds on the approximate rank and related measures of the Identity matrix.
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 investigate the randomized and quantum communication complexities of the well-studied Equality function with small error probability ϵ, getting the optimal constant factors in the leading terms in a number of different models.
In the randomized model,
1) we give a general technique to convert public-coin protocols to private-coin protocols by incurring a small multiplicative error, at a small additive cost. This is an improvement over Newman's theorem [Inf. Proc. Let.'91] in the dependence on the error parameter.
2) Using this we obtain a (log(n/ϵ2)+4)-cost private-coin communication protocol that computes the n-bit Equality function, to error ϵ. This improves upon the log(n/ϵ3)+O(1) upper bound implied by Newman's theorem, and matches the best known lower bound, which follows from Alon [Comb. Prob. Comput.'09], up to an additive loglog(1/ϵ)+O(1).
In the quantum model,
1) we exhibit a one-way protocol of cost log(n/ϵ)+4, that uses only pure states and computes the n-bit Equality function to error ϵ. This bound was implicitly already shown by Nayak [PhD thesis'99].
2) We show that any ϵ-error one-way protocol for n-bit Equality that uses only pure states communicates at least log(n/ϵ)−loglog(1/ϵ)−O(1) qubits.
3) We exhibit a one-way protocol of cost log(n/ϵ)+3, that uses mixed states and computes the n-bit Equality function to error ϵ. This is also tight up to an additive loglog(1/ϵ)+O(1), which follows from Alon's result.
Our upper bounds also yield upper bounds on the approximate rank and related measures of the Identity matrix. This also implies improved upper bounds on these measures for the distributed SINK function, which was recently used to refute the randomized and quantum versions of the log-rank conjecture.
Private simultaneous quantum messages (PSQM) provide a minimal model of noninteractive secure multiparty quantum computation, yet their communication complexity for concrete functions remains poorly understood. We show that familiar total functions already exhibit both genuine quantum advantages and strong structural limitations. For three-party equality on n-bit inputs, which determines whether the players' n-bit strings are identical, we construct an entanglement-assisted protocol with asymptotic communication (1.633…)n qubits, whereas every perfectly correct protocol without prior entanglement requires at least 3n qubits. For three-bit majority, one shared GHZ state and one transmitted qubit per player suffice for perfect correctness and perfect privacy, reducing the communication from the optimal classical cost of six bits to three qubits. Three-bit AND behaves differently. No perfectly correct and perfectly private protocol exists when the players share an arbitrary three-qubit state, apply arbitrary local unitary encodings, and transmit one qubit each. However, increasing the local dimension overcomes this obstruction: one shared three-qutrit GHZ state and one transmitted qutrit per player yield a one-shot protocol with total communication 3log23. Together with the six-bit classical lower bound, this gives a strict quantum communication advantage. More generally, for every k≥3, we construct a perfectly correct and perfectly private one-shot protocol for k-bit AND using one qudit of dimension at most k per player, and hence at most klog2k qubits in total.
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
We study the following task: Alice is given a classical description of a rank-k projector P on Cd, and Alice and Bob want to prepare the quantum state P/k on Bob's side using shared entanglement and classical communication. The general form of this task is known as remote state preparation (RSP). We give nearly-matching lower and upper bounds for the entanglement cost and communication cost for RSP of the states P/k. Ours are the first nearly matching upper and lower bounds for RSP of mixed states, and in the special case of pure states, our lower bound outperforms the best previously known lower bound. Our results show that any pure entangled state that can be used to do RSP of these states with o(d) bits of communication, can distill logd ebits of entanglement, and conversely, any state that can distill logd ebits of entanglement can be used to do RSP of these states efficiently. As applications of our results, we rederive a previously-known incompressibility result for states of the form P/k, and give a new entanglement-assisted communication protocol for the equality function that uses 21logn+O(1) many ebits, and O(1) communication.