Device-independent randomness generation with sublinear shared quantum resources

Cédric Bamps, Serge Massar, and Stefano Pironio

Laboratoire d'Information Quantique, CP 224, Université libre de Bruxelles (ULB), 1050 Brussels, Belgium

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.


In quantum cryptography, device-independent (DI) protocols can be certified secure without requiring assumptions about the inner workings of the devices used to perform the protocol. In order to display nonlocality, which is an essential feature in DI protocols, the device must consist of at least two separate components sharing entanglement. This raises a fundamental question: how much entanglement is needed to run such DI protocols? We present a two-device protocol for DI random number generation (DIRNG) which produces approximately $n$ bits of randomness starting from $n$ pairs of arbitrarily weakly entangled qubits. We also consider a variant of the protocol where $m$ singlet states are diluted into $n$ partially entangled states before performing the first protocol, and show that the number $m$ of singlet states need only scale sublinearly with the number $n$ of random bits produced. Operationally, this leads to a DIRNG protocol between distant laboratories that requires only a sublinear amount of quantum communication to prepare the devices.

► BibTeX data

► References

[1] Antonio Acínand Lluis Masanes ``Certified randomness in quantum physics'' Nature 540, 213-219 (2016).

[2] Nicolas Brunner, Daniel Cavalcanti, Stefano Pironio, Valerio Scarani, and Stephanie Wehner, ``Bell nonlocality'' Rev. Mod. Phys. 86, 419–478 (2014).

[3] S. Pironio, A. Acín, S. Massar, A. Boyer de la Giroday, D. N. Matsukevich, P. Maunz, S. Olmschenk, D. Hayes, L. Luo, T. A. Manning, and C. Monroe, ``Random numbers certified by Bell's theorem'' Nature 464, 1021 (2010).

[4] Umesh Vaziraniand Thomas Vidick ``Certifiable quantum dice'' Phil. Trans. R. Soc. A 370, 3432–3448 (2012).

[5] Matthew Coudronand Henry Yuen ``Infinite randomness expansion and amplification with a constant number of devices'' (2013).

[6] Carl A. Millerand Yaoyun Shi ``Robust protocols for securely expanding randomness and distributing keys using untrusted quantum devices'' J. ACM 63, 33:1–33:63 (2016).

[7] Kai-Min Chung, Yaoyun Shi, and Xiaodi Wu, ``Physical randomness extractors: generating random numbers with minimal assumptions'' (2014).

[8] Charles H. Bennett, Herbert J. Bernstein, Sandu Popescu, and Benjamin Schumacher, ``Concentrating partial entanglement by local operations'' Phys. Rev. A 53, 2046–2052 (1996).

[9] Antonio Acín, Serge Massar, and Stefano Pironio, ``Randomness versus Nonlocality and Entanglement'' Phys. Rev. Lett. 108, 100402 (2012).

[10] Reinhard F. Werner ``Quantum states with Einstein-Podolsky-Rosen correlations admitting a hidden-variable model'' Phys. Rev. A 40, 4277–4281 (1989).

[11] F. J. Curchod, M. Johansson, R. Augusiak, M. J. Hoban, P. Wittek, and A. Acín, ``Unbounded randomness certification using sequences of measurements'' Phys. Rev. A 95, 020102 (2017).

[12] Frederic Dupuis, Omar Fawzi, and Renato Renner, ``Entropy accumulation'' (2016).

[13] Rotem Arnon-Friedman, Renato Renner, and Thomas Vidick, ``Simple and tight device-independent security proofs'' (2016).

[14] Rotem Arnon-Friedman, Frédéric Dupuis, Omar Fawzi, Renato Renner, and Thomas Vidick, ``Practical device-independent quantum cryptography via entropy accumulation'' Nat. Commun. 9, 459 (2018).

[15] Cédric Bampsand Stefano Pironio ``Sum-of-squares decompositions for a family of Clauser-Horne-Shimony-Holt-like inequalities and their application to self-testing'' Phys. Rev. A 91, 052111 (2015).

[16] Wassily Hoeffding ``Probability Inequalities for Sums of Bounded Random Variables'' J. Am. Stat. Assoc. 58, 13–30 (1963).

[17] Ben W. Reichardt, Falk Unger, and Umesh Vazirani, ``A classical leash for a quantum system: command of quantum systems via rigidity of CHSH games'' (2012).

