Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1305.1316 · IEEE Transactions on Information Theory

Entanglement Sampling and Applications

Frédéric Dupuis, Omar Fawzi, Stephanie Wehner

Published Nov 26, 2014• 95 citations
arXivHTMLPDF

Abstract

A natural measure for the amount of quantum information that a physical system E holds about another system A = A1, .. . , Anis 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.

DOI
10.1109/tit.2014.2371464

Related papers

Achieving the Limits of the Noisy-Storage Model Using Entanglement Sampling

Frédéric Dupuis, Omar Fawzi, Stephanie Wehner

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 | E ). Specifically, 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 behaviour 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, including sampling of subsystems and measuring in a randomly chosen basis. The results on random measurements yield new high-order entropic uncertainty relations with which we prove the optimality of cryptographic schemes in the bounded quantum storage model. This is an abridged version of the paper; the full version containing all proofs and further applications can be found in [13]. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

Lecture notes in computer science•Jan 1, 2013•3 citations

Sampling of Min-Entropy Relative to Quantum Knowledge

Robert König, Renato Renner

Let$X_1, \ldots, X_n$be a sequence of$n$classical random variables and consider a sample$X_{s_1}, \ldots, X_{s_r}$of$r \leq n$positions selected at random. Then, except with (exponentially in$r$) small probability, the min-entropy$H_{\min}(X_{s_1} \cdots X_{s_r})$of the sample is not smaller than, roughly, a fraction${r\over n}$of the overall entropy$H_{\min}(X_1 \cdots X_n)$, which is optimal. Here, we show that this statement, originally proved in [S. Vadhan, LNCS 2729, Springer, 2003] for the purely classical case, is still true if the min-entropy$H_{\min}$is measured relative to a quantum system. Because min-entropy quantifies the amount of randomness that can be extracted from a given random variable, our result can be used to prove the soundness of locally computable extractors in a context where side information might be quantum-mechanical. In particular, it implies that key agreement in the bounded-storage model—using a standard sample-and-hash protocol—is fully secure against quantum adversaries, thus solving a long-standing open problem.

arXiv:0712.4291•IEEE Transactions on Information Theory•Jun 21, 2011•65 citations

Quantum to Classical Randomness Extractors

Mario Berta, Omar Fawzi, Stephanie Wehner

The goal of randomness extraction is to distill (almost) perfect randomness from a weak source of randomness. When the source yields a classical string X, many extractor constructions are known. Yet, when considering a physical randomness source, X is itself ultimately the result of a measurement on an underlying quantum system. When characterizing the power of a source to supply randomness, it is hence natural to ask how much classical randomness we can extract from a quantum system. To tackle this question, we here take on the study of quantum-to-classical randomness extractors (QC-extractors). We provide constructions of QC-extractors based on measurements in a full set of mutually unbiased bases (MUBs), and certain single qubit measurements. The latter are particularly appealing since they are not only easy to implement, but also appear throughout quantum cryptography. We proceed to prove an upper bound on the maximum amount of randomness that we could hope to extract from any quantum state. Some of our QC-extractors almost match this bound. We show two applications of our results. First, we show that any QC-extractor gives rise to entropic uncertainty relations with respect to quantum side information. Such relations were previously only known for two measurements. In particular, we obtain strong relations in terms of the von Neumann (Shannon) entropy as well as the min-entropy for measurements in (almost) unitary two-designs, a full set of MUBs, and single qubit measurements in three MUBs each. Second, we resolve the central open question in the noisy-storage model by linking security to the quantum capacity of the adversary's storage device. More precisely, we show that any two party cryptographic primitives can be implemented securely as long as the adversary's storage device has sufficiently low quantum capacity. Our protocol does not need any quantum storage to implement, and is technologically feasible using present-day technology.

arXiv:1111.2026•IEEE Transactions on Information Theory•Jan 24, 2014•38 citations

One-Shot Min-Entropy Calculation of Classical-Quantum States and Its Application to Quantum Cryptography

Rong Wang, H. F. Chau

