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

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 (2012), which is a lower bound on the distributional quantum communication complexity of computing a single copy of V with respect to p. For a two-input boolean function f , 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, which is a lower bound on communication. Our lower bound on non-distributional communication complexity is in terms of max product p eff * (V, p), and there is no known relationship between this and the generalized discrepancy. But we define a distributional version of the generalized discrepancy bound and can show that for a given p, eff * (V, p) upper bounds it. Moreover, unlike Sherstov's result, our result works for two-input functions or relations whose outputs are non-boolean as well, and is a strong direct product theorem for functions or relations whose quantum communication complexity is characterized by eff * (V f , p) for a product 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 (it is not known how to do parallel DI randomness expansion even without 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.