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:1806.04553

Quantum Probability Estimation for Randomness with Quantum Side Information

Emanuel H. Knill, Yanbao Zhang, Honghao Fu

Published Jun 12, 2018• 26 citations
arXivHTMLPDF

Abstract

We develop a quantum version of the probability estimation framework [arXiv:1709.06159] for randomness generation with quantum side information. We show that most of the properties of probability estimation hold for quantum probability estimation (QPE). This includes asymptotic optimality at constant error and randomness expansion with logarithmic input entropy. QPE is implemented by constructing model-dependent quantum estimation factors (QEFs), which yield statistical confidence upper bounds on data-conditional normalized Rényi powers. This leads to conditional min-entropy estimates for randomness generation. The bounds are valid for relevant models of sequences of experimental trials without requiring independent and identical or stationary behavior. QEFs may be adapted to changing conditions during the sequence and trials can be stopped any time, such as when the results so far are satisfactory. QEFs can be constructed from entropy estimators to improve the bounds for conditional min-entropy of classical-quantum states from the entropy accumulation framework [Dupuis, Fawzi and Renner, arXiv:1607.01796]. QEFs are applicable to a larger class of models, including models permitting experimental devices with super-quantum but non-signaling behaviors and semi-device dependent models. The improved bounds are relevant for finite data or error bounds of the form $e^{-κs}$, where $s$ is the number of random bits produced. We give a general construction of entropy estimators based on maximum probability estimators, which exist for many configurations. For the class of $(k,2,2)$ Bell-test configurations we provide schemas for directly optimizing QEFs to overcome the limitations of entropy-estimator-based constructions. We obtain and apply QEFs for examples involving the $(2,2,2)$ Bell-test configuration to demonstrate substantial improvements in finite-data efficiency.

DOI
10.48550/arxiv.1806.04553

Related papers

Efficient randomness certification by quantum probability estimation

Yanbao Zhang, Honghao Fu, Emanuel H. Knill

For practical applications of quantum randomness generation, it is important to certify and further produce a fixed block of fresh random bits with as few trials as possible.Consequently, protocols with high finite-data efficiency are preferred.To yield such protocols with respect to quantum side information, we develop quantum probability estimation.Our approach is applicable to device-independent as well as device-dependent scenarios, and it generalizes techniques from previous works [Miller and Shi, SIAM J. Comput. 46, 1304 (2017); Arnon-Friedman et al., Nat. Commun. 9, 459 (2018)].Quantum probability estimation can adapt to changing experimental conditions, allows stopping the experiment as soon as the prespecified randomness goal is achieved, and can tolerate imperfect knowledge of the input distribution.Moreover, the randomness rate achieved at constant error is asymptotically optimal.For the device-independent scenario, our approach certifies the amount of randomness available in experimental results without first searching for relations between randomness and violations of fixed Bell inequalities.We implement quantum probability estimation for device-independent randomness generation in the CHSH Bell-test configuration, and we show significant improvements in finite-data efficiency, particularly at small Bell violations which are typical in current photonic loophole-free Bell tests.

Physical Review Research•Jan 7, 2020•49 citations

Certifying quantum randomness by probability estimation

Yanbao Zhang, Emanuel H. Knill, Peter Bierhorst

We introduce probability estimation, a broadly applicable framework to certify randomness in a finite sequence of measurement results without assuming that these results are independent and identically distributed. Probability estimation can take advantage of verifiable physical constraints, and the certification is with respect to classical side information. Examples include randomness from single-photon measurements and device-independent randomness from Bell tests. Advantages of probability estimation include adaptability to changing experimental conditions, unproblematic early stopping when goals are achieved, optimal randomness rates, applicability to Bell tests with small violations, and unsurpassed finite-data efficiency. We greatly reduce latencies for producing random bits and formulate an associated rate-tradeoff problem of independent interest. We also show that the latency is determined by an information-theoretic measure of nonlocality rather than the Bell violation.

arXiv:1811.11928•Physical Review A•Oct 31, 2018•34 citations

Device-independent randomness generation from several Bell estimators

Olmo Nieto-Silleras, Cédric Bamps, Jonathan Silman +1 more