In quantum Shannon theory, various kinds of quantum entropies are used to characterize the capacities of noisy physical systems. Among them, min-entropy and its smooth version attract wide interest especially in the field of quantum cryptography as they can be used to bound the information obtained by an adversary. However, calculating the exact value or nontrivial bounds of min-entropy are extremely difficult because the composite system dimension may scale exponentially with the dimension of its subsystem. Here, we develop a one-shot lower bound calculation technique for the min-entropy of a classical-quantum state that is applicable to both finite and infinite dimensional reduced quantum states. Moreover, we show our technique is of practical interest in at least three situations. First, it offers an alternative tight finite-data analysis for the BB84 quantum key distribution scheme. Second, it gives the best finite-key bound known to date for a variant of device independent quantum key distribution protocol. Third, it provides a security proof for a novel source-independent continuous-variable quantum random number generation protocol. These results show the effectiveness and wide applicability of our approach.

arXiv:2406.15226•Physical Review Letters•Jun 9, 2025•3 citations

Bitwise Quantum Min-Entropy Sampling and New Lower Bounds for Random Access Codes

Jürg Wullschleger

Min-entropy sampling gives a bound on the min-entropy of a randomly chosen subset of a string, given a bound on the min-entropy of the whole string. König and Renner showed a min-entropy sampling theorem that holds relative to quantum knowledge. Their result achieves the optimal rate, but it can only be applied if the bits are sampled in blocks, and only gives weak bounds for the non-smooth min-entropy. We give two new quantum min-entropy sampling theorems that do not have the above weaknesses. The first theorem shows that the result by König and Renner also applies to bitwise sampling, and the second theorem gives a strong bound for the non-smooth min-entropy. Our results imply a new lower bound for k-out-of-n random access codes: while previous results by Ben-Aroya, Regev, and de Wolf showed that the decoding probability is exponentially small in k if the storage rate is smaller than 0.7, our results imply that this holds for any storage rate strictly smaller than 1, which is optimal.

arXiv:1012.2291•Dec 10, 2010•5 citations

Quantum Computational Unpredictability Entropy and Quantum Leakage Resilience

Noam Avidan, Rotem Arnon-Friedman

Computational entropies provide a framework for quantifying uncertainty and randomness under computational constraints. They play a central role in classical cryptography, underpinning the analysis and construction of primitives such as pseudo-random generators, leakage-resilient cryptography, and randomness extractors. However, in the quantum setting, computational analogs of entropy remain largely unexplored. In this work, we initiate the study of quantum computational entropy by definingquantum computational unpredictability entropy, a natural generalization of classical unpredictability entropy to the quantum setting. Our definition builds on the operational interpretation of quantum min-entropy as the optimal guessing probability, while restricting the adversary to efficient guessing strategies. We prove that this entropy satisfies several fundamental properties, including a leakage chain rule that holds even in the presence of unbounded prior quantum side-information. We also show that unpredictability entropy enables pseudo-randomness extraction against quantum adversaries with bounded computational power. Together, these results lay a foundation for developing cryptographic tools that rely on min-entropy in the quantum computational setting.

