Entanglement sampling and applications

Frederic Dupuis, Omar Fawzi, Stephanie Wehner

Research output: Contribution to journalArticleScientificpeer-review

58 Citations (Scopus)


A natural measure for the amount of quantum information that a physical system E holds about another system A = A1, . . . , An is given by the min-entropy Hmin(A|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 minentropy 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 A1, . . . , An is selected at random. Our tool allows us to quantify the entanglement that E has with the selected systems AS, i.e., Hmin(AS|ES) as a function of the original Hmin(A|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(log2 n) qubits, which finally settles the fundamental limits of the BQSM.

Original languageEnglish
Article number6967820
Pages (from-to)1093-1112
Number of pages20
JournalIEEE Transactions on Information Theory
Issue number2
Publication statusPublished - 1 Feb 2015
Externally publishedYes


  • bounded storage model
  • collision entropy
  • entropic uncertainty relation
  • min-entropy sampling
  • noisy quantum-storage model
  • Quantum cryptography
  • random access codes


Dive into the research topics of 'Entanglement sampling and applications'. Together they form a unique fingerprint.

Cite this