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:0712.4291 · IEEE Transactions on Information Theory

Sampling of Min-Entropy Relative to Quantum Knowledge

Robert König, Renato Renner

Published Jun 21, 2011• 65 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1109/tit.2011.2146730

Related papers

Entanglement Sampling and Applications

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 = 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.

arXiv:1305.1316•IEEE Transactions on Information Theory•Nov 26, 2014•95 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

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

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

Extracting More Quantum Randomness With Non-Uniform Quantization

Bai-Xiang Ji, Jian Li, Qin Wang

Random numbers generated via quantum process is indeterministic, which are of essential to the cryptographic communication and the large-scale computer modeling. However, in realistic scenarios, classical noises can inevitably contaminate the raw sequences of a quantum randomness number generator (QRNG), and then compromise the security of the QRNG. Min-entropy is a useful approach that can quantify the randomness independent of side-information. To enhance the extractable randomness of the raw sequences arising from the QRNG, we propose a new method which exploits non-uniform quantization methods instead of uniform sampling methods and effectively enhances the extractable randomness from the QRNG at a high quantum-to-classical-noise ratio (QCNR). Given a QCNR as 50 dB and a 16-bit analog-to-digital converter (ADC), the worst-case conditional min-entropy of the non-uniform quantization scheme is improved by nearly 11% compared with that of the uniform sampling scheme.

IEEE photonics journal•Aug 1, 2022•2 citations

Deterministic randomness extraction for quantum random number generation with partial trust

Pablo Tikas Pueyo, Tomás Fernández Martos, Gabriel Senno

It is a well-known fact in classical information theory that no deterministic procedure can extract close-to-ideal randomness from an arbitrary entropy source. On the other hand, if additional knowledge about the source is available -- e.g., that it is a sequence of independent Bernoulli trials -- then deterministic extractors do exist. For quantum entropy sources, where in addition to classical random variables we consider quantum side information, the use of extra knowledge about their structure was pioneered in a recent publication [C. Foreman and L. Masanes, Quantum 9, 1654 (2025)]. In that work, the authors provide deterministic extractors for device-independent randomness generation with memoryless devices achieving a sufficiently high CHSH score. In this work, we port their construction to the prepare-and-measure scenario. Specifically, we prove that the considered functions are also extractors for memoryless devices in settings with partial trust, either in the state preparation or in the measurement, as well as in a semi-device-independent setting under an overlap assumption on the prepared quantum states. Within this last setting, we simulate the resulting randomness generation protocol on a novel and experimentally relevant family of behaviors, observing positive key rates already for $7\times 10^3$ rounds.

quant-pharXiv:2512.08900•Dec 10, 2025•0 citations
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.
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.
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.
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.
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.
Random numbers generated via quantum process is indeterministic, which are of essential to the cryptographic communication and the large-scale computer modeling. However, in realistic scenarios, classical noises can inevitably contaminate the raw sequences of a quantum randomness number generator (QRNG), and then compromise the security of the QRNG. Min-entropy is a useful approach that can quantify the randomness independent of side-information. To enhance the extractable randomness of the raw sequences arising from the QRNG, we propose a new method which exploits non-uniform quantization methods instead of uniform sampling methods and effectively enhances the extractable randomness from the QRNG at a high quantum-to-classical-noise ratio (QCNR). Given a QCNR as 50 dB and a 16-bit analog-to-digital converter (ADC), the worst-case conditional min-entropy of the non-uniform quantization scheme is improved by nearly 11% compared with that of the uniform sampling scheme.
It is a well-known fact in classical information theory that no deterministic procedure can extract close-to-ideal randomness from an arbitrary entropy source. On the other hand, if additional knowledge about the source is available -- e.g., that it is a sequence of independent Bernoulli trials -- then deterministic extractors do exist. For quantum entropy sources, where in addition to classical random variables we consider quantum side information, the use of extra knowledge about their structure was pioneered in a recent publication [C. Foreman and L. Masanes, Quantum 9, 1654 (2025)]. In that work, the authors provide deterministic extractors for device-independent randomness generation with memoryless devices achieving a sufficiently high CHSH score. In this work, we port their construction to the prepare-and-measure scenario. Specifically, we prove that the considered functions are also extractors for memoryless devices in settings with partial trust, either in the state preparation or in the measurement, as well as in a semi-device-independent setting under an overlap assumption on the prepared quantum states. Within this last setting, we simulate the resulting randomness generation protocol on a novel and experimentally relevant family of behaviors, observing positive key rates already for 7×1037\times 10^37×103 rounds.