Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2106.04299 · SIAM Journal on Computing

A Direct Product Theorem for Quantum Communication Complexity with Applications to Device-Independent Cryptography

Rahul Jain, Srijita Kundu

Published Aug 7, 2025• 11 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1137/23m1549353

Related papers

A direct product theorem for quantum communication complexity with applications to device-independent QKD

Rahul Jain, Srijita Kundu

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.

Annual Symposium on Foundations of Computer Science•Feb 1, 2022•14 citations

A Direct Product Theorem for One-Way Quantum Communication.

Rahul Jain, Srijita Kundu

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.

Electronic colloquium on computational complexity•Jan 1, 2020•0 citations

A Direct Product Theorem for One-Way Quantum Communication

Rahul Jain, Srijita Kundu

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.

arXiv:2008.08963•Leibniz international proceedings in informatics•Aug 20, 2020•7 citations

Communication Complexity of Entanglement-Assisted Multi-Party Computation

Ruoyu Meng, Aditya Ramamoorthy

We consider a quantum and a classical version of a multi-party function computation problem with n players, where players 2,…,n need to communicate appropriate information to player 1 so that a “generalized” inner product function with an appropriate promise can be calculated. In the quantum version of the protocol, the players have access to entangled qudits but the communication is still classical. The communication complexity of a given protocol is the total number of classical bits that need to be communicated. When n is prime, and for our chosen function, we exhibit a quantum protocol (with complexity (n−1)(logn) bits) and a classical protocol (with complexity ((n−1)2(logn2) bits)). Furthermore, we present an integer linear programming formulation for determining a lower bound on the classical communication complexity. This demonstrates that our quantum protocol is strictly better than classical protocols.

arXiv:2305.04435•Entropy•Oct 23, 2024•1 citation

Quantum Communication Complexity of Distributed Set Joins

Stacey Jeffery, François Le Gall

Computing set joins of two inputs is a common task in database theory. Recently, Van Gucht, Williams, Woodruff and Zhang [PODS 2015] considered the complexity of such problems in the natural model of (classical) two-party communication complexity and obtained tight bounds for the complexity of several important distributed set joins. In this paper we initiate the study of the *quantum* communication complexity of distributed set joins. We design a quantum protocol for distributed Boolean matrix multiplication, which corresponds to computing the composition join of two databases, showing that the product of two $n\times n$ Boolean matrices, each owned by one of two respective parties, can be computed with $\widetilde{O}(\sqrt{n}\ell^{3/4})$ qubits of communication, where $\ell$ denotes the number of non-zero entries of the product. Since Van Gucht et al. showed that the classical communication complexity of this problem is $\widetildeΘ(n\sqrt{\ell})$, our quantum algorithm outperforms classical protocols whenever the output matrix is sparse. We also show a quantum lower bound and a matching classical upper bound on the communication complexity of distributed matrix multiplication over $\mathbb{F}_2$. Besides their applications to database theory, the communication complexity of set joins is interesting due to its connections to direct product theorems in communication complexity. In this work we also introduce a notion of *all-pairs* product theorem, and relate this notion to standard direct product theorems in communication complexity.

arXiv:1608.06617•Leibniz international proceedings in informatics•Jan 1, 2016•0 citations

A Direct Product Theorem for the Two-Party Bounded-Round Public-Coin Communication Complexity

Rahul Jain, Attila Pereszlényi, Penghui Yao

A strong direct product theorem for a problem in a given model of computation states that, in order to compute k instances of the problem, if we provide resource which is less than k times the resource required for computing one instance of the problem with constant success probability, then the probability of correctly computing all the k instances together, is exponentially small in k. In this paper, we consider the model of two-party bounded-round public-coin randomized communication complexity. We show a direct product theorem for the communication complexity of any relation in this model. In particular, our result implies a strong direct product theorem for the two-party constant-message public-coin randomized communication complexity of all relations. As an immediate application of our result, we get a strong direct product theorem for the pointer chasing problem. This problem has been well studied for understanding round v/s communication trade-offs in both classical and quantum communication protocols. Our result generalizes the result of Jain [2011] which can be regarded as the special case when t=1. Our result can be considered as an important progress towards settling the strong direct product conjecture for the two-party public-coin communication complexity, a major open question in this area. We show our result using information theoretic arguments. Our arguments and techniques build on the ones used in Jain~\cite{Jain:2011}. %, where a strong direct product theorem for the %two-party one-way public-coin communication complexity of all %relations is shown (that is the special case of our result when $t=1$). One key tool used in our work and also in Jain~\cite{Jain:2011} is a message compression technique due to Braver man and Rao~\cite{Braverman2011}, who used it to show a {\em direct sum} theorem in the same model of communication complexity as considered by us. Another important tool that we use is a correlated sampling protocol, which for example, has been used in Holenstein~\cite{Holenstein2007} for proving a parallel repetition theorem for two-prover games.

