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

.We give a direct product theorem for the entanglement-assisted interactive quantum communication complexity of an \(l\)-player predicate \(V\). In particular, we show that for a distribution \(p\) that is product across the input sets of the \(l\) players, the success probability of any entanglement-assisted quantum communication protocol for computing \(n\) copies of \(V\), whose communication is \(o(log (eff^*(V,p))· n)\), goes down exponentially in \(n\). Here \(eff^*(V, p)\) 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 \(V\) with respect to \(p\). Applying our direct product theorem for small communication, and techniques related to \(eff^*\), 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 \(Ω (n)\) bits of key from it, even in the presence of \(O(n)\) bits of leakage. Finally, we show that proofs of quantumness with two entangled provers are resistant to leakage, i.e., classical players who communicate \(O(n)\) bits with each other cannot convince the verifier that they share entanglement.