[18] Mark Wilde ``Quantum Information Theory'' Cambridge University Press (2013).

[19] Michael A. Nielsenand Isaac L. Chuang ``Quantum Computation and Quantum Information'' Cambridge University Press (2000).

[20] Richard Cleveand David P. DiVincenzo ``Schumacher's quantum data compression as a quantum computation'' Phys. Rev. A 54, 2636–2650 (1996).

[21] R. König, R. Renner, and C. Schaffner, ``The operational meaning of min- and max-entropy'' IEEE Trans. Inf. Theory 55, 4337–4347 (2009).

[22] Marco Tomamichel ``A framework for non-asymptotic quantum information theory'' thesis (2012).

[23] Benjamin Schumacher ``Quantum coding'' Phys. Rev. A 51, 2738–2747 (1995).

[24] Thomas M. Coverand Joy A. Thomas ``Elements of Information Theory'' John Wiley & Sons (2012).

[25] A. Winter ``Coding theorem and strong converse for quantum channels'' IEEE Trans. Inf. Theory 45, 2481–2485 (1999).

[26] T. Ogawaand H. Nagaoka ``A new proof of the channel coding theorem via hypothesis testing in quantum information theory'' 2002 IEEE International Symposium on Information Theory, 2002. Proceedings 73 (2002).

Cited by

[1] Shuai Zhao, Ravishankar Ramanathan, Yuan Liu, and Paweł Horodecki, "Tilted Hardy paradoxes for device-independent randomness extraction", Quantum 7, 1114 (2023).

[2] Abhishek Sadhu and Siddhartha Das, "Testing of quantum nonlocal correlations under constrained free will and imperfect detectors", Physical Review A 107 1, 012212 (2023).

[3] Matthias Christandl, Nicholas Gauguin Houghton-Larsen, and Laura Mancinska, "An Operational Environment for Quantum Self-Testing", Quantum 6, 699 (2022).

[4] David Schmid, Thomas C. Fraser, Ravi Kunjwal, Ana Belen Sainz, Elie Wolfe, and Robert W. Spekkens, "Understanding the interplay of entanglement and nonlocality: motivating and developing a new branch of entanglement theory", Quantum 7, 1194 (2023).

[5] Jurij Volčič, "Constant-sized self-tests for maximally entangled states and single projective measurements", Quantum 8, 1292 (2024).

[6] Elie Wolfe, David Schmid, Ana Belén Sainz, Ravi Kunjwal, and Robert W. Spekkens, "Quantifying Bell: the Resource Theory of Nonclassicality of Common-Cause Boxes", Quantum 4, 280 (2020).

[7] Ivan Šupić and Joseph Bowles, "Self-testing of quantum systems: a review", Quantum 4, 337 (2020).

[8] Thomas Van Himbeeck, Jonatan Bohr Brask, Stefano Pironio, Ravishankar Ramanathan, Ana Belén Sainz, and Elie Wolfe, "Quantum violations in the Instrumental scenario and their relations to the Bell scenario", Quantum 3, 186 (2019).

[9] Peter J. Brown, Sammy Ragy, and Roger Colbeck, "A Framework for Quantum-Secure Device-Independent Randomness Expansion", IEEE Transactions on Information Theory 66 5, 2964 (2020).

[10] Xavier Coiteux-Roy, Elie Wolfe, and Marc-Olivier Renou, "No Bipartite-Nonlocal Causal Theory Can Explain Nature’s Correlations", Physical Review Letters 127 20, 200401 (2021).

[11] Rotem Arnon-Friedman, Renato Renner, and Thomas Vidick, "Simple and Tight Device-Independent Security Proofs", SIAM Journal on Computing 48 1, 181 (2019).

[12] Tony Metger, Omar Fawzi, David Sutter, and Renato Renner, 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS) 844 (2022) ISBN:978-1-6654-5519-0.

[13] Rotem Arnon-Friedman, Renato Renner, and Thomas Vidick, "Simple and tight device-independent security proofs", arXiv:1607.01797, (2016).

[14] Rotem Arnon-Friedman, "Reductions to IID in Device-independent Quantum Information Processing", arXiv:1812.10922, (2018).

The above citations are from Crossref's cited-by service (last updated successfully 2024-06-22 05:45:30) and SAO/NASA ADS (last updated successfully 2024-06-22 05:45:31). The list may be incomplete as not all publishers provide suitable and complete citation data.