Annual Symposium on Foundations of Computer Science•Oct 1, 2012•33 citations
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 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.
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×Zf\subseteq\mathcal{X}\times\mathcal{Y}\times\mathcal{Z}f⊆X×Y×Z. For any ε,ζ>0\varepsilon, ζ> 0ε,ζ>0 and any k≥1k\geq1k≥1, we show that Q1−(1−ε)Ω(ζ6k/log⁡∣Z∣)1(fk)=Ω(k(ζ5⋅Qε+12ζ1(f)−log⁡log⁡(1/ζ))), \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),Q1−(1−ε)Ω(ζ6k/log∣Z∣)1​(fk)=Ω(k(ζ5⋅Qε+12ζ1​(f)−loglog(1/ζ))), where Qε1(f)\mathrm{Q}^1_{\varepsilon}(f)Qε1​(f) represents the one-way entanglement-assisted quantum communication complexity of fff with worst-case error ε\varepsilonε and fkf^kfk denotes kkk parallel instances of fff. 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)G = (q, \mathcal{X}\times\mathcal{Y}, \mathcal{A}\times\mathcal{B}, \mathsf{V})G=(q,X×Y,A×B,V) where qqq is a distribution on X×Y\mathcal{X}\times\mathcal{Y}X×Y anchored on any one side with anchoring probability ζζζ, then ω∗(Gk)=(1−(1−ω∗(G))5)Ω(ζ2klog⁡(∣A∣⋅∣B∣)) ω^*(G^k) = \left(1 - (1-ω^*(G))^5\right)^{Ω\left(\frac{ζ^2 k}{\log(|\mathcal{A}|\cdot|\mathcal{B}|)}\right)}ω∗(Gk)=(1−(1−ω∗(G))5)Ω(log(∣A∣⋅∣B∣)ζ2k​) where ω∗(G)ω^*(G)ω∗(G) represents the entangled value of the game GGG. 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 consider a quantum and a classical version of a multi-party function computation problem with n players, where players 2,…,n need to communicate appropriate information to player 1 so that a “generalized” inner product function with an appropriate promise can be calculated. In the quantum version of the protocol, the players have access to entangled qudits but the communication is still classical. The communication complexity of a given protocol is the total number of classical bits that need to be communicated. When n is prime, and for our chosen function, we exhibit a quantum protocol (with complexity (n−1)(logn) bits) and a classical protocol (with complexity ((n−1)2(logn2) bits)). Furthermore, we present an integer linear programming formulation for determining a lower bound on the classical communication complexity. This demonstrates that our quantum protocol is strictly better than classical protocols.
Computing set joins of two inputs is a common task in database theory. Recently, Van Gucht, Williams, Woodruff and Zhang [PODS 2015] considered the complexity of such problems in the natural model of (classical) two-party communication complexity and obtained tight bounds for the complexity of several important distributed set joins. In this paper we initiate the study of the *quantum* communication complexity of distributed set joins. We design a quantum protocol for distributed Boolean matrix multiplication, which corresponds to computing the composition join of two databases, showing that the product of two n×nn\times nn×n Boolean matrices, each owned by one of two respective parties, can be computed with O~(nℓ3/4)\widetilde{O}(\sqrt{n}\ell^{3/4})O(n​ℓ3/4) qubits of communication, where ℓ\ellℓ denotes the number of non-zero entries of the product. Since Van Gucht et al. showed that the classical communication complexity of this problem is Θ~(nℓ)\widetildeΘ(n\sqrt{\ell})Θ(nℓ​), our quantum algorithm outperforms classical protocols whenever the output matrix is sparse. We also show a quantum lower bound and a matching classical upper bound on the communication complexity of distributed matrix multiplication over F2\mathbb{F}_2F2​. Besides their applications to database theory, the communication complexity of set joins is interesting due to its connections to direct product theorems in communication complexity. In this work we also introduce a notion of *all-pairs* product theorem, and relate this notion to standard direct product theorems in communication complexity.
A strong direct product theorem for a problem in a given model of computation states that, in order to compute k instances of the problem, if we provide resource which is less than k times the resource required for computing one instance of the problem with constant success probability, then the probability of correctly computing all the k instances together, is exponentially small in k. In this paper, we consider the model of two-party bounded-round public-coin randomized communication complexity. We show a direct product theorem for the communication complexity of any relation in this model. In particular, our result implies a strong direct product theorem for the two-party constant-message public-coin randomized communication complexity of all relations. As an immediate application of our result, we get a strong direct product theorem for the pointer chasing problem. This problem has been well studied for understanding round v/s communication trade-offs in both classical and quantum communication protocols. Our result generalizes the result of Jain [2011] which can be regarded as the special case when t=1. Our result can be considered as an important progress towards settling the strong direct product conjecture for the two-party public-coin communication complexity, a major open question in this area. We show our result using information theoretic arguments. Our arguments and techniques build on the ones used in Jain~\cite{Jain:2011}. %, where a strong direct product theorem for the %two-party one-way public-coin communication complexity of all %relations is shown (that is the special case of our result when t=1t=1t=1). One key tool used in our work and also in Jain~\cite{Jain:2011} is a message compression technique due to Braver man and Rao~\cite{Braverman2011}, who used it to show a {\em direct sum} theorem in the same model of communication complexity as considered by us. Another important tool that we use is a correlated sampling protocol, which for example, has been used in Holenstein~\cite{Holenstein2007} for proving a parallel repetition theorem for two-prover games.