MajuLab Seminar by Rahul Jain – 12 April 2023

4:30 PM Singapore time | 10:30 AM French time

In person at SPMS MAS Executive Classroom 1 (SPMS-MAS-03-06), NTU
Online via Zoom, registration is required. 

Please register at:

Rahul Jain, Centre for Quantum Technologies, National University of Singapore

Rahul Jain

Rahul Jain

Rahul Jain has been promoted to full Professor from 1 January 2020. He was an Associate Professor at the Computer Science Department of the National University of Singapore (NUS) from July 2013 (Assistant Professor Nov2008 – July 2013). He obtained his PhD from Tata Institute of Fundamental Research, Mumbai, India in 2003. He was a postdoctoral researcher at the University of California at Berkeley, USA from 2004-2006 and at the Institute for Quantum Computing (IQC), University of Waterloo, Canada from 2006-2008. He obtained Bachelor’s degree (B-Tech) in Electrical and Electronics Engineering from Indian Institute of Technology, Mumbai (IIT-B), India in 1997. He is a Principle Investigator at the Centre for Quantum Technologies (CQT), Singapore from Nov. 2008.


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 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 MajuLab

MajuLab is an international joint research unit of the CNRS, UCA, SU, NUS and NTU in Singapore (IRL 3654), hosted by CQT and SPMS.