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• 14 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•47 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•30 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•33 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•35 citations

Experimental Realization of Device-Independent Quantum Randomness Expansion

Minghan Li, Xingjian Zhang, Wen‐Zhao Liu +12 more

Randomness expansion where one generates a longer sequence of random numbers from a short one is viable in quantum mechanics but not allowed classically. Device-independent quantum randomness expansion provides a randomness resource of the highest security level. Here, we report the first experimental realization of device-independent quantum randomness expansion secure against quantum side information established through quantum probability estimation. We generate $5.47\ifmmode\times\else\texttimes\fi{}{10}^{8}$ quantum-proof random bits while consuming $4.39\ifmmode\times\else\texttimes\fi{}{10}^{8}\text{ }\text{ }\mathrm{bits}$ of entropy, expanding our store of randomness by $1.08\ifmmode\times\else\texttimes\fi{}{10}^{8}\text{ }\text{ }\mathrm{bits}$ at a latency of about 13.1 h, with a total soundness error $4.6\ifmmode\times\else\texttimes\fi{}{10}^{\ensuremath{-}10}$. Device-independent quantum randomness expansion not only enriches our understanding of randomness but also sets a solid base to bring quantum-certifiable random bits into realistic applications.

arXiv:1902.07529•Physical Review Letters•Feb 4, 2021•69 citations

Rethinking quantum smooth entropies: Tight one-shot analysis of quantum privacy amplification

Bartosz Regula, Marco Tomamichel

We introduce an improved one-shot characterisation of randomness extraction against quantum side information (privacy amplification), strengthening known one-shot bounds and providing a unified derivation of the tightest known asymptotic constraints. Our main tool is a new class of smooth conditional entropies defined by lifting classical smooth divergences through measurements. A key role is played by the measured smooth Rényi relative entropy of order 2, which we show to admit an equivalent variational form: it can be understood as allowing for smoothing over not only states, but also non-positive Hermitian operators. Building on this, we establish a tightened leftover hash lemma, significantly improving over all known smooth min-entropy bounds on extractable randomness and recovering the sharpest classical achievability results. We extend these methods to decoupling, the coherent analogue of privacy amplification, obtaining a corresponding improved one-shot bound. Relaxing our smooth entropy bounds leads to one-shot achievability results in terms of measured Rényi divergences, tightening the bounds of [Dupuis, arXiv:2105.05342] and recovering state-of-the-art asymptotic i.i.d. error exponents. We show an approximate optimality of our results by giving a matching one-shot converse bound up to additive logarithmic terms. This yields an optimal second-order asymptotic expansion of privacy amplification under trace distance, establishing a significantly tighter one-shot achievability result than previously shown in [Shen et al., arXiv:2202.11590] and proving its optimality for all hash functions.

quant-pharXiv:2603.04493•Mar 6, 2026•0 citations
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 expansion where one generates a longer sequence of random numbers from a short one is viable in quantum mechanics but not allowed classically. Device-independent quantum randomness expansion provides a randomness resource of the highest security level. Here, we report the first experimental realization of device-independent quantum randomness expansion secure against quantum side information established through quantum probability estimation. We generate $5.47\ifmmode\times\else\texttimes\fi{}{10}^{8}$ quantum-proof random bits while consuming $4.39\ifmmode\times\else\texttimes\fi{}{10}^{8}\text{ }\text{ }\mathrm{bits}$ of entropy, expanding our store of randomness by $1.08\ifmmode\times\else\texttimes\fi{}{10}^{8}\text{ }\text{ }\mathrm{bits}$ at a latency of about 13.1 h, with a total soundness error $4.6\ifmmode\times\else\texttimes\fi{}{10}^{\ensuremath{-}10}$. Device-independent quantum randomness expansion not only enriches our understanding of randomness but also sets a solid base to bring quantum-certifiable random bits into realistic applications.
We introduce an improved one-shot characterisation of randomness extraction against quantum side information (privacy amplification), strengthening known one-shot bounds and providing a unified derivation of the tightest known asymptotic constraints. Our main tool is a new class of smooth conditional entropies defined by lifting classical smooth divergences through measurements. A key role is played by the measured smooth Rényi relative entropy of order 2, which we show to admit an equivalent variational form: it can be understood as allowing for smoothing over not only states, but also non-positive Hermitian operators. Building on this, we establish a tightened leftover hash lemma, significantly improving over all known smooth min-entropy bounds on extractable randomness and recovering the sharpest classical achievability results. We extend these methods to decoupling, the coherent analogue of privacy amplification, obtaining a corresponding improved one-shot bound. Relaxing our smooth entropy bounds leads to one-shot achievability results in terms of measured Rényi divergences, tightening the bounds of [Dupuis, arXiv:2105.05342] and recovering state-of-the-art asymptotic i.i.d. error exponents. We show an approximate optimality of our results by giving a matching one-shot converse bound up to additive logarithmic terms. This yields an optimal second-order asymptotic expansion of privacy amplification under trace distance, establishing a significantly tighter one-shot achievability result than previously shown in [Shen et al., arXiv:2202.11590] and proving its optimality for all hash functions.