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 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 prove a direct product theorem for the one-way entanglement-assisted quantum communication complexity of a general relation f ⊆ 𝒳×𝒴×𝒵. For any 0 < ε < δ < 1/2 and any k≥1, we show that Q¹_{1-(1-ε)^{Ω(k/log|𝒵|)}}(f^k) = Ω(k⋅Q¹_{δ}(f)), where Q¹_{ε}(f) represents the one-way entanglement-assisted quantum communication complexity of f with worst-case error ε and f^k 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, Pereszlényi and Yao [Rahul Jain et al., 2014], and under anchored distributions due to Bavarian, Vidick and Yuen [Bavarian et al., 2017], as well as message compression for quantum protocols due to Jain, Radhakrishnan and Sen [Rahul Jain et al., 2005]. 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 𝒳×𝒴 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 f̃ which has an anchored distribution q close to p, such that a protocol that fails with probability at most ε for f̃ under q can be used to give a protocol that fails with probability at most ε + ζ 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, 𝒳×𝒴, 𝒜×ℬ, 𝖵) where q is a distribution on 𝒳×𝒴 anchored on any one side with constant anchoring probability, then ω^*(G^k) = (1 - (1-ω^*(G))⁵) ^{Ω(k/(log(|𝒜|⋅|ℬ|)))} where ω^*(G) represents the entangled value of the game G. This is a generalization of the result of [Bavarian et al., 2017], 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 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.
Quantum query complexity enjoys a variety of pleasing joint computation properties: for example, a composition theorem asserting Q(f∘g)=Θ(Q(f)Q(g)) for all Boolean functions f and g; a direct sum theorem asserting that computing k copies of a function (or search problem) costs Ω(k) times as much as the cost of computing one copy; and a direct product theorem asserting that for Boolean functions, even succeeding at the direct sum problem with exponentially small probability still requires Ω(k) times the cost of computing one copy to bounded error.
However, all of these results are strictly for worst-case quantum query complexity. For example, if we have a fixed distribution μ over inputs, the direct sum theorem says nothing about the quantum query complexity of computing k copies of f when the input comes from the product distribution μk instead of being worst-case. (Note that while a standard Yao-type minimax theorem guarantees a hard distribution for the direct sum problem, there's no guarantee that this hard distribution is a product distribution.) A similar problem occurs for the direct product theorem and the composition theorem: none of these results respect distributions.
In this work, we give distributional joint computation lower bounds for the composition, direct sum, and direct product problems. Along the way, we introduce some new tools for handling quantum query lower bounds, including (a) a new ``multiplicative'' variant of the γ2 norm (which we use in place of the multiplicative adversary method for proving the direct product theorem), and (b) a new ``Shaltiel-free'' measure of quantum query complexity, which we show characterizes the composition behavior of distributional quantum query complexity and satisfies pleasing properties.
We give a direct product theorem for the entanglement-assisted interactive quantum communication complexity in terms of the quantum partition bound for product distributions. The quantum partition or efficiency bound is a lower bound on communication complexity, a non-distributional version of which was introduced by Laplante, Lerays and Roland (2012). For a two-input boolean function, the best result for interactive quantum communication complexity known previously was due to Sherstov (2018), who showed a direct product theorem in terms of the generalized discrepancy. While there is no direct relationship between the maximum distributional quantum partition bound for product distributions, and the generalized discrepancy method, unlike Sherstov's result, our result works for two-input functions or relations whose outputs are non-boolean as well. As an application of our result, we show that it is possible to do device-independent quantum key distribution (DIQKD) without the assumption that devices do not leak any information after inputs are provided to them. We analyze the DIQKD protocol given by Jain, Miller and Shi (2020), and show that when the protocol is carried out with devices that are compatible with several copies of the Magic Square game, it is possible to extract a linear (in the number of copies of the game) amount of key from it, even in the presence of a linear amount of leakage. Our security proof is parallel, i.e., the honest parties can enter all their inputs into their devices at once, and works for a leakage model that is arbitrarily interactive, i.e., the devices of the honest parties Alice and Bob can exchange information with each other and with the eavesdropper Eve in any number of rounds, as long as the total number of bits or qubits communicated is bounded.
Abstract. We give a direct product theorem for the entanglement-assisted interactive quantum communication complexity of an [Formula: see text]-player predicate [Formula: see text]. In particular, we show that for a distribution [Formula: see text] that is product across the input sets of the [Formula: see text] players, the success probability of any entanglement-assisted quantum communication protocol for computing [Formula: see text] copies of [Formula: see text], whose communication is [Formula: see text], goes down exponentially in [Formula: see text]. Here [Formula: see text] is a distributional version of the quantum efficiency or partition bound introduced in [S. Laplante, V. Lerays, and J. Roland, Classical and quantum partition bound and detector inefficiency, in Automata, Languages, and Programming, Springer, Berlin, Heidelberg, 2012, pp. 617–628], which is a lower bound on the distributional quantum communication complexity of computing a single copy of [Formula: see text] with respect to [Formula: see text]. Applying our direct product theorem for small communication, and techniques related to [Formula: see text], we show that it is possible to do device-independent (DI) quantum cryptography without the assumption that devices do not leak any information. We analyze parallel and sequential versions of the DI quantum key distribution protocol given in [R. Jain, C. A. Miller, and Y. Shi [ IEEE Trans. Inform. Theory, 66 (2020), pp. 5567–5584], and show that it is possible to extract [Formula: see text] bits of key from it, even in the presence of [Formula: see text] bits of leakage. Finally, we show that proofs of quantumness with two entangled provers are resistant to leakage, i.e., classical players who communicate [Formula: see text] bits with each other cannot convince the verifier that they share entanglement.
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.