Efficient randomness certification by quantum probability estimation

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.