Entanglement Sampling and Applications

A natural measure for the amount of quantum information that a physical system E holds about another system A = A(1), ... , A(n) is given by the min-entropy H-min(A vertical bar E). In particular, the min-entropy measures the amount of entanglement between E and A, and is the relevant measure when analyzing a wide variety of problems ranging from randomness extraction in quantum cryptography, decoupling used in channel coding, to physical processes such as thermalization or the thermodynamic work cost (or gain) of erasing a quantum system. As such, it is a central question to determine the behavior of the min-entropy after some process M is applied to the system A. Here, we introduce a new generic tool relating the resulting min-entropy to the original one, and apply it to several settings of interest. A simple example of such a process is the one of sampling, where a subset S of the systems A(1), ... , A(n) is selected at random. Our tool allows us to quantify the entanglement that E has with the selected systems A(S), i.e., H-min(A(S)vertical bar ES) as a function of the original H-min(A vertical bar E). We give two applications of this result. First, it directly provides the first local quantum-to-classical randomness extractors for use in quantum cryptography, as well as decoupling operations acting on only a small fraction AS of the input A. Moreover, it gives lower bounds on the dimension of k-out-of-n fully quantum random access encodings. Another natural example of such a process is a measurement in, e.g., BB84 bases commonly used in quantum cryptography. We establish the first entropic uncertainty relations with quantum side information that are nontrivial whenever E is not maximally entangled with A. As a consequence, we are able to prove optimality of quantum cryptographic schemes in the noisy-storage model. This model allows for the secure implementation of two-party cryptographic primitives under the assumption that the adversary cannot store quantum information perfectly. A special case is the bounded-quantum-storage model (BQSM), which assumes that the adversary's quantum memory device is noise free but limited in size. Ever since the inception of the BQSM, it has been a vexing open question to determine whether the security is possible as long as the adversary can only store strictly less than the number of qubits n transmitted during the protocol. Here, we show that security is even possible as long as the adversary's device is not larger than n - O(log(2) n) qubits, which finally settles the fundamental limits of the BQSM.