Device-independent randomness generation and quantum key distribution protocols rely on a fundamental relation between the non-locality of quantum theory and its random character. This relation is usually expressed in terms of a trade-off between the probability of guessing correctly the outcomes of measurements performed on quantum systems and the amount of violation of a given Bell inequality. However, a more accurate assessment of the randomness produced in Bell experiments can be obtained if the value of several Bell expressions is simultaneously taken into account, or if the full set of probabilities characterizing the behavior of the device is considered. We introduce protocols for device-independent randomness generation secure against classical side information, that rely on the estimation of an arbitrary number of Bell expressions or even directly on the experimental frequencies of measurement outcomes. Asymptotically, this results in an optimal generation of randomness from experimental data (as measured by the min-entropy), without having to assume beforehand that the devices violate a specific Bell inequality.

arXiv:1611.00352•New Journal of Physics•Jan 23, 2018•35 citations

Generalised entropy accumulation

Tony Metger, Omar Fawzi, David Sutter +1 more

The min-entropy of a quantum system A conditioned on another quantum system E describes how much randomness can be extracted from A with respect to an adversary in possession of E. This quantity plays a crucial role in quantum cryptography: the security proofs of many quantum cryptographic protocols reduce to showing a lower bound on such a min-entropy. Here, we develop a new tool, called generalised entropy accumulation, for computing such bounds. Concretely, we consider a sequential process in which each step outputs a system Aiand updates a side information register E. We prove that if this process satisfies a natural “non-signalling” condition between past outputs and future side information, the min-entropy of the outputs $A_{1},\ldots,\ A_{n}$ conditioned on the side information E at the end of the process can be bounded from below by a sum of von Neumann entropies associated with the individual steps. This is a generalisation of the entropy accumulation theorem (EAT) [1], which deals with a more restrictive model of side information: there, past side information cannot be updated in subsequent rounds, and newly generated side information has to satisfy a Markov condition.Due to its more general model of side-information, our generalised EAT can be applied more easily and to a broader range of cryptographic protocols. In particular, it is the first general tool that is applicable to mistrustful device-independent cryptography. To demonstrate this, we give the first security proof for blind randomness expansion [2] against general adversaries. Furthermore, our generalised EAT can be used to give improved security proofs for quantum key distribution [3], and also has applications beyond quantum cryptography.

Annual Symposium on Foundations of Computer Science•Oct 1, 2022•46 citations

Trevisan's Extractor in the Presence of Quantum Side Information

Anindya De, Christopher Portmann, Thomas Vidick +1 more

Randomness extraction involves the processing of purely classical information and is therefore usually studied with in the framework of classical probability theory. However, such a classical treatment is generally too restrictive for applications where side information about the values taken by classical random variables may be represented by the state of a quantum system. This is particularly relevant in the context of cryptography, where an adversary may make use of quantum devices. Here, we show that the well-known construction paradigm for extractors proposed by Trevisan is sound in the presence of quantum side information. We exploit the modularity of this paradigm to give several concrete extractor constructions, which, e.g., extract all the conditional (smooth) min-entropy of the source using a seed of length polylogarithmic in the input, or only require the seed to be weakly random.

