We present relation problems whose input size is $n$ such that they can be solved with no communication for entanglement-assisted quantum communication models, but require $Ω(n)$ qubit communication for $2$-way quantum communication models without prior shared entanglement. This is the maximum separation of quantum communication complexity with and without shared entanglement. To our knowledge, our result even shows the first lower bound on quantum communication complexity without shared entanglement when the upper bound of entanglement-assisted quantum communication models is zero. Our result refutes a quantum analog of Newman's theorem. The problem we consider is parallel repetition of any non-local game which has a perfect quantum strategy and no perfect classical strategy, and for which a parallel repetition theorem holds with exponential decay.
We present relation problems whose input size is n such that they can be solved with no communication for entanglement-assisted quantum communication models, but require Ω(n) qubit communication for 2-way quantum communication models without prior shared entanglement. This is the maximum separation of quantum communication complexity with and without shared entanglement. To our knowledge, our result even shows the first lower bound on quantum communication complexity without shared entanglement when the upper bound of entanglement-assisted quantum communication models is zero. Our result refutes a quantum analog of Newman's theorem. The problem we consider is parallel repetition of any non-local game which has a perfect quantum strategy and no perfect classical strategy, and for which a parallel repetition theorem holds with exponential decay.
We study the impact of noise on the theories of quantum nonlocality and entanglement-assisted communication complexity. We consider non-local games and entanglement-assisted communication complexity in a model where Alice and Bob may share arbitrarily many noisy EPR pairs. We study four noise models: depolarizing noise, unital noise, biased reset noise, and erasure noise. Our results are as follows:
1. We upper bound the value of the CHSH game under all these noise models in terms of the noise parameter, without any assumptions on the measurements used in the strategy.
2. We prove a parallel repetition theorem for general non-local games under all noise models except biased reset noise; we prove an improved parallel repetition theorem for unique games. Our parallel repetition rate is smaller than the quantum parallel repetition rate for CHSH in a nontrivial noise regime.
3. Using our unique-game parallel repetition theorem and a relation defined by the CHSH game, we prove a separation between communication complexity with noisy vs noiseless entanglement. This implies an Ω(n) two-way communication lower bound for distilling n EPR pairs from noisy EPR pairs, in the same nontrivial noise regime.
4. We show that any interactive entanglement-assisted communication protocol can be simulated by an SMP communication protocol with noisy shared randomness, with an exponential blowup in communication. This generalizes a known result on the simulation of noiseless shared randomness with noisy shared randomness.
5. We show a polynomial lower bound on the number of copies of noisy EPR pairs required to compute the Equality function with constant communication, under all four noise models. The previous result gives a matching upper bound, and moreover, this answers an open question in the literature on whether logarithmically many noisy shared bits suffice for communication.
We prove a direct product theorem for the one-way entanglement-assisted quantum communication complexity of a general relation f⊆X×Y×Z. For any 0 k ≥ 1, we show that [EQUATION] where Q1e(f) represents the one-way entanglement-assisted quantum communication complexity of f with worst-case error e and fk denotes k parallel instances of f. As far as we are aware, this is the first direct product theorem for the quantum communication complexity of a general relation - direct sum theorems were previously known for one-way quantum protocols for general relations, while direct product theorems were only known for special cases. Our techniques are inspired by the parallel repetition theorems for the entangled value of two-player non-local games, under product distributions due to Jain, Pereszlenyi and Yao [24], and under anchored distributions due to Bavarian, Vidick and Yuen [4], as well as message compression for quantum protocols due to Jain, Radhakrishnan and Sen [29]. In particular, we show that a direct product theorem holds for the distributional one-way quantum communication complexity of f under any distribution q on X × Y that is anchored on one side, i.e., there exists a y* such that q(y*) is constant and q(x\y*) = q(x) for all x. This allows us to show a direct product theorem for general distributions, since for any relation f and any distribution p on its inputs, we can define a modified relation [EQUATION] which has an anchored distribution q close to p, such that a protocol that fails with probability at most e for [EQUATION] under q can be used to give a protocol that fails with probability at most e + ζ for f under p. Our techniques also work for entangled non-local games which have input distributions anchored on any one side, i.e., either there exists a y* as previously specified, or there exists an x* such that q(x*) is constant and q(y\x*) = q(y) for all y. In particular, we show that for any game G = (q,X×Y, A×B, V) where q is a distribution on X × Y anchored on any one side with constant anchoring probability, then [EQUATION] where ω* (G) represents the entangled value of the game G. This is a generalization of the result of [4], who proved a parallel repetition theorem for games anchored on both sides, i.e., where both a special x* and a special y* exist, and potentially a simplification of their proof.
We study the complexity of quantum decomposable randomized encodings (QDRE). We establish a bi-directional connection between the QDRE model and the communication complexity model of quantum private simultaneous message protocols (QPSM), where classical communication is free, and quantum communication is the primary complexity measure. We show the following upper and lower bounds. (1) For every quantum channel mapping n to m qubits, we give a QPSM protocol with quantum communication m, using exponential pre-shared entanglement. In particular, constant-output channels have O(1) quantum communication, and classical-output channels require no quantum communication. (2) With O(n) pre-shared entanglement, every one-qubit-output channel has an O(n)-quantum-communication QPSM protocol. Conversely, there exists a channel and a constant c>0 for which any protocol with at most cn pre-shared entanglement requires Ω(n) quantum communication. (3) In contrast, we identify a structured class of quantum channels, Clifford-induced channels, for which there exist QPSM protocols with O(n) pre-shared entangled qubits and only O(1) quantum communication complexity. Through our connection, we obtain analogous upper and lower bounds on the quantum encoding size of QDRE. Our results show that the amount of pre-shared entanglement plays a central role in quantum encoding size and quantum communication complexity.
A longstanding question in quantum communication complexity is whether some task can be accomplished with a small amount of communication in the presence of entanglement, yet require much more quantum communication in the absence of entanglement. Separations of this nature were previously known for relational problems and, in the simultaneous message passing model, for partial functions. But it has remained unresolved whether any such separation exists for a total Boolean function. We resolve this question with an exponential separation in the one-way setting: we exhibit a family of total Boolean functions fn:{0,1}n×{0,1}n→{0,1} that can be computed with O(logn) bits of one-way classical communication given prior entanglement, but that require Ω(n1/3) qubits of one-way quantum communication without entanglement. Our function is a special case of the subgroup membership problem, first studied in the communication setting by Aaronson, Le Gall, Russell, and Tani.
We prove a direct product theorem for the one-way entanglement-assisted quantum communication complexity of a general relation f⊆X×Y×Z. For any ε,ζ>0 and any k≥1, we show that Q1−(1−ε)Ω(ζ6k/log∣Z∣)1(fk)=Ω(k(ζ5⋅Qε+12ζ1(f)−loglog(1/ζ))), where Qε1(f) represents the one-way entanglement-assisted quantum communication complexity of f with worst-case error ε and fk denotes k parallel instances of f. As far as we are aware, this is the first direct product theorem for quantum communication. Our techniques are inspired by the parallel repetition theorems for the entangled value of two-player non-local games, under product distributions due to Jain, Pereszlényi and Yao, and under anchored distributions due to Bavarian, Vidick and Yuen, as well as message-compression for quantum protocols due to Jain, Radhakrishnan and Sen. Our techniques also work for entangled non-local games which have input distributions anchored on any one side. In particular, we show that for any game G=(q,X×Y,A×B,V) where q is a distribution on X×Y anchored on any one side with anchoring probability ζ, then ω∗(Gk)=(1−(1−ω∗(G))5)Ω(log(∣A∣⋅∣B∣)ζ2k) where ω∗(G) represents the entangled value of the game G. This is a generalization of the result of Bavarian, Vidick and Yuen, who proved a parallel repetition theorem for games anchored on both sides, and potentially a simplification of their proof.
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.