arXiv:2505.13710•IEEE Transactions on Information Theory•Jan 28, 2026•1 citation
A natural measure for the amount of quantum information that a physical system E holds about another system A = A1, .. . , Anis 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.
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 | E ). Specifically, 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 behaviour 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, including sampling of subsystems and measuring in a randomly chosen basis. The results on random measurements yield new high-order entropic uncertainty relations with which we prove the optimality of cryptographic schemes in the bounded quantum storage model. This is an abridged version of the paper; the full version containing all proofs and further applications can be found in [13]. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
LetX1,…,XnX_1, \ldots, X_nX1​,…,Xn​be a sequence ofnnnclassical random variables and consider a sampleXs1,…,XsrX_{s_1}, \ldots, X_{s_r}Xs1​​,…,Xsr​​ofr≤nr \leq nr≤npositions selected at random. Then, except with (exponentially inrrr) small probability, the min-entropyHmin⁡(Xs1⋯Xsr)H_{\min}(X_{s_1} \cdots X_{s_r})Hmin​(Xs1​​⋯Xsr​​)of the sample is not smaller than, roughly, a fractionrn{r\over n}nr​of the overall entropyHmin⁡(X1⋯Xn)H_{\min}(X_1 \cdots X_n)Hmin​(X1​⋯Xn​), which is optimal. Here, we show that this statement, originally proved in [S. Vadhan, LNCS 2729, Springer, 2003] for the purely classical case, is still true if the min-entropyHmin⁡H_{\min}Hmin​is measured relative to a quantum system. Because min-entropy quantifies the amount of randomness that can be extracted from a given random variable, our result can be used to prove the soundness of locally computable extractors in a context where side information might be quantum-mechanical. In particular, it implies that key agreement in the bounded-storage model—using a standard sample-and-hash protocol—is fully secure against quantum adversaries, thus solving a long-standing open problem.
The goal of randomness extraction is to distill (almost) perfect randomness from a weak source of randomness. When the source yields a classical string X, many extractor constructions are known. Yet, when considering a physical randomness source, X is itself ultimately the result of a measurement on an underlying quantum system. When characterizing the power of a source to supply randomness, it is hence natural to ask how much classical randomness we can extract from a quantum system. To tackle this question, we here take on the study of quantum-to-classical randomness extractors (QC-extractors). We provide constructions of QC-extractors based on measurements in a full set of mutually unbiased bases (MUBs), and certain single qubit measurements. The latter are particularly appealing since they are not only easy to implement, but also appear throughout quantum cryptography. We proceed to prove an upper bound on the maximum amount of randomness that we could hope to extract from any quantum state. Some of our QC-extractors almost match this bound. We show two applications of our results. First, we show that any QC-extractor gives rise to entropic uncertainty relations with respect to quantum side information. Such relations were previously only known for two measurements. In particular, we obtain strong relations in terms of the von Neumann (Shannon) entropy as well as the min-entropy for measurements in (almost) unitary two-designs, a full set of MUBs, and single qubit measurements in three MUBs each. Second, we resolve the central open question in the noisy-storage model by linking security to the quantum capacity of the adversary's storage device. More precisely, we show that any two party cryptographic primitives can be implemented securely as long as the adversary's storage device has sufficiently low quantum capacity. Our protocol does not need any quantum storage to implement, and is technologically feasible using present-day technology.
In quantum Shannon theory, various kinds of quantum entropies are used to characterize the capacities of noisy physical systems. Among them, min-entropy and its smooth version attract wide interest especially in the field of quantum cryptography as they can be used to bound the information obtained by an adversary. However, calculating the exact value or nontrivial bounds of min-entropy are extremely difficult because the composite system dimension may scale exponentially with the dimension of its subsystem. Here, we develop a one-shot lower bound calculation technique for the min-entropy of a classical-quantum state that is applicable to both finite and infinite dimensional reduced quantum states. Moreover, we show our technique is of practical interest in at least three situations. First, it offers an alternative tight finite-data analysis for the BB84 quantum key distribution scheme. Second, it gives the best finite-key bound known to date for a variant of device independent quantum key distribution protocol. Third, it provides a security proof for a novel source-independent continuous-variable quantum random number generation protocol. These results show the effectiveness and wide applicability of our approach.
Min-entropy sampling gives a bound on the min-entropy of a randomly chosen subset of a string, given a bound on the min-entropy of the whole string. König and Renner showed a min-entropy sampling theorem that holds relative to quantum knowledge. Their result achieves the optimal rate, but it can only be applied if the bits are sampled in blocks, and only gives weak bounds for the non-smooth min-entropy. We give two new quantum min-entropy sampling theorems that do not have the above weaknesses. The first theorem shows that the result by König and Renner also applies to bitwise sampling, and the second theorem gives a strong bound for the non-smooth min-entropy. Our results imply a new lower bound for k-out-of-n random access codes: while previous results by Ben-Aroya, Regev, and de Wolf showed that the decoding probability is exponentially small in k if the storage rate is smaller than 0.7, our results imply that this holds for any storage rate strictly smaller than 1, which is optimal.
Computational entropies provide a framework for quantifying uncertainty and randomness under computational constraints. They play a central role in classical cryptography, underpinning the analysis and construction of primitives such as pseudo-random generators, leakage-resilient cryptography, and randomness extractors. However, in the quantum setting, computational analogs of entropy remain largely unexplored. In this work, we initiate the study of quantum computational entropy by definingquantum computational unpredictability entropy, a natural generalization of classical unpredictability entropy to the quantum setting. Our definition builds on the operational interpretation of quantum min-entropy as the optimal guessing probability, while restricting the adversary to efficient guessing strategies. We prove that this entropy satisfies several fundamental properties, including a leakage chain rule that holds even in the presence of unbounded prior quantum side-information. We also show that unpredictability entropy enables pseudo-randomness extraction against quantum adversaries with bounded computational power. Together, these results lay a foundation for developing cryptographic tools that rely on min-entropy in the quantum computational setting.