We prove a direct product theorem for the one-way entanglement-assisted quantum communication complexity of a general relation $f\subseteq\mathcal{X}\times\mathcal{Y}\times\mathcal{Z}$. For any $\varepsilon, ζ> 0$ and any $k\geq1$, we show that \[ \mathrm{Q}^1_{1-(1-\varepsilon)^{Ω(ζ^6k/\log|\mathcal{Z}|)}}(f^k) = Ω\left(k\left(ζ^5\cdot\mathrm{Q}^1_{\varepsilon + 12ζ}(f) - \log\log(1/ζ)\right)\right),\] where $\mathrm{Q}^1_{\varepsilon}(f)$ represents the one-way entanglement-assisted quantum communication complexity of $f$ with worst-case error $\varepsilon$ and $f^k$ 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, \mathcal{X}\times\mathcal{Y}, \mathcal{A}\times\mathcal{B}, \mathsf{V})$ where $q$ is a distribution on $\mathcal{X}\times\mathcal{Y}$ anchored on any one side with anchoring probability $ζ$, then \[ ω^*(G^k) = \left(1 - (1-ω^*(G))^5\right)^{Ω\left(\frac{ζ^2 k}{\log(|\mathcal{A}|\cdot|\mathcal{B}|)}\right)}\] 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 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 [ \mathrm{Q}^1_{1-(1-\varepsilon)^{Ω(ζ^6k/\log|\mathcal{Z}|)}}(f^k) = Ω\left(k\left(ζ^5\cdot\mathrm{Q}^1_{\varepsilon + 12ζ}(f) - \log\log(1/ζ)\right)\right),] 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 [ ω^(G^k) = \left(1 - (1-ω^(G))^5\right)^{Ω\left(\frac{ζ^2 k}{\log(|\mathcal{A}|\cdot|\mathcal{B}|)}\right)}] 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 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 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.
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.
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.
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 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.