arXiv:0912.5514•SIAM Journal on Computing•Jan 1, 2012•187 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•1 citation
We develop a quantum version of the probability estimation framework [arXiv:1709.06159] for randomness generation with quantum side information. We show that most of the properties of probability estimation hold for quantum probability estimation (QPE). This includes asymptotic optimality at constant error and randomness expansion with logarithmic input entropy. QPE is implemented by constructing model-dependent quantum estimation factors (QEFs), which yield statistical confidence upper bounds on data-conditional normalized Rényi powers. This leads to conditional min-entropy estimates for randomness generation. The bounds are valid for relevant models of sequences of experimental trials without requiring independent and identical or stationary behavior. QEFs may be adapted to changing conditions during the sequence and trials can be stopped any time, such as when the results so far are satisfactory. QEFs can be constructed from entropy estimators to improve the bounds for conditional min-entropy of classical-quantum states from the entropy accumulation framework [Dupuis, Fawzi and Renner, arXiv:1607.01796]. QEFs are applicable to a larger class of models, including models permitting experimental devices with super-quantum but non-signaling behaviors and semi-device dependent models. The improved bounds are relevant for finite data or error bounds of the form e−κse^{-κs}e−κs, where sss is the number of random bits produced. We give a general construction of entropy estimators based on maximum probability estimators, which exist for many configurations. For the class of (k,2,2)(k,2,2)(k,2,2) Bell-test configurations we provide schemas for directly optimizing QEFs to overcome the limitations of entropy-estimator-based constructions. We obtain and apply QEFs for examples involving the (2,2,2)(2,2,2)(2,2,2) Bell-test configuration to demonstrate substantial improvements in finite-data efficiency.
For practical applications of quantum randomness generation, it is important to certify and further produce a fixed block of fresh random bits with as few trials as possible.Consequently, protocols with high finite-data efficiency are preferred.To yield such protocols with respect to quantum side information, we develop quantum probability estimation.Our approach is applicable to device-independent as well as device-dependent scenarios, and it generalizes techniques from previous works [Miller and Shi, SIAM J. Comput. 46, 1304 (2017); Arnon-Friedman et al., Nat. Commun. 9, 459 (2018)].Quantum probability estimation can adapt to changing experimental conditions, allows stopping the experiment as soon as the prespecified randomness goal is achieved, and can tolerate imperfect knowledge of the input distribution.Moreover, the randomness rate achieved at constant error is asymptotically optimal.For the device-independent scenario, our approach certifies the amount of randomness available in experimental results without first searching for relations between randomness and violations of fixed Bell inequalities.We implement quantum probability estimation for device-independent randomness generation in the CHSH Bell-test configuration, and we show significant improvements in finite-data efficiency, particularly at small Bell violations which are typical in current photonic loophole-free Bell tests.
We introduce probability estimation, a broadly applicable framework to certify randomness in a finite sequence of measurement results without assuming that these results are independent and identically distributed. Probability estimation can take advantage of verifiable physical constraints, and the certification is with respect to classical side information. Examples include randomness from single-photon measurements and device-independent randomness from Bell tests. Advantages of probability estimation include adaptability to changing experimental conditions, unproblematic early stopping when goals are achieved, optimal randomness rates, applicability to Bell tests with small violations, and unsurpassed finite-data efficiency. We greatly reduce latencies for producing random bits and formulate an associated rate-tradeoff problem of independent interest. We also show that the latency is determined by an information-theoretic measure of nonlocality rather than the Bell violation.
Device-independent randomness generation and quantum key distribution protocols rely on a fundamental relation between the non-locality of quantum theory and its random character. This relation is usually expressed in terms of a trade-off between the probability of guessing correctly the outcomes of measurements performed on quantum systems and the amount of violation of a given Bell inequality. However, a more accurate assessment of the randomness produced in Bell experiments can be obtained if the value of several Bell expressions is simultaneously taken into account, or if the full set of probabilities characterizing the behavior of the device is considered. We introduce protocols for device-independent randomness generation secure against classical side information, that rely on the estimation of an arbitrary number of Bell expressions or even directly on the experimental frequencies of measurement outcomes. Asymptotically, this results in an optimal generation of randomness from experimental data (as measured by the min-entropy), without having to assume beforehand that the devices violate a specific Bell inequality.
The min-entropy of a quantum system A conditioned on another quantum system E describes how much randomness can be extracted from A with respect to an adversary in possession of E. This quantity plays a crucial role in quantum cryptography: the security proofs of many quantum cryptographic protocols reduce to showing a lower bound on such a min-entropy. Here, we develop a new tool, called generalised entropy accumulation, for computing such bounds. Concretely, we consider a sequential process in which each step outputs a system Aiand updates a side information register E. We prove that if this process satisfies a natural “non-signalling” condition between past outputs and future side information, the min-entropy of the outputs A1,…, AnA_{1},\ldots,\ A_{n}A1​,…, An​ conditioned on the side information E at the end of the process can be bounded from below by a sum of von Neumann entropies associated with the individual steps. This is a generalisation of the entropy accumulation theorem (EAT) [1], which deals with a more restrictive model of side information: there, past side information cannot be updated in subsequent rounds, and newly generated side information has to satisfy a Markov condition.Due to its more general model of side-information, our generalised EAT can be applied more easily and to a broader range of cryptographic protocols. In particular, it is the first general tool that is applicable to mistrustful device-independent cryptography. To demonstrate this, we give the first security proof for blind randomness expansion [2] against general adversaries. Furthermore, our generalised EAT can be used to give improved security proofs for quantum key distribution [3], and also has applications beyond quantum cryptography.
Randomness extraction involves the processing of purely classical information and is therefore usually studied with in the framework of classical probability theory. However, such a classical treatment is generally too restrictive for applications where side information about the values taken by classical random variables may be represented by the state of a quantum system. This is particularly relevant in the context of cryptography, where an adversary may make use of quantum devices. Here, we show that the well-known construction paradigm for extractors proposed by Trevisan is sound in the presence of quantum side information. We exploit the modularity of this paradigm to give several concrete extractor constructions, which, e.g., extract all the conditional (smooth) min-entropy of the source using a seed of length polylogarithmic in the input, or only require the seed to be weakly random.
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.