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 by Laplante, Lerays and Roland (2014), 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. First, we analyze the parallel DI quantum key distribution protocol given by Jain, Miller and Shi (2020), and show that when the protocol is carried out with devices that are compatible with n copies of the Magic Square game, it is possible to extract Ω(n) bits of key from it, even in the presence of O(n) bits of leakage. Second, we show that it is possible to do sequential versions of the Jain, Miller and Shi protocol, which give a better key rate for QKD with leakage, and let us do sequential DI randomness expansion with leakage. Third, 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.

The talk is based on:

A direct product theorem for quantum communication complexity with applications to device- independent QKD. Rahul Jain, Srijita Kundu. Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2021. Conference on Quantum Information Processing (QIP), 2022 (short plenary talk). ArXiv:2106.04299